Modular Arithmetic

For integers a, b and n > 0, what does a ≡ b (mod n) mean?

a and b leave the same remainder when divided by n, or that there exists an integer x such that a = b + nx

How can ‘a and b leave the same remainder when divided by n’ be written formally?

n | (a − b) (a - b is divisible by n)

What are the properties of congruence if a ≡ b (mod n) and c ≡ d (mod n)?

Addition: a + c ≡ b + d (mod n)

Subtraction: a − c ≡ b − d (mod n)

Multiplication: ac ≡ bd (mod n)

What does ax ≡ b (mod n) mean?

when ax is divided by n, it leaves the same remainder as b

When does ax ≡ b (mod n) have a solution?

Iff hcf(a, n) | b which is the rule that tells you whether its solvable or not e.g. if hcf(a, n) = 1 then there’s exactly one solution mod n

Why does hcf(a, n) = 1 mean there’s only 1 solution?

Because Bézout’s Lemma guarantees integers x, y such that ax + ny = 1 so x acts as a multiplicative inverse of a mod n. We can multiply both sides of the congruence by that inverse to isolate x

What is the Chinese Remainder Theorem?

If the moduli n₁, n₂, …, n_k are pairwise coprime (no common factors other than 1), then the system:

x = a₁ (mod n₁)

x = a₂ (mod n₂)

…

x = a_k (mod n_k)

Has exactly 1 solution N = n₁n₂…n_k.

(If the moduli don’t “interfere” with each other (they’re coprime), you can combine several modular equations into one single equivalent equation)

What is Fermat’s Little Theorem?

If p is prime and a is not divisible by p, then: a^p−1 ≡ 1 (mod p)

Let a, b, c be integers and n be a natural number. What are the properties of congruence modulo n?

• Reflexive property: a ≡ a mod n

• Symmetric property: If a ≡ b mod n then b ≡ a mod n

• Transitive property: If a ≡ b mod n and b ≡ c mod n then a ≡ c mod n

Prove the properties of congruence modulo n

• Reflexive property: a ≡ a + 0n so a ≡ a mod n

• Symmetric property: Since a ≡ b mod n, there exists an integer x such that a = b + nx. Then b = a - nx = a + n(-x) and -x is an integer. So b ≡ a mod n

• Transitive property: Since a ≡ b mod n and b ≡ c mod n, there exists integers x, y such that a = b + nx and b = c + ny. Then a = c + ny + nx so a = c + n(x + y) where x + y is an integer. So a ≡ c mod n

Prove the lemma: Let n be a natural number and a, b be integers. Then a ≡ b mod n iff a and b leave the same remainder when divided by n.

• Use division theorem: there exists a q, q’, r, r’ such that a = qn + r and b = q’ + r’

• Then r is the remainder when a is divided by n and r’ is the remainder when b is divided by n

• So a - b = (q - q’)n + (r - r’)

• Suppose a ≡ b mod n so n | (a - b) and n | ((q - q’)n + (r - r’))

• Then n | (r - r’) and n | (q - q’) by lemma

• Also -n < r - r’ < n

• So r - r’ = 0 thus r = r’ then a - b ≡ (q - q’)n

• Then n | a - b and a ≡ b mod n

Let n, m be natural numbers and a, a’, b, b’ be integers. Suppose a ≡ b mod n and a’ ≡ b’ mod n. Then…

• a + a’ ≡ (b + b’) mod n: Since a + a’ = b + nx + b’ + nx’ so a + a’ = b + b’ + n(x + x’) where x + x’ is an integer

• aa’ ≡ bb’ mod n: aa’ = (b + nx)(b’ + nx’) = bb’ + bnx’ + b’nx + n²xx’ = bb’ + n(bx’ + b’x + nxx’) where bx’ + b’x + nxx’ is an integer

• a^m ≡ b^m mod n: Repeated use of 2nd proof

What is a linear congruence equation?

One of form ax ≡ b mod n

Let n be a natural number and a be an integer. Suppose that a is coprime to n. Then…

There exists an integer z such that az ≡ 1 mod n

Prove the corollary: Let n be a natural number and a, b be integers. Suppose a is coprime to n. Consider ax ≡ b mod n (*). Then there exists an integer s such that the solutions of (*) are given by x ≡ s mod n.

By the theorem that states that if a is coprime to n, there exists an integer z such that az ≡ 1 mod n.

If ax ≡ b mod n then x ≡ (az)x mod n ≡ z(ax) mod n ≡ zb mod n

If x ≡ zb mod n then,

ax ≡ azb mod n ≡ (az)b mod n ≡ b mod n

Therefore we can take s = zb and the solutions of (*) are given by x ≡ s mod n

What is the algorithm to solve linear congruence equations ax ≡ b mod n?

1. Calculate h = hcf(a, n)

2. If h is not a factor of b, there are no solutions. If h | b, consider a’x ≡ b’ mod n’ where a’ = a/h, b’ = b/h and n’ = n/h

3. Find integer s such that a’s ≡ b’ mod n’. To do this, find integer z such that a’z ≡ 1 mod n’ and then set x = zb’. We can find z using extended Euclidean algorithm or find x by inspection

4. The solutions are given by x ≡ s mod n’

Let a, b, x be integers, n be a natural number and h = hcf(a, n). Suppose ax ≡ b mod n. Then…

h | b

Let a, b, x be integers, n be a natural number and h = hcf(a, n). Suppose h | b and let a’ = a/h, b’ = b/h and n’ = n/h. Then…

• ax ≡ b mod n iff a’x ≡ b’ mod n’

• a’ is coprime to n’

Let n be a natural number and a, b, c be integers. Suppose c is coprime to n and ac ≡ bc mod n. Then…

a ≡ b mod n

Let a, b, c be integers. Suppose a is coprime to b, a | c and b | c. Then…

ab | c

Let a, b, c be integers. Suppose a is coprime to c and b is coprime to c. Then…

ab is coprime to c

What is the Chinese Remainder Theorem?

Let n₁, …, n_k be natural numbers and a₁, …, a_k be integers. Suppose hcf(n_i, n_j) = 1 for all i =/ j. Consider the simultaneous congruences (*):

x ≡ a₁ mod n₁

…

x ≡ a_k mod n_k

For every integer s such that the solutions to (*) are given by x ≡ s mod n₁…n_k

What is the definition of a congruence class?

Let n be a natural number and a be an integer. We define the congruence class of a mod n to be [a]_n = {x ∈ Z s.t. x ≡ a mod n}

What are some lemmas about congruence classes?

• [a]_n = [b]_n iff a ≡ b mod n

• [a]_n = [b]_n or [a]_n ∩ [b]_n = empty set

• There are exactly n congruence classes mod n namely [0]_n, [1]_n, …, [n - 1]_n

What is the proof for [a]_n = [b]_n iff a ≡ b mod n?

Suppose [a]_n = [b]_n

Then a ∈ [a]_n = [b]_n

Now suppose a ≡ b mod n. Let x ∈ [a]_n

Then x ≡ a mod n and a ≡ b mod n, so x ≡ b mod n. Thus x ∈ [b]_n

So [a]_n ⊆ [b]_n

Similarly, [b]_n ⊆ [a]_n

Hence, [a]_n = [b]_n

What is the proof for [a]_n = [b]_n or [a]_n ∩ [b]_n = empty set?

Suppose [a]_n ∩ [b]_n =/ empty set

Let x ∈ [a]_n ∩ [b]_n

Then x ≡ a mod n and x ≡ b mod n

So a ≡ x mod n and x ≡ b mod n

Thus a ≡ b mod n

Therefore [a]_n = [b]_n by previous proof

What is the definition of the ring of integers modulo n?

Let n be a natural number. We define Z_n = {[a]_n : a ∈ Z} = {[0]_n, …, [n - 1]_n} and addition and multiplication on Z_n as follows:

Define [a]_n + [b]_n = [a + b]_n and [a]_n ^. [b]_n = [ab]_n

The set Z_n with + and ^. is called the ring of integers mod n. [a]_n can also be written ā

What are the properties of the ring of integers modulo n Z_n?

Let x, y, z belong to Z_n

• x + y = y + x

• x ^. ( y ^. z) = (x ^. y) ^. z

How do we write a ≡ r mod n?

Let n be a natural number and a be an integer. We write a(mod n) for the unique r ∈ {0, 1, …, n - 1} such that a ≡ r mod n

What is Fermat’s Little Theorem?

Let p be a prime natural number and a be an integer. Suppose p is not a factor of a. Then a^p-1 ≡ 1 mod p

What is a corollary of Fermat’s Little Theorem?

Let p be a prime natural number and a be an integer. Then a^p ≡ a mod p

Let p, q be distinct prime natural numbers, k be a natural number and a be an integer. Then…

a^{k(p-1)(q-1)+1} ≡ a mod pq