Congruences

Definition If a nonzero integer m divides the difference a-b, we say that a is congruent to b modulo m and write a º b(mod m). If a-b is not divisible by m, we say that a is not congruent to b modulo m.

Theorem 2.1 Let a,b,c,d,x,y denote integers. Then

0. a º a (mod m).

1. a º b (mod m),
b º a (mod m),
a-b º 0 (mod m)
and
b-a º 0 (mod m)
are equivalent statements.

2. If a º b (mod m) and b º c (mod m), then a º c (mod m).

3. If a º b (mod m) and c º d (mod m), then ax+ cy º bx + dy (mod m).

4. If a º b (mod m) and c º d (mod m), then ac º bd (mod m).

5. If a º b (mod m) and d|m, d > 0, then a º b (mod d).

6. If a º b (mod m) then ac º bc (mod mc) for c > 0.

Theorem 2.2 Let f denote a polynomial with integral coefficients. If a º b (mod m), then f(a) º f(b) (mod m).

Theorem 2.3 (1) ax º ay (mod m) if and only if x º y (mod [m/ (a,m)]).

(2) If ax º ay (mod m) and (a,m) = 1, then x º y (mod m).

(3) x º y (mod mi) for i = 1,2,···,r if and only if x º y (mod[m1,m2,···,mr]).
 

Definition. If x º y (mod m) then y is called a residue of x modulo m. A set x1, x2,···,xm is called a complete residue system modulo m if for every integer y there is one and only one xj such that y º xj (mod m).

Theorem 2.4 If x º y (mod m), then (x,m) = (y,m).

Definition. A reduced residue system modulo m is a set of integers ri such that (ri,m) = 1, ri º / rj (mod m) if i ¹ j, and such that every x prime to m is congruent modulo m to some number ri of the set.

Theorem 2.5 The number f(m) is the number of positive integers less than or equal to m that are relatively prime to m.

Theorem 2.6 Let (a,m) = 1. Let r1, r2, ··· , rn be a complete, or a reduced, residue system modulo m. Then ar1, ar2, ··· , arn is a complete, or a reduced, residue system, respectively, modulo m.

Theorem 2.7 Fermat's Theorem. Let p denote a prime. If p does not divide a, then ap-1 º 1 mod p. For every integer a, ap º a mod p.

Theorem. 2.8 Euler's generalization of Fermat's theorem. If (a,m) = 1, then

af(n) º 1 mod  m

Proof. Let r1, r2,...,rf(m) be a reduced system modulo m. Then ar1, ar2,...,arf(m) is also a reduced residue system modulo m. Hence corresponding to each ri there is one and only one arj such that ri º arj mod m. Furthermore, different ri will have different corresponding arj. Therefore

(ar1)(ar2)···(arf(m)) º r1·r2···rf(m) mod  m. 

Thus

af(m)r1·r2···rf(m) º r1·r2···rf(m) mod  m. 

Now each rj is relatively prime to m, we obtain af(m) º 1 mod m.

Proof of Fermat's Theorem. If p does not divide m, then (a,p) = 1 and so af(p) º 1 mod m. But f(p) = p-1, since 1,2,···,p-1 are relatively prime to p.

Corollary 2.9 If (a,m) = 1, then ax º b mod m has a solution x = x1. All solutions are given by x = x1 + jm, where j = 0, ±1, ±2,···.

Proof. Set x1 = af(m)-1b. If x is another solution, then ax - ax1 º b - b º 0 mod m. Since (a,m) = 1, x - x1 º 0 mod m, so x = x1 + jm for some integer j.

Theorem 2.10 Wilson's Theorem. If p is a prime, then (p-1)! º -1 mod p.

Proof. The result holds for p = 2 and for p = 3. Suppose that p ³ 5. For each integer j with 2 £ j £ p-2 we have (j,p) = 1 and so there is a unique i with ji º 0 mod p and this i is in the range 2 £ i £ p-2. Multiplying these pairs together we have

2·3···(p-2) º 1 mod  p. 

Therefore

1·2·3···(p-1) º -1 mod  p. 

Theorem. 2.11 Let p be a prime. Then x2 º -1 mod p has a solution if and only if p = 2 or p º 1 mod 4.

Proof. If p = 2 we have the solution x = 1. For odd p we can write Wilson's theorem in the form

(1·2···j··· p-1
2		 )( p+1
2		 ···(p-j)···(p-2)(p-1)) º -1 mod  p. 

Pairing off j in the second half with p - j in the first half, we have

1·(p-1)·2·(p-2)···( p-1
2		 )( p+1
2		 ) º -1 mod  p. 

Thus

(-12)·(-22)···(-  p-1
2		 )2 º -1 mod  p

or

(-1)(p-1)/2(1·2··· p-1
2		 )2 º -1 mod  p. 

Since p º 1 mod 4, (-1)(p-1)/2 = 1, so we have the solution x = 1·2···[(p-1)/ 2].

If p ¹ 2 and p ¹ 4k + 1, then p = 4k + 3 so (p-1)/2 is odd. If x2 º -1 mod p, then xp-1 º x2·(p-1)/2 º -1 mod p. Since p does not divide x, we have xp-1 º 1 mod p, a contradiction.