Here are some symbols to use in constructing this page . . . . . .  not a ≡b is ab  bold not a ≡b is ab

Definitions and fundamental properties of congruences

The following symbols were introduced by Gauss in his Disquisitiones arithmeticae: If a-b is divisible by n, then a is said to be congruent to b (mod n), which is expressed as

a ≡ b (mod n)

When a-b is not divisible by n, we say that a and b are incongruent (mod n), which is expressed as

a b (mod n)

From the definitions, above, the following rules for operating with congruences can be derived:

1. If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n).

2. If a ≡ b (mod n) and c ≡ d (mod n), then a+c ≡ b+d (mod n), and also a-c ≡ b-d (mod n).

3. If a ≡ b (mod n) and c ≡ d (mod n), then ac ≡ bd (mod n)

4. If a ≡ b (mod n) then ac ≡ bc (mod n),
     which follows from rule 3 with c=d

5. If a ≡ b (mod n) then a^m ≡ b^m (mod n) for any positive integer exponent m.

6. If f(x) is a polynomial with integral coefficients and if a ≡ b (mod n), then f(a) ≡ f(b) (mod n),
     which follows from repeated applications of rules 2, 4, and 5.

7. If ma ≡ mb (mod n) and if d=GCD(m,n), then a ≡ b (mod n/d)

8. If ma ≡ mb (mod n) and if GCD(m,n)=1, then a ≡ b (mod n),
     which follows from rule 7 with d=GCD(m,n)=1

Residue classes and residue systems

Residue class - integers a and b are said to be members of the same residue class (mod m) when they have the same principle remainder (mod n).  Thus there are n residue classes (mod n), corresponding to the n principle remainders 0, 1, 2, ..., n-1.

a and b belong to the same residue class (mod n) iff a ≡ b (mod n).

Complete Residue system - any set of integers {a₁, a₂, ..., a_n} representing all the residue classes (mod n) is called a complete residue system (mod n).  The simplest complete residue system is 0, 1, 2, ..., n-1.

Theorem: If natural numbers m,n are coprime and r is an integer, then the set S of n numbers

S = {r, m+r, 2m+r, ... (n-1)m+r}

form a complete residue system (mod n).

Proof: Any two of the elements of S are incongruent (mod n), because if h ≠ k exist such that hm+r ≡ km+r (mod n), then (h-k)m | n, and since GCD(m,n)=1, h ≡ k (mod n) contrary to hypothesis.  Supposing k exists such that none of the elements of S is congruent to k (mod m), so by the pigeonhole principle, one of the n equivalence classes is represented by two different elements of S, a contradiction.

Theorem: If natural number m,n are coprime, and if x runs through a complete residue system (mod n), and if y runs through a complete residue system (mod m), then the m*n numbers mx+ny form a complete residue system mod m*n.

Proof: As in the previous theorem, it is sufficient to show that no two numbers mx₁+ny₁ and mx₂+ny₂ are congruent (mod m*n).  (Remainder of proof is left to the reader . . . . . . )

Reduced Residue system - a set of representatives of the residue classes of the φ(n) numbers that are coprime to n is called a reduced residue system (mod n).

Theorem: If m,n are coprime, and if u runs through a reduced residue system (mod n), and if v runs through a reduced residue system (mod m), then the φ(m)*φ(n) integers mu+nv form a reduced residue system (mod m*n).  (Again, the proof is left to the reader . . . . . . )

Fermat's Theorem, and the Totient Theorem

 . . . . . . refer to the relevant pages here

Algebraic congruences

 . . . . . . a whole slew of theorems related to the solutions of f(x) ≡ 0 (mod n)

and in particular, where n is a prime or a prime power.

Wilson's Theorem and its generalization

x^p-1 - 1 ≡ 0 (mod p)

has roots x ≡ 1, 2, 3, ..., p-1.  By theorem (a polynomial is the product of x minus each of its roots), we have then identically

x^p-1 - 1 ≡ (x-1)(x-2)...(x-(p-1)) (mod p)

Letting x=p, it follows that (p-1)! ≡ -1 (mod p), which is Wilson's Theorem

Theorem: n (n>1) is a prime iff (n-1)!+1 divides n

Proof: Wilson's theorem gives the "only if" direction.  Now it remains to be shown that if (n-1)!+1 divides n then n is prime, or contrapositively, if n is composite, then (n-1)!+1 does not divide n.  This is shown as follows: let q be a prime divisor of n with q<n, so (n-1)! is divisible by q, so (n-1)+1 can't be divisible by q.

Theorem: If p is prime, and p ≡ 1 (mod 4), then x²≡-1 (mod p) has two solutions x≡&plusmn;((p-1)/2)! (mod p),
and furthermore, of p ≡ 3 (mod 4), then x²≡-1 (mod p) has no solutions.

Proof: . . . . . .  The second part is proved directly using Fermat's little theorem.

 . . . . . .  Well, there's a whole lot more in the number theory book about congruences, and I would like to get to that sometime and finish this page!

Internet references

Related pages in this website

Counting Primes method of proving the following are integers: C(n,k) = n!/(k!(n-k)!), (2a)!(2b)!/((a+b)!a!b!)

Combination identities proves the standard combination identities, including C(n,k) = C(n-1,k-1) + C(n-1,k) and many others.

Floor Function Identities, which are used in proofs that combinatorial identities are integers

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]