This document provides an overview of congruences in number theory. It defines congruences modulo m as integers a and b such that their difference is divisible by m. Congruences can be added, multiplied, and taken to powers if the modulus m is held constant. Fermat's Little Theorem states that if p is prime and a is not divisible by p, then ap-1 is congruent to 1 modulo p. Division with remainder is also discussed, where the remainder r is the smallest nonnegative integer congruent to the dividend modulo the divisor.
This document provides an overview of congruences in number theory. It defines congruences modulo m as integers a and b such that their difference is divisible by m. Congruences can be added, multiplied, and taken to powers if the modulus m is held constant. Fermat's Little Theorem states that if p is prime and a is not divisible by p, then ap-1 is congruent to 1 modulo p. Division with remainder is also discussed, where the remainder r is the smallest nonnegative integer congruent to the dividend modulo the divisor.
This document provides an overview of congruences in number theory. It defines congruences modulo m as integers a and b such that their difference is divisible by m. Congruences can be added, multiplied, and taken to powers if the modulus m is held constant. Fermat's Little Theorem states that if p is prime and a is not divisible by p, then ap-1 is congruent to 1 modulo p. Division with remainder is also discussed, where the remainder r is the smallest nonnegative integer congruent to the dividend modulo the divisor.
This document provides an overview of congruences in number theory. It defines congruences modulo m as integers a and b such that their difference is divisible by m. Congruences can be added, multiplied, and taken to powers if the modulus m is held constant. Fermat's Little Theorem states that if p is prime and a is not divisible by p, then ap-1 is congruent to 1 modulo p. Division with remainder is also discussed, where the remainder r is the smallest nonnegative integer congruent to the dividend modulo the divisor.
Math 347, Summer 2019 Number Theory II: Congruences A.J.
Hildebrand
Number Theory II: Congruences
Congruences are a simple, but extremely useful concept in number theory. The magic of congruences (“modular arithmetic”) can often turn an otherwise complex and lengthy argument into a couple of lines. This handout summarizes the basic definitions and results about congruences that you need to know.
Definition Definition: Let a, b ∈ Z, and m ∈ N. We say “a is congruent to b modulo m”, and write “a ≡ b mod m”, if m | (a − b). The integer m is called the modulus of the congruence.
Equivalent definition: By the definition of divisibility, “m | (a − b)” means that there exists k ∈ Z such that a − b = km, i.e., a = b + km. Thus, the above definition can be stated as follows. This version is particularly suited for proofs involving congruences.
Definition: Let a, b ∈ Z, and m ∈ N. Then “a ≡ b mod m” means that a = b + km
for some k ∈ Z.
• Examples: 22 ≡ 4 mod 6 (since 6 | (22 − 4)), 4 ≡ −2 mod 6 (since 6 | 4 − (−2)), 5 ≡ 1 mod 2
(since 2 | (1 − 5)).
• Special case: Congruences modulo 2: n ≡ 0 mod 2 means that n = 2k for some k ∈ Z. But the integers of the form n = 2k are exactly the even integers. Similarly, the integers satisfying n ≡ 1 mod 2 are those of the form n = 1 + 2k for some k ∈ Z, i.e., the odd integers.
• Special case: Congruences to 0: By the above definition, “a ≡ 0 mod m” means m | (a − 0),
i.e., it is equivalent to the divisibility relation m | a.
• Notes:
• Congruences are only defined for integers, and the modulus m must be a natural number. For example, a ≡ 1/2 mod 2 is not defined since 1/2 is not an integer; similarly, a ≡ b mod 0 is not defined since 0 is not a natural number. • The modulus m is an essential part of the definition. Make sure to always specify the modulus; saying “a is congruent to b”, or writing “a ≡ b”, without specifying a modulus, makes no sense.
Properties What makes congruences so useful is that, to a large extent, they can be manipulated like ordinary equations. Congruences to the same modulus can be added, multiplied, and taken to a fixed positive integral power; i.e., for any a, b, c, d ∈ Z and m ∈ N we have:
• Adding/subtracting congruences: If a ≡ b mod m and c ≡ d mod m, then a + c ≡ b + d
mod m. and a − c ≡ b − d mod m.
• Multiplying congruences: If a ≡ b mod m and c ≡ d mod m, then ac ≡ bd mod m.
• Taking congruences to the k-th power: If a ≡ b mod m and k ∈ N, then ak ≡ bk mod m.
• Chaining congruences together: If a ≡ b mod m and b ≡ c mod m, then a ≡ c mod m.
1 Math 347, Summer 2019 Number Theory II: Congruences A.J. Hildebrand
• Proofs. Proving the above congruence properties is an instructive exercise in applying proof techniques you’ve learned earlier in this course, and you should be able to carry out such proofs. Some examples will be given in class or on worksheets; others will be assigned as homework.
• Notes.
• Congruences to different moduli can NOT be added, multiplied, etc. In the above properties, the modulus m must be the same at each occurrence. • Congruences can NOT be divided. An analogous property involving division of congruences does not exist. This is because congruences are only defined for integers, and dividing congru- ences would introduce rational numbers. • Congruences can NOT be exponentiated. It is not true that a ≡ b mod m and c ≡ d mod m implies ac ≡ bd mod m. (However, you can take each side of the congruence to the same exponent k: a ≡ b mod m implies ak ≡ bk mod m.)
Famous Congruence: Fermat’s Little Theorem
Fermat’s Little Theorem: Let p be a prime and a ∈ N such that p - a. Then ap−1 ≡ 1 mod p.
• Example: The number 2017 is prime, so by Fermat’s Little theorem, we have a2016 ≡ 1 mod 2017 for any natural number a that is not divisible by 2017. In particular, it follows that each of the numbers 22016 − 1, 32016 − 1, . . . , 20162016 − 1 is divisible by 2017.
• Note: The modulus, p, in this theorem must be a prime. For composite moduli the above congru- ence does, in general, not hold.
Division with Remainder
The familiar process of division with remainder is made precise in the following theorem.
Theorem (Division with Remainder (Division Algorithm)). Let a ∈ Z and
b ∈ N. Then there exist unique integers q (“quotient”) and r (“remainder”) such that a = qb + r and 0 ≤ r < b.
• Example: If a = 16 and b = 5, then 16 = 3 · 5 + 1, so in this case q = 3 and r = 1. By the theorem,
this is the only such representation with a remainder satisfying 0 ≤ r < 5.
• Congruences and remainders. The remainder, r, in the division algorithm is the smallest nonnegative integer that is congruent to a modulo q.
Further Resources In the text the above definitions and theorems can be found in Chapter 6: Congruences: Definition 7.15, p. 142. Addition/Multiplication Properties: Lemma 7.19, p. 145. Fermat’s Little Theorem: Theorem 7.36, p. 148. Division with Remainder: Proposition 6.14, p. 126.
