implies a2≡b2modm. For greater exponents the statement is true by induction.
Combination with different moduli
x≡amodn1n2⇒{xx≡amodn1≡amodn2
If gcd(n1,n2)=1, then the converse also holds: xx≡amodn1≡amodn2}⇒x≡amodn1n2
General simultaneous congruences
It holds, that xxL≡a1modn1≡a2modn2=∅⎭⎪⎪⎬⎪⎪⎫⇔{a1x1≡a2modgcd(n1,n2)≡x2modlcm(n1,n2)∀x1,x2∈L
where L is the solution set.
Proof
(⇒): First, we prove that a1 must be equivalent to a2 modulo gcd(n1,n2): {xx≡a1modn1≡a2modn2⇒{x−a1x−a2≡0modn1≡0modn2⇒{x−a1x−a2≡0modgcd(n1,n2)≡0modgcd(n1,n2)⇒x−a1−x+a2≡0modgcd(n1,n2)⇒a2−a1≡0modgcd(n1,n2)⇒a1≡a2modgcd(n1,n2)
The set of solutions L is defined modulo lcm(n1,n2), because given x1,x2∈L=∅ it follows, that x1x1x2x2=a1+k1⋅n1=a2+k2⋅n2=a1+k3⋅n1=a2+k4⋅n2
where k1,k2,k3,k4∈Z. By subtracting the third row from the first one and the fourth row from the second one we get: x1−x2x1−x2=a1+k1⋅n1−a1−k3⋅n1=(k1−k3)⋅n1=a2+k2⋅n2−a2−k4⋅n2=(k2−k4)⋅n2
So x1−x2 must be a multiple of both n1 and n2 and therefore: x1−x2≡0modlcm(n1,n2)
(⇐): By assumption, we know that for some k∈Za1−a2=k⋅gcd(n1,n2)
Also, as stated in the Bézout Lemma, we can write the greatest common divisor as a linear combination: gcd(n1,n2):=u⋅n1+v⋅n2
By replacing gcd(n1,n2) with the linear combination we get: a1−a2=k⋅u⋅n1+k⋅v⋅n2