Modular Arithmetic Theorems

On this page my goal is to explain and prove some important theorems in modular arithmetic in hopes for you to gain a better understanding of why the theorems are important and how they work.

If a ≡ b (mod m) and c ≡ d (mod m), then (a + c) ≡ (b + d) (mod m)

Given a ≡ b (mod m) and c ≡ d (mod m), we know by the Congruence definition that a ≡ b (mod m) implies m ∣ (a-b) and c ≡ d (mod m) implies m ∣ (c-d). Then by definition of divides, which states for some integers x, y, and z, x ∣ y if xz=y, we know for some integers k and j ,

mk=(a-b) and mj=(c-d)

Which implies that,

mk+mj=(a-b) +(c-d) => m(k+j)= (a+c)-(b+d)

Since k+j is an integer because the set of all integers is closed under addition we know by the congruence definition that m(k+j)= (a+c)-(b+d) implies (a+c) ≡ (b+d) (mod m). Therefore, If a ≡ b (mod m) and c ≡ d (mod m), then (a + c) ≡ (b + d) (mod m). Q.E.D.

A similar process can be done to prove Theorem 2. I’ll let you try to prove Theorem 2 using what you have learned so far.

If a ≡ b (mod m) and c ≡ d (mod m), then (a ⋅ c) ≡ (b ⋅ d) (mod m)

For any natural numbers c and n, we have c · 10ⁿ ≡ c (mod 9).

Proof:
Given natural numbers c and n and c ⋅ 10ⁿ ≡ c (mod 9) we know that c ≡ c and 10ⁿ ≡ c (mod 9). This is because 10 ≡ 1 (mod 9), then suppose we combine the equation with itself to obtain 100 = 10 ⋅ 10 ≡ 1 ⋅ 1 ≡ 1 (mod 9). We can do this as many times as necessary, (e.g., n times), and therefore have 10ⁿ ≡ 1ⁿ ≡ 1 (mod 9) for any natural number n. Thus, by Theorem 2 we can combine c ≡ c and 10ⁿ ≡ c (mod 9) to obtain c · 10ⁿ ≡ c (mod 9). Therefore, for any natural numbers c and n, we have c · 10ⁿ ≡ c (mod 9).

This is a shortcut for knowing any congruence of c · 10ⁿ in mod 9.

If p is prime and p ∤ a , then a^p-1 ≡ 1 mod p

Proof:
We will prove Fermat’s Little Theorem by induction. For this proof we will use the Binomial Theorem which states:

For integers a, b and n ,

(a+b)ⁿ = ∑ _{i=0, n} (n Cr k)(a ^n-k )(b^k) .

Where k and n are integers.

Consider, a=1 for a^p-1 we know p ∤ a because p is prime and the only integer that divides 1 is itself. So 1^p-1 ≡ 1 mod p is true. Assume that a^p-1 ≡ 1 mod p is true. By multiplying a to both sides of a^p-1 ≡ 1 mod p we obtain the expression a^p ≡ a mod p . Now we want to show that based on our assumption (a+1)^p-1 ≡ 1 mod p is also true. By the Binomial Theorem we know,

(a+1)^p = ∑ _{i=0, n} (p Cr k)(a ^p-k )(1^k) .

Furthermore,

∑ _{i=0, n} (p Cr k)(a ^p-k )(1^k = a^p + (p Cr 1)(a^p-1)(1)+ (p Cr 2)(a^p-2)(1²) +...+(p Cr p-1)(a)(1^p-1)+1^p

Note that 1 raised to the power of any integer is always 1 and that p divides into any binomial coefficient of the form, (p Cr k) because (p Cr k)=(p!)/(k!(p-k)1) indicating that (p Cr k)=p[(p-k!)/(k!(p-k)!)] => p ∣ p[(p-1!)/(k!(p-k)1)]. By translating all of our term in a^p + (p Cr 1)(a^p-1)(1)+ (p Cr 2)(a^p-2)(1²) +...+(p Cr p-1)(a)(1^p-1)+1^p to classes of mod p all of are middle terms go to [0] because any multiple of p is [0] in mod p . Thus, we are left with the following terms: (a+1)^p = a^p +1. Thus, (a+1)^p ≡ a^p +1 mod p
Therefore, if a^p-1 ≡ 1 mod p is true then (a+1)^p-1 ≡ 1 mod p is true and since we know a^p-1 ≡ 1 mod p is true for a=1 we know that it is true for all integers. Q.E.D.

Importance: Fermat’s Little Theorem is important in number theory because it helps use compute powers of integers modulo prime numbers. It has a fundamental role in the application of public-key cryptography which we will dive into more deeply on the Application page.

Let m₁ ,m₂ ,…,m_k be pairwise relatively prime. Then the system of simultaneous linear congruences
x ≡ c₁ (mod m₁ ),
x ≡ c₂ (mod m₂ ), …,
x ≡ c_k (mod m_k )
always has a solution, which is of the form x ≡ c (mod m₁m₂ … m_k ).

Before I start this proof I would like to list some Lemmas I feel are vital for proving The Chinese Remainder Theorem:

Let m and a₁, . . . , a_n be positive integers. If m is relatively prime to each of a₁, . . . , a_n then it is relatively prime to their product a₁ · · ·a_n .

Let m and a₁, . . . , a_n be positive integers. If m is a multiple of each of a₁, . . . , a_n, then m is a multiple of [ a₁, . . . , a_n].

Let a₁, . . . , a_n be positive integers. If a₁, . . . , a_n are pairwise relatively prime (that is, (a_i , a_j ) = 1 for i ≠ j), then [ a₁, . . . , a_n] = a₁ · · ·a_n .

Proof:
Suppose p_k is equal to the product of some combination of the m_i’s. Then by Lemma C.1,

(p_k, m_k) = 1

Hence, there exist

s_k, t_k such that s_kp_k + t_km_k = 1 which implies s_kp_k = 1 (mod m_k)

Now we let,

x = a₁p₁s₁ + a₂s₂p₂ + · · · + a_np_ns_n.

Further suppose that there exist p_j such that j ≠ i then, we know that m_k ∣ p_j since all the m_i’s are relatively prime. Now when we mod m_k all the terms but the k-th term are [0] in mod m_k:

x = a_kp_ks_k = a_k · 1 = a_k (mod m_k).

This shows x is a solution to the system of congruences giving us a formula for x. So now we just need to show that for two solutions to the system of congruences x and y that x = y (mod m₁ · · · m_n). So now we have,

x = a₁ (mod m₁) and y = a₁ (mod m₁)
x = a₂ (mod m₂) and y = a₂ (mod m₂)
.
.
.
x = a_n (mod m_n) and y = a_n (mod m_n)

By using a bit of algebra we see,

x = a_k = y (mod m_k) so (x − y) = 0 (mod m_k) and by definition 3 we know m_k ∣ (x − y).

Thus, (x − y) is a multiple of all the m_i’s, so [m₁, . . . , m_n] ∣ (x − y). But the m_i’s are all pairwise relatively prime by our given, so by Lemma C.3, m₁ · · · m_n ∣ (x − y), or x ≡ y (mod m₁ · · · m_n). This means that the solution to the congruences is unique. Therefore,
Let m₁ ,m₂ ,…,m_k be pairwise relatively prime. Then the system of simultaneous linear congruences

x ≡ c₁ (mod m₁ ),
x ≡ c₂ (mod m₂ ), …,
x ≡ c_k (mod m_k )

always has a solution, which is of the form x ≡ c (mod m₁m₂ … m_k ). Q.E.D.

Importance: This is a special case for Theorem 4 where the m_i’s , i={1, 2, 3,..., k} , are reactively prime meaning no integer greater than one that divides them all. This Theorem allows us to easily indicate whether a system of congruences has a solution that can be found and how to find that solution. The Chinese Remainder Theorem has an important role in Cryptography which we will later discuss on the Application page.