As with so many concepts we will see, congruence is simple, perhaps familiar to you, yet enormously useful and powerful in the study of number theory. If $n$ is a positive integer, we say the integers $a$ and $b$ are congruent modulo $n$, and write $a\equiv b\pmod n$, if they have the same remainder on division by $n$. (By remainder, of course, we mean the unique number $r$ defined by the Division Algorithm.) This notation, and much of the elementary theory of congruence, is due to the famous German mathematician, Carl Friedrich Gauss—certainly the outstanding mathematician of his time, and perhaps the greatest mathematician of all time.
Example 3.1.1 $\{…,-6,1,8,15,…\}$ are all congruent modulo 7 because their remainders on division by 7 equal 1. $\{…,-4,4,12,20,…\}$ are all congruent modulo 8 since their remainders on division by 8 equal 4. $\square$
Here is a wonderfully useful result.
Proof. We break the proof into two parts:
(only if) If $a\equiv b\pmod n$, then there are integers $q$, $q'$ and $r$, with $a=qn+r$ and $b=q'n+r$. So $a-b=(qn+r)-(q'n+r)=(q-q')n$, which means $n|a-b$.
(if) Suppose $n|a-b$, so there is an $x$ with $a-b=xn$, that is, $a=b+xn$. Suppose $r$ is the remainder on dividing $n$ into $b$; we need to show that $r$ is also the remainder on dividing $n$ into $a$. Since $b=qn+r$, we have $a=b+xn=qn+r+xn=(q+x)n+r$. Thus, when $n$ is divided into $a$, the remainder is $r$ as desired.$\qed$
If the value of $n$ is clear from the context, we often write simply $a\equiv b$. Congruence of integers shares many properties with equality; we list a few here.
Theorem 3.1.3 Congruence modulo $n$ satisfies the following:
1. $a\equiv a$ for any $a$;
2. $a\equiv b$ implies $b\equiv a$;
3. $a\equiv b$ and $b\equiv c$ implies $a\equiv c$;
4. $a\equiv 0$ iff $n|a$;
5. $a\equiv b$ and $c\equiv d$ implies $a+c \equiv b+d$;
6. $a\equiv b$ and $c\equiv d$ implies $a-c \equiv b-d$;
7. $a\equiv b$ and $c\equiv d$ implies $ac \equiv bd$;
8. $a\equiv b$ implies $a^j\equiv b^j$ for each integer $j\ge 1$.
Proof. Parts 1, 2, 3 and 4 are clear by the definition of congruence. (Aren't they? Check!) We'll prove parts 6 and 8, leaving parts 5 and 7 as exercises. Part 6: By hypothesis $n|a-b$ and $n|c-d$, so we have $n|(a-b)-(c-d)$. Rearranging the terms, this means $n|(a-c)-(b-d)$, so $a-c\equiv b-d$. Part 8: This follows from part 7, but it is easy to prove it directly: since $a\equiv b$, $n|a-b$. Therefore, $$ n|(a-b)(a^{j-1}+a^{j-2}b+…+ab^{j-2}+b^{j-1})=a^j-b^j, $$ so $a^j\equiv b^j$. Be sure you notice how often we have used lemma 3.1.2.$\qed$
Parts 5–8 can be summarized by saying that in any expression involving $+,-,\cdot$ and positive integer exponents (that is, any "polynomial''), if individual terms are replaced by other terms that are congruent to them modulo $n$, the resulting expression is congruent to the original.
Example 3.1.4 Any perfect square is of the form $4x$ or $4x+1$, that is, if you divide $4$ into a perfect square, the remainder is never $2$ or $3$: Suppose $k^2$ is some perfect square. Then $k$ is congruent modulo 4 to exactly one of $0,1,2$ or $3$, so $k^2$ is congruent to $0^2=0$, $1^2=1$, $2^2\equiv 0$ or $3^2\equiv 1$, so it is never congruent to $2$ or $3$. $\square$
Example 3.1.5 Find all integers $x$ such that $3x-5$ is divisible by $11$. Put in somewhat more familiar terms, we are trying to solve the congruence $3x\equiv 5\pmod {{11}}$ for $x$, much as we might try to solve an equation for an unknown. Let's assume $3x\equiv 5$ and see what that tells us about $x$. Since $4\cdot 3=12\equiv 1$, $$ 3x\equiv 5 \implies 4\cdot 3 x\equiv 4\cdot 5\implies 12x\equiv 20 \implies x\equiv 9. $$ So if $3x\equiv 5$ then $x\equiv 9$, or $x\in\{…, -13, -2, 9, 20, …\}$. We also want to know that in fact all of these values are solutions, that is, if $x\equiv 9$ then $3x\equiv 5$. This is easy. (Right?) $\square$
Example 3.1.6 You are probably familiar with the old rule ("casting out nines'') that an integer is divisible by 9 if and only if the sum of its digits is divisible by 9. Here is a proof. Suppose $x$ is some positive integer and when we write it in decimal form it looks like $d_kd_{k-1}… d_1d_0$ (where each $d_i$ is between 0 and 9). This means $$ x=d_k\cdot 10^k+d_{k-1}\cdot 10^{k-1}+…+d_1\cdot 10 +d_0. $$ Observe that $10\equiv 1 \pmod 9$ and so $10^i\equiv 1^i=1\pmod 9$ for every $i$. This implies that $$ x\equiv d_k+d_{k-1}+… +d_1+d_0 \pmod 9. $$ This actually proves more than we need. It says that an integer and the sum of its digits are congruent modulo 9. In particular, one is congruent to 0 (that is, divisible by 9) if and only if the other is. $\square$
Carl Friedrich Gauss. Gauss (1777–1855) was an infant prodigy and arguably the greatest mathematician of all time (if such rankings mean anything; certainly he would be in almost everyone's list of the top five mathematicians, as measured by talent, accomplishment and influence). Perhaps the most famous story about Gauss relates his triumph over busywork. As Carl Boyer tells the story: "One day, in order to keep the class occupied, the teacher had the students add up all the numbers from one to a hundred, with instructions that each should place his slate on a table as soon as he had completed the task. Almost immediately Carl placed his slate on the table, saying, `There it is;' the teacher looked at him scornfully while the others worked diligently. When the instructor finally looked at the results, the slate of Gauss was the only one to have the correct answer, 5050, with no further calculation. The ten-year-old boy evidently had computed mentally the sum of the arithmetic progression $1+2+\cdots+100$, presumably through the formula $m(m+1)/2$.''
By the time Gauss was about 17, he had devised and justified the method of least squares, but had not decided whether to become a mathematician or a philologist. Just short of his nineteenth birthday, he chose mathematics, when he succeeded in constructing (under the ancient restriction to compass and straightedge) a seventeen-sided regular polygon, the first polygon with a prime number of sides to be constructed in over 2000 years; previously, only the equilateral triangle and the regular pentagon had been constructed. Gauss later proved precisely which regular polygons can be constructed. (The answer is somewhat unsatisfying, however. He proved that the regular polygons that can be constructed have $2^m p_1p_2\cdots p_r$ sides, for any $m\ge 0$ and distinct Fermat primes $p_i$, that is, prime numbers having the form $2^{2^n}+1$ for some $n$. Unfortunately, it is not known whether there are an infinite number of Fermat primes.)
Gauss published relatively little of his work, but from 1796 to 1814 kept a small diary, just nineteen pages long and containing 146 brief statements. This diary remained unknown until 1898. It establishes in large part the breadth of his genius and his priority in many discoveries. Quoting Boyer again: "The unpublished memoranda of Gauss hung like a sword of Damocles over mathematics of the first half of the nineteenth century. When an important new development was announced by others, it frequently turned out that Gauss had had the idea earlier, but had permitted it to go unpublished.''
The range of Gauss's contributions is truly stunning, including some deep and still standard results such as the Quadratic Reciprocity Theorem and the Fundamental Theorem of Algebra. He devoted much of his later life to astronomy and statistics, and made significant contributions in many other fields as well. His name is attached to many mathematical objects, methods and theorems; students of physics may know him best as the namesake of the standard unit of magnetic intensity, the gauss.
The information here is taken from A History of Mathematics, by Carl Boyer, New York: John Wiley & Sons, 1968.
Exercises 3.1
Ex 3.1.1 For the given values of $n$ and $a$, find the number $b\in \{0,1,… , n-1\}$ for which $a\equiv b\pmod n.$
a) $n=7$, $a=30$
b) $n=9$, $a=69$
c) $n=2$, $a=123{,}472{,}461$
d) $n=6$, $a=-60$
e) $n=11$, $a=-63$
f) $n=17$, $a=-38$
Ex 3.1.2 If $a=nq+r$, it is not necessarily the case that $r$ is the remainder on dividing $a$ by $n$; for example, $20=6\cdot2+8$, but $8$ is certainly not the remainder when we divide $20$ by $6$. In lemma 3.1.2 we showed that $a=(q+x)n+r$ and concluded from this that the remainder on dividing $a$ by $n$ is $r$. Explain why this conclusion is justified.
Ex 3.1.3 Prove parts (5) and (7) in theorem 3.1.3. (For part 7, you might want to prove $ac\equiv bc\equiv bd$.)
Ex 3.1.4 Prove part (8) from part (7) in theorem 3.1.3, by induction.
Ex 3.1.5 What digits can appear in the 1's place of a perfect square?
Ex 3.1.6 Prove that $x\equiv 9 \pmod{11}$ iff $3x\equiv 5\pmod{11}$.
Ex 3.1.7 Find all $x$ such that $7x+3$ is divisible by $9$.
Ex 3.1.8 Suppose $n$ and $m$ are positive integers. Show that $$ ma\equiv mb \pmod {{mn}}\quad\iff\quad a\equiv b\pmod n. $$ (See exercise 5 of section 2.2.)
Ex 3.1.9 State and prove a result similar to example 3.1.6 regarding divisibility by $11$.
Ex 3.1.10 Prove that for any integer $x$, $x^3-x$ is divisible by $6$.
Ex 3.1.11 Find a rule, similar to example 3.1.6, that determines when a three-digit number is divisible by 7, and prove that it works.
Ex 3.1.12 Find the remainder when 111111110888888895 is divided by 9.