Consider two sets and , and a function that maps elements from to the elements of .
- is injective if each element in has at most one element in that maps to it
- is surjective if each element in has at least one element in that maps to it
- is bijective if it is both injective and surjective
- is bijective if and only if it has an inverse
Chinese Remainder Theorem
Given a list of congruences , , , , find an that satisfies all congruences.
Let . If all the are relatively prime () then there is exactly one value of in the set that satisfies all the congruences.
For and , we want to find a number that is a multiple of and , and similarly a number that is a multiple of and . Then is a solution because and .