|
|
|
Here are some symbols to use in constructing this page . . . . . . not
a ≡b is a
b
bold not a ≡b is a
b
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
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 am ≡ bm (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 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 {a1, a2, ..., an} 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 mx1+ny1 and mx2+ny2 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 . . . . . . )
. . . . . . refer to the relevant pages here
. . . . . . 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.
xp-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
xp-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 x2≡-1 (mod p) has
two solutions x≡±((p-1)/2)! (mod p),
and furthermore, of p ≡ 3 (mod 4), then x2≡-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!
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 this Math Help site is Graeme McRae.