Modular Arithmetic

Modular arithmetic is a notation and set of mathematics that were first introduced by Carl Friedrich Gauss.

The major insight is that equations can fruitfully be analyzed from the perspective of remainders. Standard equations use the '=' sign. Modular arithmetic uses the '≡' sign. Two values that are '≡' to each other are said to be congruent relative the modulus. In the case below, the modulus is 3.

Here's an example of a modular equation:

7 ≡ 1 (mod 3).

By definition, this means that 3 divides 7 - 1.

Here's a more formal definition of a modular equation:

Definition 1: a ≡ b (mod c) if and only if c divides a - b.

This definition tells us the following is true:

7 ≡ 1 ≡ 10 ≡ -2 (mod 3).

Now, one of the most interesting things about '≡' is that it follows many of the same relations as '='.

Lemma 1: For any value a,b,c,d,n where a ≡ b (mod n) and c ≡ d (mod n):
(a) a + c ≡ b + d (mod n)
(b) a - c ≡ b - d (mod n)
(c) ac ≡ bd (mod n)

(1) n divides a - b, and n divides c - d. [definition of ≡ ]
(2) We know that n divides (a + c) - (b + d) since this is equal to: (a -b) + (c - d).
(3) We know that n divides (a - c) - (b - d) since this is equal to: (a - b) - (c - d).
(4) We know that n divides ac - bd since this is equal to : c(a - b) + b(c - d).

QED

Lemma 2: If a ≡ b (mod n) then:
(a) a + c ≡ b + c (mod n)
(b) a - c ≡ b - c (mod n)
(c) ac ≡ bc (mod n)

(1) So, we are given that n divides a - b.
(2) We know (a) since n divides a + c - (b + c) = a - b.
(3) We know (b) since n divides a - c - (b - c) = a - b.
(4) We know (c) since n divides ac - bc = c(a - b)

QED

Corrolary 2.1: a ≡ d (mod n), b ≡ e (mod n), c ≡ f (mod n), then:
a + b + c ≡ d + e + f.

(1) We know that a + b ≡ d + e from above.
(2) We therefore know that (a + b) + c ≡ (d + e) + f.

QED

Lemma 3: a + b + c ≡ 0, a ≡ 0 (mod p), then b + c ≡ 0 (mod p).(1) a + b + c ≡ 0 (mod p) [Definition of ≡ ]

(2) b ≡ c (mod p) → a + b ≡ a + c (mod p) [See above]

(3) So, 0 ≡ a + b + c ≡ 0 + b + c ≡ b + c (mod p).

QED

Lemma 4:  if gcd(k,p)=1 and kx ≡ ky (mod p), then x ≡ y (mod p)

Proof:

(1)  Since kx ≡ ky (mod p), there exists a such that ap = kx - ky = k(x-y)

(2)  Since gcd(k,p)=1, it follows that p divides (x-y)

(3)  So that x ≡ y (mod p)

QED