Skip to content
Topos Uranos
English

Congruences and modular arithmetic

Summary

This lesson turns the classification of the integers by their remainder into a calculus. It defines congruence modulo nn, proves that it amounts to leaving the same remainder, that it is an equivalence relation and that it respects addition, multiplication and powers, and builds with its classes the set Zn\mathbb{Z}_n of remainders, with its addition and multiplication tables. With Bézout’s identity it decides which remainders have an inverse and solves linear congruences completely; it proves the Chinese remainder theorem and Fermat’s little theorem, rereads the divisibility tests as congruences, and applies all this to check digits, to the calendar and to the RSA cryptosystem, whose correctness is proved.

Learning objectives

  1. Prove that congruence modulo nn is an equivalence relation compatible with addition, multiplication and powers, and use it to compute remainders of large numbers.
  2. Build the addition and multiplication tables of Zn\mathbb{Z}_n and decide, by means of the greatest common divisor, which remainders have an inverse.
  3. Decide whether a linear congruence has a solution, compute how many solutions it has modulo nn and find them all.
  4. Solve systems of congruences with coprime moduli by means of the Chinese remainder theorem, constructing the solution and proving its uniqueness.
  5. Prove Fermat’s little theorem and apply it to remainders of powers, to divisibilities that hold for every integer and to the correctness of the RSA cryptosystem.
  6. Analyze which errors a check digit detects and compute days of the week by means of congruences.

The congruence relation

If today is Monday, in 1515 days it will be Tuesday, and in 10001000 days it will be Sunday: to know this there is no need to count the days one by one, because the remainder of dividing the number of days by 77 suffices. In the same way, 55 hours after 99 o’clock it is 22 o’clock on a clock with 1212 hours, and the last digit of a product depends only on the last digits of the factors. In all three cases one computes with remainders and forgets the quotient. The lesson on divisibility and division with remainder distributed the integers into classes according to the remainder they leave when divided by a natural number, and proved that the remainder of a sum, of a product and of a power depends only on the remainders of the data. This lesson gives those observations a language of their own, that of congruences, which Gauss introduced in 1801 in his Disquisitiones Arithmeticae, and turns it into an instrument of computation. As in that lesson, the integers are used in advance, with the rules of their arithmetic and of their order that are founded in the lesson on the integers.

Definition (congruence). Let nn be a natural number. Two integers aa and bb are congruent modulo nn if nn divides their difference a−ba - b. One writes a≡b(modn)a \equiv b \pmod{n} and reads “aa is congruent to bb modulo nn”; the natural number nn is called the modulus of the congruence.
a≡b(modn)↔n∣a−ba \equiv b \pmod{n} \leftrightarrow n \mid a - b

Thus 17≡2(mod5)17 \equiv 2 \pmod{5}, because 17−2=1517 - 2 = 15; −3≡9(mod4)-3 \equiv 9 \pmod{4}, because −3−9=−12-3 - 9 = -12; and an integer is even exactly when it is congruent to 00 modulo 22. That aa is a multiple of nn is now written a≡0(modn)a \equiv 0 \pmod{n}. With the modulus 11 all integers are congruent to one another, because 11 divides every integer; that case is of no interest, and in the examples the modulus will be at least 22. The sign ≡\equiv, with three strokes, recalls that of equality because, as will be seen, congruence behaves like equality in almost everything; the exception, division, will occupy the section on inverses.

The definition by the difference is the most convenient one for proofs, but the intuition of the initial examples is that of the remainder. The following proposition ensures that both say the same thing; its content was already observed, in another form, in the lesson on divisibility, when the divisibility tests were justified, and here it is proved in full detail.

PropositionCongruence and remainder

Two integers are congruent modulo nn if and only if they leave the same remainder when divided by nn. Let a=nq+ra = nq + r and b=ns+tb = ns + t be the divisions with remainder of aa and of bb by nn, with 0≤r<n0 \leq r < n and 0≤t<n0 \leq t < n. The figure arranges the integers from −10-10 to 2424 in rows of 55, so that each column gathers those that leave the same remainder.

Proof

  1. a−b=(nq+r)−(ns+r)=n(q−s)a - b = (nq + r) - (ns + r) = \resaltar{n(q - s)}

    If the remainders coincide, r=tr = t, then on subtracting the two divisions the remainder cancels, and the difference is a multiple of nn.

  2. a=b+nk=ns+t+nk=n(s+k)+ta = \resaltar{b} + nk = \resaltar{ns + t} + nk = \dato{d}{n(s + k) + t}

    Conversely, suppose that nn divides a−ba - b, that is, that a=b+nka = b + nk for some integer kk. We substitute the division of bb.

  3. 0≤t<n→r=t0 \leq t < n \rightarrow \resaltar{r = t}

    Since 0≤t<n0 \leq t < n, this equality is a division of aa by nn with remainder tt. By the uniqueness of the quotient and the remainder, tt is the remainder of aa, that is, t=rt = r.

  4. 23≡8≡−2≡−7≡3(mod5)23 \equiv 8 \equiv -2 \equiv -7 \equiv 3 \pmod{5}

    In the figure, −7-7, −2-2, 33, 88, 1313, 1818 and 2323 occupy the same column: all of them leave remainder 33, and their differences are multiples of 55.

In particular, every integer is congruent modulo nn to its remainder, which is one of the nn integers 0,1,…,n−10, 1, \ldots, n - 1, and to only one of them, because two of those integers are their own remainders and, if they are distinct, they leave distinct remainders. Computing modulo nn consists in replacing each number by a convenient representative of its column: the remainder, or sometimes a small negative number, such as −1-1 instead of n−1n - 1.