«2.5 Congruences For this section, we think of m as a ﬁxed positive integer. Deﬁnition 15. We say that a is congruent to b modulo m, and we write ...»
For this section, we think of m as a ﬁxed positive integer.
Deﬁnition 15. We say that a is congruent to b modulo m, and we write
a≡b (mod m)
if m divides (a − b).
IMPORTANT NOTE: All the following statements are equivalent:
• a ≡ b (mod m)
• a and b give the same remainder when divided by m
• a can be written as b + km for some integer k
• a can be reached from b (and vice versa) by jumping only jumps of length m • (a − b) is an element of the ideal m Switching between these diﬀerent formulations will help you solve most problems concerning congruence questions.
Theorem 12. The relation a ≡ b (mod m) is an equivalence relation on Z.
Proof. This should be obvious from the 2nd point above.
Congruence behave in many ways just like equality. This is very useful in arguments with congruences. To be precise, the following rules hold. (The proofs of these rules is not the important thing, the important thing is that you can use the rules in calculations and arguments.) Theorem 13 (Rules for congruences). If we have two congruences mod m, we may add them, multiply them, and subtract them. In other words, suppose that a≡b (mod m) and c ≡ d (mod m)
Then the following holds:
a+c ≡ b+d (mod m) ac ≡ bd (mod m) a−c ≡ b−d (mod m) Proof. Our hypothesis is that m divides (a − b) and m also divides (c − d).
Then m must divide (a − b) + (c − d) = (a + c) − (b + d), which gives the ﬁrst congruence. Similar easy arguments prove the second and third congruence.
Theorem 14 (More rules for congruences). We may multiply both sides of a congruence by an integer, and we may raise both sides of a congruence to a power. More precisely, suppose that a ≡ b (mod m). Then the following
na ≡ nb (mod m) for every integer n, and an ≡ bn (mod m) for every positive integer n.
Proof. This follows from the previous theorem. Add the congruence a ≡ b (mod m) to itself n times to get the na ≡ nb (mod m), and multiply it n times to get an ≡ bn (mod m).
Theorem 15 (Cancellation law). If ac ≡ bc (mod m) and GCD(m, c) = 1, then a ≡ b (mod m).
Proof. The ﬁrst part of the hypothesis says that m|(ac − bc), that is, m divides c(a − b). Since the second part of the hypothesis says that m has no prime factor in common with c, we can conclude that m must divide (a − b).
Let us now prove a few simple theorems, to show how congruences can be used. The important thing in these examples is not the statement of the theorem, but the method of proof, using congruences.
Theorem 16. Every odd square gives the remainder 1 when divided by 4.
Proof. (Recall that a square is an integer
which means that n is congruent to the digit sum of n, mod 3. This implies that n is divisible by 3 if and only if its digit sum is divisible by 3.
Now let us prove two important theorems about existence of solutions to certain congruences.
Theorem 18. Let a, b be two integers. Consider the congruence
This congruence is solvable (i.e. their exists an integer x satisfying the congruence) if and only if b is a multiple of GCD(a, m).
Proof. First we assume that their exists an x satisfying the congruence.
Then (b − ax) is a multiple of m. This implies
for some integer k. This implies b = ax + km, so b is a linear combination of m and a. Hence b ∈ a, m, which implies that b is a multiple of GCD(a, m).
Now we have to prove the converse. Assume that b is a multiple of GCD(a, m).
Then b ∈ a, m, so b = ax + my for some integers x and y. For this particular x, we see that b − ax is a multiple of m, so x satisﬁes the congruence of the theorem.
Theorem 19 (Chinese remainder theorem). Let a, b ∈ Z, and let m and n be positive coprime integers. Then there exists z ∈ Z such that
Proof. Since n and m are coprime, we have m, n = Z. In other words, every integer is a linear combination of m and n. Hence there are some integers x and y such that
Now let z = a − xm. This implies z = b + yn. Now it is obvious that z satisﬁes the two congruences in the theorem.
The last theorem of this section is a useful fact about primes.
Theorem 20. A prime p 3 gives remainder 1 or 5 when divided by 6.
Proof. If we divide an integer by 6, the remainder is 0, 1, 2, 3, 4, or 5.
Suppose p is prime and greater than 3. Clearly p cannot be even, so the remainder of p when divided by 6 cannot be 0, 2, or 4. Also, the remainder cannot be 3, since this would imply that p is divisible by 3, and hence not prime. Therefore the remainder must be 1 or 5.
2.5.1 Exercises For each of the statements E155 to E169, determine whether it is true or
E155 3 ≡ −3 (mod 5) E156 12 ≡ 24 (mod 24) E157 0 ≡ 0 (mod 8) E158 9 ≡ 30 (mod 7) E159 31 ≡ −26 (mod 5) E160 6 ≡ 132 (mod 12) E161 Every integer n can be written either as 2k or as 2k + 1 for some integer k.
E162 If n ≡ 3 (mod 5), then n3 ≡ 4 (mod 5).
E163 If a ≡ b (mod 16), then a ≡ b (mod 8).
E164 If a ≡ b (mod 5), then a ≡ b (mod 10).
E165 If a ≡ b (mod m), then −a ≡ −b (mod m).
E166 If x ≡ 3 (mod m), then x + 4 ≡ 7 (mod m).
E167 If a ≡ b (mod m), then a2 ≡ b3 (mod m).
E168 If 2x ≡ 6 (mod 4), then x ≡ 3 (mod 4).
E169 If 3a ≡ 3b (mod 7), then a ≡ b (mod 7).
E170 What remainders can you get when dividing a square by 3?
E171 What remainders can you get when dividing a square by 5?
E172 Is the congruence 2x ≡ 7 (mod 3) solvable? If yes, can you ﬁnd such an x?
E173 Is the congruence 8x ≡ 6 (mod 12) solvable? If yes, can you ﬁnd such an x?
E174 Is the congruence 9x ≡ 2 (mod 6) solvable? If yes, can you ﬁnd such an x?
E175 Is the congruence 3x ≡ 5 (mod 8) solvable? If yes, can you ﬁnd such an x?
E176 Is there an integer which gives the remainder 2 when divided by 5 and the remainder 3 when divided by 7? If yes, ﬁnd such an integer.
E177 Is there an integer which gives the remainder 1 when divided by 10 and the remainder 8 when divided by 9? If yes, ﬁnd such an integer.
E178 Is there an integer which gives the remainder 2 when divided by 6 and the remainder 3 when divided by 4? If yes, ﬁnd such an integer.
2.5.2 Problems P10 Find all prime numbers such that p2 + 2 is also a prime number.
P11 Let n be a positive integer. Prove that n is congruent to the alternating digit sum of n, mod 11.
P12 Prove that if p 3 is a prime, then 24|(p2 − 1).
P13 Find an integer x such that 38x ≡ 5 (mod 17).
P14 Is there a positive integer n such that
for every prime number p?
2.6 Induction proofs An important method of proof, which is useful both in number theory and in many other parts of mathematics, is the method of induction. It can often be used to prove that a certain statement holds for all positive integers n.
Let S(n) denote a statement about the integer n. For example, S(n) could
be any of the following statements:
• n is a prime number n(n+1) n • = k=1 k 2 • (52n−1 + 1) is divisible by 6 • (n2 + n + 17) is a prime number
• A set with n elements has 2n subsets
• n can be written as the sum of at most three prime numbers Consider the ﬁrst of these examples. In this case, S(2) is a true statement, while S(4) is a false statement. What do you think about the other statements? Are they true for all positive integers n, or only for some positive integers n, or perhaps false for all positive integers n?
If a statement is true for all positive integers n, one way of proving it might be by induction. The idea of an induction proof is the following: Let S(n) be the statement to be proved for all positive integers n.
1. Prove that S(1) is true (Base step)
2. Prove that S(n) implies S(n + 1) (Induction step) If we can prove both of these steps, we may conclude that S(n) is true for all positive integers n (this is called the Principle of Induction).
In most cases, the base step is the easy part and the induction step is the complicated part. However, you must never forget to do both steps, otherwise the proof is not valid! Let us now prove a few theorems to show how induction proofs work.
Theorem 21. For all positive integers n, the integer (52n−1 + 1) is divisible by 6.
Proof. We proceed by induction. The statement S(n) is the statement of the theorem.
Base step: We compute, for n = 1:
52n−1 + 1 = 6 The statement S(1) therefore says that 6 is divisible by 6, which is of course true.
Induction step: Assume that S(n) is true. The statement S(n + 1), that
we must prove, says the following:
52(n+1)−1 + 1 is divisible by 6.
Since 2(n + 1) − 1 is equal to (2n + 1), we must prove that
which implies that S(n + 1) is true.
By the Principle of Induction we now know that S(n) is true for all positive integers n.
Theorem 22. Let n be a positive integer. The sum of the ﬁrst n positive integers is equal to n(n+1).
But the right hand side of this equality is equal to (n+1)(n+2) (check this!) which means that we have proved the statement S(n + 1).
Now the Principle of Induction allows us to conclude that S(n) is true for all n.
Theorem 23. If A is a set with n elements, then A has 2n subsets.
Proof. Recall that we proved the following lemma in the lectures (we omit
this proof here, as the important point is the induction proof):
Lemma 1. Let the ﬁnite set A have one more element than the set B.
Then A has twice as many subsets as B.
Let us now the induction proof. The statement S(n) is the statement of the theorem.
Base step: The statement S(1) is true, because a set A with one element has exactly two subsets: the empty set and the set A itself.
Induction step: Assume that S(n) is true. This means that a set with n elements has 2n subsets. By the lemma we can see that a set with (n + 1) elements has 2·2n subsets, that is 2n+1 subsets. Hence the statement S(n+1) is also true.
Now the Principle of Induction allows us to conclude that S(n) is true for all positive integers n.
Let us again summarize the method of induction:
• In the base step, we prove that S(1) is true
• In the induction step, we assume that S(n) is true, and use this to prove that S(n + 1) is true 2.6.1 Exercises E179 Prove that 23n ≡ 1 (mod 7) for every positive integer n.
E180 Prove that 3n ≡ 3 (mod 6) for every positive integer n.
2.6.2 Problems P15 Try to ﬁnd a formula for the sum of the ﬁrst n odd numbers.
We will not need the above general formula (and you don’t have to remember it for the exam), but we shall need the following two special cases (which you must remember).
Corollary 1. If p is a prime number, then ϕ(p) = p − 1. If p and q are prime numbers, and n = pq, then ϕ(n) = (p − 1)(q − 1).
Proof. This follows from the general formula.
Example 34. Using the corollary, we can compute that
Proof. We consider two cases.
Case 1: p divides a.
In this case, a ≡ 0 (mod p). Hence ap ≡ 0 (mod p), so the theorem is true in this case.
Case 2: p does not divide a.
We know that φ(p) = p − 1. Since a is coprime to p, we may apply Euler’s
theorem (with n = p) to get the following congruence:
Multiplying both sides by a proves the theorem also in the second case.
Example 35. Fermat’s little theorem is of great help when dealing with
congruences mod a prime number. Consider for example the following question:
What is the remainder of 422 when divided by 7?