Congruences

Let’s keep the 17 counters and packets of 5. Each outlined blue packet below contains five counters. The dashed gold packet contains only the two left over. It is not another complete packet of five.

The 5 tells us the size of a full group; we call it the divisor here. The 3 or 4 counts full groups and is called the quotient. The 2 left over is the remainder. A remainder must be at least zero and smaller than the group size. If five or more counters remained, we could make another complete packet, so the grouping would not yet be finished.

We use letters so that one sentence can cover different totals. Let $a$ be an integer: one of …, $-3, -2, -1, 0, 1, 2, 3$, …, without a fractional part. We write $a \in \mathbb Z$ to say “$a$ is an integer”. Let $m$ be our fixed positive group size, at least 2. Then $q$ is an integer quotient and $r$ is the remainder:

The letters next to one another in $qm$ mean multiplication: $q \times m$. Negative totals cannot be pictured as physical packets of counters. A number line lets us keep the same equation: choose a multiple $qm$ at or to the left of $a$, then move $r$ units to the right. For example, $-1 = (-1) \times 5 + 4$. We start at $-5$ and move four units right to $-1$. The quotient is $-1$, but the remainder is 4, not $-1$.

The picture found a remainder for a few integers. Before building rules on it, we need two guarantees: every integer has such a description, and two different remainders cannot both be correct. We prove those separately.

First, find a description for every integer

If $a$ is nonnegative, start at $a$ and repeatedly subtract $m$ while at least $m$ remains. Each subtraction removes a full group. The remainder falls by at least 1 each time and never becomes negative, so this process must stop: there are only $a + 1$ nonnegative integers from 0 to $a$. If we subtracted $m$ exactly $q$ times, the final number $r$ satisfies $a = qm + r$ and $0 \le r < m$.

If $a$ is negative, write $a = -n$ with $n$ positive, and apply the process to $n$. Suppose $n = qm + r$. When $r = 0$, changing the sign gives $a = (-q)m + 0$. When $r > 0$, $a$ initially becomes $-qm - r$. To make the remainder positive, subtract one more full $m$ from the multiple and give it back in the remainder:

Expanding the right side gives $-qm - m + m - r = -qm - r$, so the number has not changed. Since $0 < r < m$, subtracting $r$ from $m$ gives $0 < m - r < m$. Thus the new remainder is allowed. These two cases cover every negative integer, so existence is proved.

Next, rule out two different answers

Suppose someone gives two descriptions $a = qm + r$ and $a = sm + t$, with both $r$ and $t$ between 0 and $m - 1$. Subtract the second description from the first. The $a$ values cancel because they are the same integer:

Because $r$ and $t$ are both in that range, their difference lies strictly between $-m$ and $m$. But an integer multiple of $m$ is either zero or has size at least $m$: a nonzero integer multiplier has size at least 1. Therefore the only possible multiple here is zero. So $q - s = 0$, hence $q = s$; then $t - r = 0$, hence $t = r$. We have proved that the quotient and allowed remainder are unique.

Return to 17 and 22. Their difference is $22 - 17 = 5$, exactly one full packet. Adding or removing full packets changes the total but not the remainder. We want a notation for that precise agreement. We write $a \equiv b \pmod{m}$, read “$a$ is congruent to $b$ modulo $m$”, to mean that $a$ and $b$ have the same remainder on division by $m$. The fixed number $m$ is called the modulus.

All integers sharing one remainder form one remainder class. We can name that whole class using any one of its members, called a representative. For example, the class containing 2 modulo 5 contains …, $-8, -3, 2, 7, 12, 17, 22$, … because each is 5 times an integer plus 2. Using the representative 2 does not mean the class contains only that one integer.

The $\equiv$ sign here does not mean the integers are equal, nor that they are approximately equal. It means exactly that their remainders agree for the stated modulus. The modulus cannot be omitted from the reasoning: 17 and 22 have the same remainder modulo 5, but modulo 3 their remainders are 2 and 1.

There is another description that will be easier to calculate with. The notation $m \mid n$ means “$m$ divides $n$”: $n$ equals $m$ times an integer. It is not a division sign. We now prove, in both directions, that having the same remainder is equivalent to the difference being a multiple of $m$.

First suppose the remainders agree. Write $a = qm + r$ and $b = sm + r$. Subtracting gives $a - b = qm + r - sm - r = m(q - s)$. Because $q - s$ is an integer, the difference is an integer multiple of $m$.

Conversely, suppose $a - b = mk$ for an integer $k$. Write the allowed remainders separately: $a = qm + r, b = sm + t$. Substitute these expressions, and move the multiple of $m$ to the other side:

Again $r - t$ lies strictly between $-m$ and $m$. Again it is a multiple of $m$. The argument in the uniqueness proof forces it to be zero, so $r = t$. Both directions are now proved. The double arrow means that either statement implies the other.

This also explains three small moves we will use. Every number is congruent to itself because $a - a = m \times 0$. We may reverse a congruence because $a - b = mk$ gives $b - a = m(-k)$. We may join two congruences with the same modulus: if $a - b = mk$ and $b - c = mh$, adding gives $a - c = m(k + h)$. Thus $a \equiv b$ and $b \equiv c$ imply $a \equiv c$, always with that same modulus.

If we know only remainders, can we still add or multiply? Let $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$. The difference description we just proved lets us write $a = b + mk$ and $c = d + mh$, where $k$ and $h$ are integers. These equations say exactly how much information was removed: whole multiples of $m$.

Addition and subtraction

The quantities $k + h$ and $k - h$ are integers. Therefore both displayed differences are multiples of $m$. By our proved description, $a + c \equiv b + d \pmod{m}$, and $a - c \equiv b - d \pmod{m}$. In particular, adding the same integer to both sides is allowed: that integer is congruent to itself.

Multiplication

For multiplication, we must include every term, including the product of the two removed multiples. Expanding the brackets shows these terms; gathering the ones that contain $m$ shows that their sum is a multiple of $m$:

The bracket contains only sums and products of integers, so it is an integer. Hence $ac \equiv bd \pmod{m}$. This is why we may reduce the factors first. For example, modulo $5, 17 \equiv 2$ because $17 = 3 \times 5 + 2$, and $22 \equiv 2$ because $22 = 4 \times 5 + 2$. Thus $17 \times 22 \equiv 2 \times 2 = 4 \pmod{5}$. Checking the full product gives $374 = 74 \times 5 + 4$. The smaller calculation kept exactly the remainder we wanted.

Positive integer powers

The notation $a^{n}$, for a positive integer $n$, means $n$ copies of a multiplied together. If $a \equiv b$, the multiplication rule gives $a^{2} \equiv b^{2}$. Applying it to $a^{2} \equiv b^{2}$ and $a \equiv b$ gives $a^{3} \equiv b^{3}$. Why does this cover any positive $n$, rather than only two examples? The starting case $n = 1$ is our given congruence. Whenever the claim holds at $n$, multiplying that congruence by $a \equiv b$ proves it at $n + 1$. Starting at 1 and taking this step repeatedly reaches every positive integer $n$. This start-and-next-step argument is called induction.

Consider $2x \equiv 2 \pmod{6}$. The ordinary equation $2x = 2$ has only $x = 1$. But our new statement is different: it asks for $2x - 2$ to be a multiple of 6. Both $x = 1$ and $x = 4$ work, since $2 \times 1 - 2 = 0 = 6 \times 0$, and $2 \times 4 - 2 = 6 = 6 \times 1$. Yet 1 and 4 are not congruent modulo 6, because $4 - 1 = 3$ is not a multiple of 6.

In the initial table, the input remainders 1 and 4 both become 2 after multiplying by 2 modulo 6. Once those two inputs have merged, the output alone cannot tell us which one we started with. This is the information that an unjustified cancellation loses.

We can still divide a genuine equality. Write $2x - 2 = 6k$, where $k$ is an integer. Divide every term of this equality by 2: $x - 1 = 3k$. This says $x \equiv 1 \pmod{3}$, not modulo 6. Reversing the steps shows that every such $x$ works. Thus all integer solutions are $x = 1 + 3k$: …, $-5, -2, 1, 4, 7, 10$, …. The modulus has changed together with the cancelled factor.

When can we keep the old modulus, and how should we change it otherwise? To answer completely, we need a way to make the number 1—or a larger common divisor—out of integer multiples. We will build that tool next, rather than assume it.

Take positive integers $A$ and $M$. A positive common divisor is a positive integer dividing both. There is always at least one, namely 1. There are only finitely many: if $A = gh$ with $g$ and $h$ positive integers, then $h \ge 1$, so $g \le A$. Thus every positive divisor lies in the finite list 1, 2, …, A. The largest is called the greatest common divisor, written $\gcd(A, M)$. We will show both how to find it and why it is an integer combination $uA + vM$.

Replacing a pair without changing its common divisors

Divide $A$ by $M$ and write $A = qM + r$. If a positive integer $g$ divides $A$ and $M$, write $A = gu$ and $M = gv$. Then $r = A - qM = gu - qgv = g(u - qv)$, so $g$ divides $r$. In the other direction, if $M = gv$ and $r = gw$, then $A = qM + r = qgv + gw = g(qv + w)$, so $g$ divides $A$. Therefore the pair $(A, M)$ and the pair $(M, r)$ have exactly the same positive common divisors.

Repeat this replacement while the remainder is nonzero. Each new remainder is a nonnegative integer smaller than the preceding divisor, so the positive remainders cannot decrease forever. Eventually we reach a pair $(d, 0)$. Every positive divisor of $d$ divides 0 too, since 0 equals that divisor times 0. The largest common divisor of this final pair is $d$ itself. Because each replacement preserved all common divisors, $d$ is also $\gcd(A, M)$. This process is the Euclidean algorithm.

Keep track of how each remainder was made

At the start, $A = 1A + 0M$ and $M = 0A + 1M$ are already integer combinations of $A$ and $M$. Suppose two current numbers are $uA + vM$ and $sA + tM$. Subtracting $q$ times the second from the first gives $(u - qs)A + (v - qt)M$, still with integer coefficients. Thus every new remainder is such a combination. We start with this property and preserve it at every step, so the final retained nonzero number $d$ also has it, even if it was one of the starting numbers:

This is Bézout’s identity. The coefficients $u$ and $v$ may be negative; “integer combination” allows subtraction as well as addition. We have proved its existence, rather than assuming that suitable coefficients can always be guessed.

Work the numbers: combine 7 and 12 to make 1

For 7 and 12, start by dividing the larger number by the smaller. At each following line, use the preceding divisor and remainder:

The last nonzero remainder is 1, so $\gcd (7, 12) = 1$. To write this 1 using the original numbers, read the earlier equations backwards. First isolate $1 = 5 - 2 \times 2$. Replace each 2 with $7 - 5$, then each 5 with $12 - 7$. We keep all the intermediate expansions:

Checking gives $36 - 35 = 1$. We have not divided by 7. We have found an integer multiplier $-5$ of 7 whose result differs from 1 by a multiple of 12. That is exactly the sort of replacement for division we were looking for.

We first handle the case where the multiplier $c$ and modulus $m$ have greatest common divisor 1. Such two positive integers are called coprime; this says only that their sole positive common divisor is 1. Bézout gives integers $u$ and $v$ with $uc + vm = 1$. Suppose $cA \equiv cB \pmod{m}$. Write $c(A - B) = mk$, then multiply the Bézout equation by $A - B$:

The bracket is an integer, so $m$ divides $A - B$. Hence $A \equiv B \pmod{m}$. We chose the Bézout equation because its left side can become $A - B$, while its right side uses the known multiple $c(A - B)$. This proves cancellation when the multiplier and modulus are coprime.

What changes when there is a common divisor?

Let $d = \gcd(c, m)$, with $c$ positive. Divide both by $d$ and call the results $c' = c/d$ and $m' = m/d$. These are integers. They are coprime: if a positive $h$ divided both, then $dh$ would divide both $c$ and $m$; since $d$ is the greatest common divisor, $dh \le d$, and division by the positive $d$ gives $h \le 1$. Thus $h$ can only be 1.

To prove the forward direction, write $c(A - B) = mk$ and divide this equality by $d$. It becomes $c'(A - B) = m'k$. Since $c'$ and $m'$ are coprime, the cancellation argument just proved gives $m' \mid (A - B)$. Conversely, if $A - B = m'j$ for an integer $j$, multiply by $c = dc'$: $c(A - B) = dc'm'j = mc'j$. This is a multiple of $m$, so the original congruence follows. Both directions hold.

There is one boundary case to explain. If $m/d = 1$, division by 1 always has remainder zero: $n = n \times 1 + 0$ for every integer $n$. Thus all integers are congruent modulo 1, and the reduced statement imposes no restriction. The proof still works, since 1 divides every integer. We began with $m \ge 2$, but cancellation can lead to this case.

Undo multiplication with another multiplication

In ordinary arithmetic, multiplying by $1/c$ undoes multiplying by $c$. Here we want an integer $u$ with $cu \equiv 1 \pmod{m}$. Such a $u$ is called a multiplicative inverse of $c$ modulo $m$. It is an integer remainder-class inverse, not the ordinary fraction $1/c$. If $cx \equiv b$, multiplying by $u$ gives $ucx \equiv ub$; since $uc \equiv 1$, another use of the multiplication rule gives $x \equiv ub$.

An inverse exists exactly when $\gcd (c, m) = 1$. If the $\gcd$ is 1, Bézout gives $uc + vm = 1$, so $uc - 1 = -vm$, proving $uc \equiv 1$. Conversely, if $uc \equiv 1$, then $uc - 1 = mk$, so $1 = uc - mk$. Every positive common divisor of $c$ and $m$ must divide this combination, hence must divide 1. If $1 = gh$ with $g$ and $h$ positive integers, $h \ge 1$ forces $g \le 1$; hence the only positive divisor of 1 is 1. So the $\gcd$ is 1. That proves both the existence condition and its necessity.

Our worked identity $1 = 3 \times 12 - 5 \times 7$ says that $-5$ is an inverse of 7 modulo 12. Adding 12 gives the representative 7. Check it: $7 \times 7 = 49 = 4 \times 12 + 1$. An inverse is not a unique integer—adding a multiple of 12 keeps the property—but it is a unique remainder modulo 12. Indeed, if $cu \equiv cv \equiv 1$ and $\gcd (c, m) = 1$, the proved cancellation gives $u \equiv v \pmod{m}$.

We can now solve $ax \equiv b \pmod{m}$, where $a$ is a positive integer, $b$ is any integer, $m \ge 2$, and $x$ is the unknown integer. “Linear” means $x$ appears multiplied by $a$, rather than squared or raised to another power. We need to answer three questions: does any solution exist, how do we get one, and how do we know we have all of them?

First decide whether a solution is possible

Put $d = \gcd(a, m)$. If $x$ is a solution, there is an integer $k$ with $ax - b = mk$. Move terms to get $b = ax - mk$. Since $a = d(a/d)$ and $m = d(m/d)$, this becomes $b = d((a/d)x - (m/d)k)$. Everything in the bracket is an integer, so $d$ must divide $b$. For example, $6x \equiv 4 \pmod{9}$ is impossible: every $6x - 9k$ is a multiple of 3, but $4 = 1 \times 3 + 1$ is not.

Now suppose $d$ does divide $b$, so $b = dh$ with integer $h$. Bézout gives $ua + vm = d$. Multiply that whole equality by $h$: $a(uh) + m(vh) = dh = b$. Rearranging gives $a(uh) - b = -m(vh)$. Thus $x_{0} = uh$ is a solution, because its difference from $b$ after multiplying by $a$ is a multiple of $m$. We have proved both directions of the existence criterion:

Then find every solution, without losing or adding any

Suppose $x_{0}$ is one solution and $x$ is any other solution. Subtract $ax_{0} \equiv b$ from $ax \equiv b$. The subtraction rule gives $a(x - x_{0}) \equiv 0 \pmod{m}$. Apply the corrected cancellation with $d = \gcd (a, m)$: $x - x_{0} \equiv 0 \pmod{m/d}$. This means $x - x_{0} = (m/d)t$ for an integer $t$. Therefore every solution must have the following form:

We still must check that every integer of this form really works. Substitute it: $ax - b = a(x_{0} + (m/d)t) - b = (ax_{0} - b) + m(a/d)t$. The first term is a multiple of $m$ because $x_{0}$ is a solution; the second is a multiple because $a/d$ and $t$ are integers. Their sum is a multiple of $m$. So this formula gives all solutions and only solutions.

Why there are $d$ different answer classes modulo $m$

The integer solutions are infinite, but their remainders modulo $m$ are not. In the formula above, use $t = 0, 1$, …, $d - 1$. These $d$ answers represent distinct remainders. To see this, if the answers for $t = i$ and $t = j$ were congruent modulo $m$, their difference $(m/d)(i - j)$ would equal $mk$. Dividing the equality by the positive $m/d$ gives $i - j = dk$. But $-d < i - j < d$, so the uniqueness argument forces $i = j$.

These classes also include every other integer $t$. Divide $t$ by $d$, writing $t = dq + j$ with $0 \le j < d$; when $d = 1$, the remainder is 0. Then $x_{0} + (m/d)t = x_{0} + (m/d)j + mq$. The final term $mq$ does not change the remainder modulo $m$, so the answer is in the class already represented by $j$. There are exactly $d$ classes whenever solutions exist.

A complete example: $4x \equiv 2 \pmod{6}$

The divisions $6 = 1 \times 4 + 2$ and $4 = 2 \times 2 + 0$ give $d = 2$. Since 2 divides the right side 2, solutions exist. Back-substitution gives $2 = 6 - 4 = (-1) \times 4 + 1 \times 6$. Here $h = b/d = 2/2 = 1$, so $x_{0} = (-1) \times 1 = -1$ is one solution. The spacing is $m/d = 6/2 = 3$, hence every solution is $x = -1 + 3t$.

We may start the same list at 2, because $-1 + 3t = 2 + 3(t - 1)$, and $t - 1$ still runs through all integers. Writing $x = 2 + 3k$ makes the two representatives modulo 6 easy to read: 2 and 5. Direct substitution checks the whole family, not just those two numbers:

Every integer $k$ makes this a multiple of 6. Conversely, the argument above proved every solution has this form. This is the two-way check a complete solution needs.

Let’s return to the large multiplication in the introduction. A nonnegative decimal integer $N$ has a last digit $r$ between 0 and 9. The other digits count complete tens, so $N = 10q + r$. Thus its last digit is exactly its remainder modulo 10. We need the remainder of $7^{2026}$, not its enormous full value.

Four rows alone would not prove that the pattern always repeats. The reason it repeats is the multiplication rule: multiplying any power $7^{n}$ by $7^{4}$ multiplies its remainder by 1, so $7^{n+4} \equiv 7^{n} \pmod{10}$. The identity $7^{n+4} = 7^{n} \times 7^{4}$ comes from putting together $n$ factors of 7 and four more factors.

Now divide the number of factors by four: $2026 = 4 \times 506 + 2$. We can arrange the 2026 factors into 506 blocks of four and two remaining factors. Each block of four has remainder 1, and the last two factors have remainder 9. Therefore:

The last digit is 9. Notice that we reduced the exponent using a proved cycle length, 4, not by replacing 2026 with its remainder modulo 10. The modulus for the values and the length of a repeating pattern are different numbers.

Why the digit-sum test for divisibility by 9 works

A four-digit number with digits $a$, $b$, $c$ and $d$ means $N = 1000a + 100b + 10c + d$. This is the meaning of decimal place value: $a$ counts thousands, $b$ hundreds, $c$ tens, and $d$ units. Since $10 = 1 \times 9 + 1$, we have $10 \equiv 1 \pmod{9}$. The power rule gives $100 = 10^{2} \equiv 1^{2} = 1$ and $1000 = 10^{3} \equiv 1^{3} = 1$. The multiplication and addition rules now give:

For a number with more or fewer digits, each additional place has weight 10 to a positive integer power, and that weight again has remainder 1. The units place already has weight 1. Repeated addition therefore proves the same conclusion for any finite number of digits. A number is divisible by 9 exactly when its remainder is zero, so it is divisible by 9 exactly when its digit sum is divisible by 9.

For 2349, the digit sum is $2 + 3 + 4 + 9 = 18 = 2 \times 9$, so its remainder is zero; direct division confirms $2349 = 261 \times 9$. For 2026, the sum is $2 + 0 + 2 + 6 = 10 = 1 \times 9 + 1$, so its remainder is 1; indeed $2026 = 225 \times 9 + 1$. The rule now has a reason, and it tells us the remainder as well as answering yes or no.

Congruences can also show that a proposed integer equation has no answer. Consider $x^{2} = 4y + 2$ with integer $x$ and $y$. Instead of trying more and more values, ask what remainder each side could have modulo 4. Every integer $x$ has exactly one remainder among 0, 1, 2 and 3. If $x \equiv r \pmod{4}$, the proved multiplication rule gives $x^{2} \equiv r^{2}$. We can therefore cover every integer by these four cases:

Thus an integer square has remainder 0 or 1 modulo 4, never 2. The right side $4y + 2$ always has remainder 2, including when $y$ is negative, because $y$ is an integer quotient and $0 \le 2 < 4$. Equal integers must have the same unique remainder. Our two sides cannot, so no integer pair $(x, y)$ satisfies the equation.