Congruence

Definition: Let a,b be integers, n is a Natural number. Then a is congruent to b modulo n iff n | (a-b).

Or "b is the remainder when you do integer division of a % n".

Then if a ≡ 0 (mod m) then n divides a.

Congruence is an Equivalence Relation (CER)

Let n be Natural. Let a,b,c be Integers. Then

• a ≡ a (mod n)
• a ≡ b (mod n) => b ≡ a (mod n)
• (Transitivity) a ≡ b (mod n) and b ≡ c (mod n) => a ≡ c (mod n)

Properties of Congruence (PC)

If a ≡ a' (mod m) and b ≡ b' (mod m) then

1. a + b ≡ a' + b' (mod m)
2. a - b ≡ a' - b' (mod m)
3. ab ≡ a'b' (mod m)
4. If a ≡ b (mod m) then a^k ≡ b^k (mod m)

The past two theorems basically state that a ≡ b is a "kind of" equality between a and b in modulus m.

Congruence and Division (CD)

If ac ≡ bc (mod m) and gcd(m,c) = 1, then a ≡ b (mod m)

This is stating that if gcd(m,c)=1, then c is unique in modulus m.

Congruent iff Same Remainder (CISR)

a ≡ b (mod m) iff a and b have the same remainder when divided by m.

States the property of the modulus operator %

Linear Congruences

Solving linear equations in modulo m. Some linear congruences have no solution, dependent on their gcd.

Linear Congruence Theorem 1 (LCT 1)

Let gcd(a,m) = d ≥ 1. The equation ax ≡ c (mod m) has a solution iff d | c.
If x0 is a solution, the complete solution is x ≡ x0 (mod m/d)

If the coefficient of x divides m, then x is multiplied by 0 and has no solution when c is not congruent to 0.

There are d solutions modulo m. When gcd(a,m)≠1, then the range (set of possible values of ax) is restricted (less than m).

Relating Everything

(GCD CT) If ax + by = d has a soltuion, and d is a positive common divisor of a and b, then gcd(a,b)=d.

Reversing, we know that if (EEA) gcd(a,b)=d, then there is a solution to ax + by = d that can be computed with EEA. ax + by = d is a linear diophantine equation. Extending this, ax + by = c has a solution iff d|c. This can be expanded to describe a class of solutions: x0 + (b/d)n, y0 - (a/d)n.

gcd is a restricting factor in solutions to LDE. This extends to linear congruences, since linear congruences are another way to express LDEs. LCT1 and 2 show the number of possible solutions to any linear congruence equation.

Fermat's Little Theorem

If p is prime, p doesn't divide a, then a^(p-1) ≡ 1 (mod p)

Integral for reducing complex exponential expressions in a prime modulus

For remainder of 3141^2001 divided by 17, 3141 ≡ 13 (mod 17). By FlT, a^16 ≡ 1 (mod 17).

• 3141^2001 ≡ 13^2001 (mod 17)
• 13^2001 = (13^125)^16 • 13
• 13^2001 ≡ (1)^16•13 (mod 17)

Chinese Remainder Theorem

For solving simultaneous congruences.

If gcd(m1,m2) = 1, then for any a1, a2, there exists a solution to the simultaneous congruences

• n ≡ a1 (mod m1)
• n ≡ a2 (mod m2)

If n = n0 is one solution, the complete solution is n ≡ n0 (mod m1•m2)

To solve, show hypothesis first. Then expand one congruence using definition. Sub into the other congruence equation to get a linear congruence.

Splitting Modulus

Special case of simultaneous congruences where n is congruent to the same thing in different moduluses.

Can also be used to simplify polynomial congruences, by splitting the mod and applying FlT.

If p and q are coprime, then (x ≡ a (mod p) and x ≡ a (mod q) ) iff x ≡ a (mod pq)