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.*

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)

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

- a + b ≡ a' + b' (mod m)
- a - b ≡ a' - b' (mod m)
- ab ≡ a'b' (mod m)
- 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.*

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.*

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

*States the property of the modulus operator %*

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

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).*

(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.

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)

*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.

*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)`