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.