Addition and multiplication
(1): reordered gives .
(2): Follows trivially from (1)
implies . For greater exponents the statement is true by induction.
Combination with different moduli
If , then the converse also holds:
General simultaneous congruences
It holds, that
where is the solution set.
(): First, we prove that must be equivalent to modulo :
The set of solutions is defined modulo , because given it follows, that
where . By subtracting the third row from the first one and the fourth row from the second one we get:
So must be a multiple of both and and therefore:
(): By assumption, we know that for some
Also, as stated in the Bézout Lemma, we can write the greatest common divisor as a linear combination:
By replacing with the linear combination we get:
Assuming the solution is defined modulo , it follows that: