Congruences

Congruences

In number theory we say that "a is congruent to b modulo m" if and only if:

(1)
\begin{equation} m | (a - b) \end{equation}

If m | (a - b), then we say:

(2)
\begin{align} a \equiv b \pmod m \end{align}

If a ≡ b mod m, we may also say that "a = b + km for some integer k", or that "a leaves the remainder b when divided by m".

Example 1.

Determine if the following are true:

A) 20 ≡ 5 mod 3
B) 16 ≡ -4 mod 2
C) 91 ≡ 7 mod 13**

A) It should be fairly obvious that 3 | (20 - 5), or 3 | 15, so it is true that 20 ≡ 5 mod 3.
B) Once again it should be obvious that 2 | (16 - (-4)), or 2 | 20, so it is true that 16 ≡ -4 mod 2.
C) Using the definition of congruence we get that 13 | 84, but this is not true. Hence 91 ≡ 7 mod 13 is false.

Lemma 1: If a ≡ b mod m, then there exists a k such that a = b + km.

  • Proof: By the definition that a ≡ b mod m, then m | (a - b). There must exists an integer k such that:
(3)
\begin{align} mk = (a - b) \\ a = b + km \end{align}
  • Thus the proof is complete. Alternatively, we can look at the proof in the reverse direction. Suppose that a = b + km, and show that a ≡ b mod m. By manipulation of the equation we get:
(4)
\begin{equation} km = (a - b) \end{equation}
  • Thus it is rather evident that m | (a - b), since k | m, and k | (a - b). Thus a ≡ b mod m by the definition of congruence.

Lemma 2: Every integer is congruent (mod m) to exactly one of 0, 1, 2, … , m-1.

  • Proof: All integers can be expressed in the form:
(5)
\begin{equation} a = qm + r \end{equation}
  • From the division algorithm, q and r are uniquely determined. For example if we divide 25 by 3, we get that 25 = 8(3) + 1, where 3 and 1 are unique. By the proof 1, we also obtain that since a = r + qm, then a ≡ r mod m. Note that r in this proof is known as the least residue since 0 ≤ r < m.

Example 2

A) What is the least residue (mod 5) of 7?
B) What is the least residue (mod 5) of 9?
C) What is the least residue (mod 5) of 13?
D) What is the least residue (mod 5) of 18?

A) For the first one, if 7 ≡ r mod 5, then 7 = 5(1) + 2. Hence the least residue is 2.
B) 9 ≡ r mod 5, hence the least residue is 4 since 9 = 5(1) + 4.
C) 13 ≡ r mod 5, hence the least residue is 3 since 13 = 5(2) + 3.
D) 18 ≡ r mod 5, hence the least residue is 3, since 18 = 5(3) + 3.

Lemma 3: a ≡ b mod m if and only if a and b leave the same remainder on division by m.

  • Proof: If a and b have the same remainder r when divided by an integer m, then it follows that by the division algorithm:
(6)
\begin{align} a = q_1m + r \quad \mathbf{and} \quad b = q_2m + r \end{align}
  • When we subtract these equations we obtain:
(7)
\begin{align} a - b = (q_1m +r) - (q_2m + r) \\ a - b = q_1m - q_2m \\ a - b = m(q_1 - q_2) \end{align}
  • Hence m | (a - b), and by the definition of congruence a ≡ b mod m.
Note: If instead of doing a - b, we did b - a, we would still get a congruence, namely b ≡ a mod m. Thus we get that a ≡ b ≡ r mod m.

Lemma 4: p | a if and only if a ≡ 0 mod p.

  • Proof: Let's say a ≡ 0 mod p. Thus it follows that p | (a - 0), or p | a, which is what we were trying to prove, hence we are done.

Lemma 5: a ≡ a (mod m) (Reflexive Property)

  • Proof: From the definition of congruence, m | (a - a), and clearly m | 0 for all m.

Lemma 6: If a ≡ b (mod m), then b ≡ a (mod m) (Symmetric Property)

  • Proof: Suppose that $a \equiv b \pmod {m}$. It thus follows that a = b + km for some k. Rewriting this equation we get that b = a - km, which can be rewritten as b = a + (-k)m. Hence $b \equiv a \pmod {m}$.

Lemma 7: If a ≡ b (mod m) and b ≡ c (mod m), then a ≡ c (mod m) (Transitive Property)

  • Proof: From the defintion of congruence, m | (a - b), and m | (b - c). Thus there exists integers x and y such that:
(8)
\begin{align} mx = a - b \quad , \quad my = b - c \end{align}
  • We can manipulate the second equation to isolate for b to obtain:
(9)
\begin{equation} my + c = b \end{equation}
  • And plug it into the first equation to obtain:
(10)
\begin{align} mx = a -(my + c) \\ mx = a - my - c \\ a - c = mx - my \\ a - c = m(x - y) \end{align}
  • Thus a ≡ c mod m by the definition of congruence.

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

  • Proof: By the definitions of congruence we get that m | (a - b), and m | (c - d). We thus get the equations for some integers x and y:
(11)
\begin{align} mx = a -b \quad , \quad my = c - d \end{align}
  • Or rather:
(12)
\begin{align} mx + b = a \quad , \quad my + d = c \end{align}
  • When we add the equations we obtain:
(13)
\begin{align} a + bc= (mx + b) + (my + d) \\ (a + c) - (b + d) = mx + my \\ (a + c) - (b + d) = m(x + y) \end{align}
  • Thus a + c ≡ b + d (mod m).

Lemma 9: If a ≡ b (mod m) and c ≡ d (mod m), then ac ≡ bd (mod m).

  • Proof: By the definition of congruence, we obtain that m | (a - b), and m | (c - d). Thus for some integers x and y:
(14)
\begin{align} mx = a - b \quad , \quad my = c - d \\ mx + b = a \quad , \quad my + d = c. \end{align}
  • Multiplication of these two equations results in:
(15)
\begin{align} ac = (mx + b)(my + d) \\ ac = m^2xy + mxd + myb + bd \\ ac - bd = m^2xy + mxd + myb \\ ac - bd = m(mxy + xd + yb) \end{align}
  • Thus ac ≡ bd mod (m).

Lemma 10: If ac ≡ bc (mod m) and (c, m) = 1, then a ≡ b (mod m).

  • Proof: From the definition of congruence m | (ac - bc). We can factor out the c to obtain m | c(a - b). By corollary 1, m | (a - b) and hence a ≡ b (mod m).

Lemma 11: If ac ≡ bc (mod m) and (c, m) = d, then a ≡ b (mod m/d)

  • Proof: By the definition of congruence m | (ac - bc), and thus m | c(a - b). Since (c, m) = d, then it follows that d | c, and d | m. Thus m/d | (c/d)(a - b). The greatest common divisor (m/d, c/d) = 1, hence we get that m/d | (a - b), so then a ≡ b (mod m/d).

Example 3

Show that no integer in the form of 8n + 7 is the sum of three squares.

Suppose that there is an integer k = 8n + 7, and assume k is the sum of three squares. Then k = a2 + b2 + c2 for some integers a, b, c. Thus it follows that we will assume k ≡ 7 (mod 8), or:

(16)
\begin{align} a^2 + b^2 + c^2 \equiv 7 \pmod 8 \end{align}

Note that every integer has one of 0, 1, 2, 3, 4, 5, 6, and 7 for a least residue of (mod 8), thus it follows that

02 ≡ 0 (mod 8) 12 ≡ 1 (mod 8)
22 ≡ 4 (mod 8) 32 ≡ 1 (mod 8)
42 ≡ 0 (mod 8) 52 ≡ 1 (mod 8)
62 ≡ 4 (mod 8) 72 ≡ 1 (mod 8)

Clearly it is impossibly to make any sum of 0, 1, and 4 to be congruent to 7 (mod 8). For example 1 + 1 + 4 = 6, but the statement 6 ≡ 7 (mod 8) is not valid.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License