The Integers Modulo n

The congruence classes modulo n as a number system. The set Z_n, the proof that adding and multiplying classes through their representatives is well defined, operations that look reasonable and are not, the laws of arithmetic in Z_n and how they are inherited from the integers, the addition and multiplication tables of Z_13, a quadratic equation with eight solutions in Z_24, powers by repeated squaring, and unsigned integers in computers as arithmetic modulo 2^32.

At 7 o'clock, eight hours from now it will be 3 o'clock. Clock arithmetic adds hours and throws away multiples of 12, and nobody needs to know which day it is. Whether "7 o'clock" means hour 7, hour 19 or hour $-5$ of some reference day, adding 8 hours lands on 3 o'clock. Can the twelve hours, and the classes modulo any $n$, be treated as numbers in their own right, with an addition and a multiplication of their own?

In the language of the previous article, the hours are congruence classes modulo 12, and the clock is adding classes. The classes modulo $n$ form a set $\mathbb{Z}_n$ with $n$ elements, the integers modulo $n$. The natural way to add two classes is to add one representative of each and take the class of the result, and that rule is ambiguous until it is proved that the choice of representatives cannot affect the answer. Once that central step of the unit is done, $\mathbb{Z}_n$ is a number system that obeys the familiar laws, and the first new example of a ring in the course.

First we define $\mathbb{Z}_n$, prove that its operations are well defined, and see two rules that fail the same test. Then we show that $\mathbb{Z}_n$ inherits the laws of arithmetic from the integers. Next we read its tables and meet a quadratic equation with eight solutions. Finally we compute large powers quickly and see that a computer's unsigned integers are arithmetic in $\mathbb{Z}_{2^{32}}$.

This is the third article of Congruence and Modular Arithmetic. It covers §2.2 and the notation at the start of §2.3 of the course text (Hungerford, 2014), and assumes congruence modulo $n$ and the idea of a well-defined rule from equivalence relations and partitions.

The set $\mathbb{Z}_n$

Definition. Let $n$ be a positive integer. The integers modulo $n$ is the set $\mathbb{Z}_n$ of congruence classes modulo $n$. By the theorem on congruence classes, it has exactly $n$ elements:

$$\mathbb{Z}_n = \{\, [0], [1], \ldots, [n - 1] \,\}.$$

A common misreading is that $\mathbb{Z}_n$ is the set of numbers $0, 1, \ldots, n - 1$. Its elements are sets of integers, not integers. The class $[3]$ in $\mathbb{Z}_{12}$ is the infinite set $\{\ldots, -9, 3, 15, 27, \ldots\}$, and the same class is equally well named $[15]$ or $[-9]$. A statement such as "$[15] = [3]$ in $\mathbb{Z}_{12}$" is a true equation between sets, while "$15 = 3$" is false as a statement about integers.

The notation $\mathbb{Z}/n\mathbb{Z}$, read "$\mathbb{Z}$ modulo $n\mathbb{Z}$", is also common. It says how the set was made: the integers, with multiples of $n$ treated as zero.

Check your understanding. The class $[3]$ belongs to $\mathbb{Z}_{12}$, and a class $[3]$ also belongs to $\mathbb{Z}_6$. Are they the same set?

They are not. Every integer $3 + 12k$ is also $3 + 6 \cdot 2k$, so $[3]_{12}$ is contained in $[3]_6$, but $[3]_6$ also contains 9. In fact $[3]_6 = [3]_{12} \cup [9]_{12}$, as the script confirms. The symbol "[3]" names different sets for different moduli.

Adding and multiplying classes

The obvious definitions are

$$[a] + [b] = [a + b], \qquad [a] \cdot [b] = [ab].$$

The course text writes $\oplus$ and $\odot$ for these operations at first, to keep them visibly separate from addition and multiplication of integers. It drops the circles once the operations are established. Each definition says: to combine two classes, pick a representative of each, combine the representatives as integers, and take the class of the result.

The problem is the word "pick". In $\mathbb{Z}_{12}$, the class of 7 o'clock is $[7] = [19] = [-5]$ and the class of eight hours is $[8] = [-4] = [32]$. Three choices of representatives give

Representatives Sum Class of the sum Product Class of the product
7 and 8 15 $[3]$ 56 $[8]$
19 and $-4$ 15 $[3]$ $-76$ $[8]$
$-5$ and 32 27 $[3]$ $-160$ $[8]$

The answers agree, but three examples prove nothing. If some other choice gave a different class, the "definition" would not define anything, because $[7] + [8]$ would have no single value.

The operations are well defined

Theorem. Let $n$ be a positive integer, and suppose $[a] = [a']$ and $[b] = [b']$ in $\mathbb{Z}_n$. Then

$$[a + b] = [a' + b'] \qquad \text{and} \qquad [ab] = [a'b'].$$

Consequently the rules $[a] + [b] = [a + b]$ and $[a][b] = [ab]$ define operations on $\mathbb{Z}_n$: the result depends only on the classes, not on the representatives used to compute it.

Here is the idea in one sentence: changing a representative adds a multiple of $n$, and sums and products of congruent numbers are congruent.

Proof. Two classes are equal exactly when their representatives are congruent. So the hypotheses say $a \equiv a' \pmod n$ and $b \equiv b' \pmod n$; write $a' = a + nk$ and $b' = b + nl$ with integers $k$ and $l$. Then

$$a' + b' = (a + b) + n(k + l), \qquad a'b' = ab + n(al + bk + nkl),$$

so $a' + b' \equiv a + b$ and $a'b' \equiv ab \pmod n$. That says $[a' + b'] = [a + b]$ and $[a'b'] = [ab]$. $\blacksquare$

The proof is the theorem on sums and products of congruences from the previous article, read as a statement about classes. It is Hungerford's Theorem 2.6. The script for this article also checks it by brute force, for every modulus up to 20 and thousands of choices of representatives.

What it establishes is worth stating plainly. Arithmetic in $\mathbb{Z}_n$ can be done with any representatives at all, and in particular with the remainders $0, \ldots, n - 1$, reducing after each step. That is how the clock does it.

Operations that are not well defined

Not every reasonable-looking rule passes this test. Seeing one fail shows what the theorem accomplished.

Check your understanding. Try to define the later of two hours on the clock by $\max([a], [b]) = [\max(a, b)]$. Is this well defined on $\mathbb{Z}_{12}$?

It is not. With representatives 7 and 8 the rule gives $[8]$, and with 19 and 8, which name the same two classes, it gives $[19] = [7]$. Adding a multiple of 12 to one integer can change which is larger, so on a clock "later" has no meaning without a day attached.

Powers with a class as the exponent. Try to define $2^{[k]}$ in $\mathbb{Z}_5$ as $[2^k]$. In $\mathbb{Z}_5$, $[1] = [6]$, but $2^1 = 2$ and $2^6 = 64 \equiv 4 \pmod 5$. So the rule gives $[2]$ for one representative and $[4]$ for the other.

Raising a class to an integer power is fine, since $[a]^k = [a] \cdots [a]$ is repeated multiplication. What fails is treating the exponent as a class modulo 5. The powers of 2 modulo 5 run $2, 4, 3, 1, 2, 4, 3, 1, \ldots$ with period 4, so exponents behave as classes modulo 4, not modulo 5. The googol-days check in the previous article met the same trap. Which modulus governs exponents is the subject of Fermat's little theorem. Getting it right is what makes the RSA cryptosystem decrypt correctly.

Changing the modulus. Try to define a function from $\mathbb{Z}_6$ to $\mathbb{Z}_4$ by $[a]_6 \mapsto [a]_4$. In $\mathbb{Z}_6$, $[0]_6 = [6]_6$, but $[0]_4 \neq [6]_4 = [2]_4$. The rule assigns two values to one class, so it is not a function. The analogous rule from $\mathbb{Z}_{21}$ to $\mathbb{Z}_7$ does work. Two representatives of one class modulo 21 differ by a multiple of 21, which is also a multiple of 7, so they have the same class modulo 7. Maps of that kind are the starting point of ring homomorphisms.

In each failure, two representatives of the same class differ by a multiple of the modulus, and the rule does not ignore that multiple. Addition and multiplication ignore it, which is the content of the theorem.

The laws of arithmetic

With the operations in hand, which of the familiar laws hold for them? All of the ones that are identities.

Theorem. For all classes $[a]$, $[b]$, $[c]$ in $\mathbb{Z}_n$:

  1. $[a] + [b]$ and $[a][b]$ are elements of $\mathbb{Z}_n$ (closure);
  2. $([a] + [b]) + [c] = [a] + ([b] + [c])$ and $([a][b])[c] = [a]([b][c])$ (associativity);
  3. $[a] + [b] = [b] + [a]$ and $[a][b] = [b][a]$ (commutativity);
  4. $[a] + [0] = [a]$ and $[a][1] = [a]$ (identities);
  5. $[a] + [-a] = [0]$ (additive inverses);
  6. $[a]([b] + [c]) = [a][b] + [a][c]$ (distributivity).

Here is the idea: compute each side of a law through representatives, where it becomes the same law in $\mathbb{Z}$, which holds.

Proof. Closure holds because each operation produces a class modulo $n$. For the other laws, use the quotient map $\pi(a) = [a]$ from $\mathbb{Z}$ to $\mathbb{Z}_n$. The definitions of the operations, now known to be well defined, say exactly that

$$\pi(a + b) = \pi(a) + \pi(b) \qquad \text{and} \qquad \pi(ab) = \pi(a)\,\pi(b)$$

for all integers $a$ and $b$. Each law is an equation between two expressions built from $[a]$, $[b]$, $[c]$, $[0]$, $[1]$ and $[-a]$ with sums and products. Applying the two rules from the inside out turns each side into $\pi$ of the corresponding expression in the integers $a$, $b$, $c$, $0$, $1$ and $-a$. For instance, the left side of the distributive law becomes $\pi(a(b + c))$ and the right side $\pi(ab + ac)$. The two integer expressions are equal by the same law in $\mathbb{Z}$, so their images under $\pi$ are equal. For the identities and inverses the integer equations are $a + 0 = a$, $a \cdot 1 = a$ and $a + (-a) = 0$. $\blacksquare$

The pattern of the proof is the important part. Any identity among sums and products that holds for all integers holds in $\mathbb{Z}_n$. Each side can be computed from representatives, where the identity holds, and the passage to classes respects both operations. The script verifies all the laws exhaustively for $n \le 12$.

The argument transfers identities only. An implication such as "if $ab = 0$ then $a = 0$ or $b = 0$" is not covered, and the section on equations shows what happens to it.

In the language of the next unit, the theorem says that $\mathbb{Z}_n$ is a commutative ring with identity (Rings: Definition and Examples). The list above is, nearly word for word, the definition of a ring, abstracted from this example and from $\mathbb{Z}$.

The modulus $n = 1$ is a degenerate case: $\mathbb{Z}_1$ has the single element $[0]$, which equals $[1]$, and every law holds trivially. For $n \ge 2$, $[0] \neq [1]$.

Additive inverses make subtraction possible: $[a] - [b] = [a] + [-b] = [a - b]$. The additive inverse of $[a]$ has the least nonnegative representative $n - a$ when $0 < a < n$. In $\mathbb{Z}_{13}$, $-[5] = [8]$.

Dropping the brackets

Writing brackets on every element quickly becomes tiresome. When it is clear that the computation is in $\mathbb{Z}_n$, the course text, like most authors, writes $a$ for the class $[a]$ and uses ordinary plus and times signs. In $\mathbb{Z}_{13}$ one then writes

$$5 + 9 = 1, \qquad 5 \cdot 8 = 1, \qquad 13 = 0, \qquad -5 = 8.$$

These are statements about classes. The convention is safe as long as the modulus is fixed and stated. It is unsafe when two moduli appear in one computation, which is when the notation $[a]_n$ returns.

Tables

A finite number system can be described completely by its addition and multiplication tables. The tables of $\mathbb{Z}_{13}$ have 169 entries each. The entry in row $a$ and column $b$ is the least nonnegative residue of $a + b$ or $ab$.

The addition and multiplication tables of the integers modulo 13, with entries equal to 0 shaded orange and entries equal to 1 shaded blue. Notice that in the addition table each row is the row above shifted one place, and every element appears once in each row. In the multiplication table, row 0 is all zeros, and each other row contains every element exactly once, so it contains exactly one 1: every nonzero element has a multiplicative inverse.
The addition and multiplication tables of the integers modulo 13, with entries equal to 0 shaded orange and entries equal to 1 shaded blue. Notice that in the addition table each row is the row above shifted one place, and every element appears once in each row. In the multiplication table, row 0 is all zeros, and each other row contains every element exactly once, so it contains exactly one 1: every nonzero element has a multiplicative inverse.

The tables show structure that the laws alone do not make obvious.

  • Each row of the addition table contains every element exactly once, because the equation $a + x = b$ has the unique solution $x = b - a$. The row of 5 is $5, 6, \ldots, 12, 0, 1, 2, 3, 4$.
  • Adding $1$ to itself 13 times gives $0$. In $\mathbb{Z}_n$, $n \cdot 1 = [n] = [0]$, so repeated addition returns to the start. In the integers it never does, and this is the main structural difference between $\mathbb{Z}$ and every $\mathbb{Z}_n$.
  • Each nonzero row of the multiplication table of $\mathbb{Z}_{13}$ also contains every element exactly once. The row of 5 is $0, 5, 10, 2, 7, 12, 4, 9, 1, 6, 11, 3, 8$. The 1 in column 8 says $5 \cdot 8 = 1$: the class 8 is a multiplicative inverse of 5, and division by 5 is possible in $\mathbb{Z}_{13}$. Every nonzero element of $\mathbb{Z}_{13}$ has an inverse, from $2 \cdot 7 = 1$ to $12 \cdot 12 = 1$.

That property of the nonzero rows fails for most moduli. In $\mathbb{Z}_{21}$, the row of 7 contains only $0, 7, 14$, and no 1. Which classes have inverses, and why 13 behaves so differently from 21, is the subject of the next article.

Equations in $\mathbb{Z}_n$

Linear equations of the form $x + a = b$ behave exactly as in the integers. Do quadratic equations? Over the integers, or the real numbers, $x^2 = 1$ has two solutions, $1$ and $-1$. In $\mathbb{Z}_{13}$ it also has two, $1$ and $12 = -1$. In $\mathbb{Z}_{24}$ it has eight:

$$x \in \{1, 5, 7, 11, 13, 17, 19, 23\}.$$

For example $5^2 = 25 \equiv 1$, $7^2 = 49 \equiv 1$ and $11^2 = 121 \equiv 1 \pmod{24}$. The usual argument that a quadratic has at most two roots rewrites $x^2 = 1$ as $(x - 1)(x + 1) = 0$ and concludes that one factor is 0. In $\mathbb{Z}_{24}$ that step fails: for $x = 5$ the factors are $4$ and $6$, both nonzero, and their product $24$ is $0$.

Nonzero elements whose product is zero are called zero divisors, and their presence is what breaks the familiar rules for solving equations. They exist in $\mathbb{Z}_n$ exactly when $n$ is composite, as the next article proves. The script also finds eight square roots of 1 in $\mathbb{Z}_{1729}$. Why the count is a power of 2 is explained by the Chinese remainder theorem.

Computing in $\mathbb{Z}_n$

Because any representative may be used at any step, a computation in $\mathbb{Z}_n$ never needs numbers much larger than $n^2$: reduce after every addition and multiplication. For powers this matters a great deal. To compute $3^{100}$ in $\mathbb{Z}_{1001}$, the 48-digit integer $3^{100}$ need never be formed, and 99 multiplications are not needed either.

The method of repeated squaring writes the exponent in binary, $100 = 64 + 32 + 4$, and computes the powers $3^{2^i}$ by squaring and reducing:

Power Computation Value in $\mathbb{Z}_{1001}$
$3^1$ 3
$3^2$ $3^2 = 9$ 9
$3^4$ $9^2 = 81$ 81
$3^8$ $81^2 = 6561$ 555
$3^{16}$ $555^2 = 308{,}025$ 718
$3^{32}$ $718^2 = 515{,}524$ 9
$3^{64}$ $9^2 = 81$ 81

Then $3^{100} = 3^{64} \cdot 3^{32} \cdot 3^4 = 81 \cdot 9 \cdot 81$. Since $81 \cdot 9 = 729$ and $729 \cdot 81 = 59{,}049 \equiv 991$, the answer is $3^{100} = 991$ in $\mathbb{Z}_{1001}$. It took six squarings and two further multiplications, and the script confirms it against the full integer.

For an exponent $k$, the method needs about $\log_2 k$ squarings and at most as many further multiplications. So an exponent with hundreds of digits costs only a few thousand multiplications. This is how the RSA cryptosystem can raise numbers to enormous powers.

Check your understanding. How many multiplications would repeated squaring need for $3^{1001}$?

In binary, $1001 = 1111101001_2$, with 10 digits, seven of them 1. That means 9 squarings to reach $3^{512}$ and 6 multiplications to combine seven powers: 15 in all, against 1,000.

The table also shows a coincidence that is not one: $3^{32} = 9 = 3^2$ in $\mathbb{Z}_{1001}$. Since 3 has an inverse in $\mathbb{Z}_{1001}$, the two sides can be divided by $3^2$, giving $3^{30} = 1$. The script finds that 30 is the smallest positive exponent with this property. Powers of 3 therefore repeat with period 30, and $3^{100} = 3^{90} \cdot 3^{10} = 3^{10}$, which is again 991.

Integers in a computer

Fixed-size integer arithmetic in computers is arithmetic in $\mathbb{Z}_n$ with $n$ a power of 2. The C standard says so explicitly for unsigned types: a computation on them "can never overflow". A result that does not fit "is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type" (ISO/IEC 9899:2011, §6.2.5, paragraph 9). With 32-bit unsigned integers, that number is $2^{32} = 4{,}294{,}967{,}296$. The machine computes in $\mathbb{Z}_{2^{32}}$, with the least nonnegative residues $0, \ldots, 2^{32} - 1$ as representatives:

  • $4{,}294{,}967{,}295 + 1 = 0$, since the sum is $2^{32}$;
  • $0 - 1 = 4{,}294{,}967{,}295$, the representative of $-1$;
  • $65{,}537 \cdot 65{,}537 = 131{,}073$, since the exact product $4{,}295{,}098{,}369 = 2^{32} + 2^{17} + 1$.

The script reproduces these with 32-bit unsigned integers. The laws of the theorem above hold for this arithmetic. So unsigned sums and products can be regrouped and reordered without changing the result, even when intermediate values wrap around. The guarantee is for unsigned types only: for signed integers, the same standard leaves a result outside the representable range undefined (§6.5, paragraph 5). Python's integers have no fixed size, and its % operator returns the least nonnegative residue for a positive modulus, as described in the division algorithm.

Check your understanding. Can two nonzero 32-bit unsigned integers multiply to 0?

They can, because $2^{32}$ is composite: $65{,}536 \cdot 65{,}536 = 2^{32}$ is stored as 0, and so is $2^{31} \cdot 2$, as the script confirms. In the terms of the previous section, $\mathbb{Z}_{2^{32}}$ has zero divisors, and every nonzero even number is one.

Where it leads

What we have learned

Adding and multiplying classes through representatives is well defined, because changing a representative only adds a multiple of $n$; rules that do not ignore that multiple, such as "the later hour", are not. Every identity of integer arithmetic carries over to $\mathbb{Z}_n$, so it is a commutative ring with identity, and a computation in it may reduce at every step.

Implications do not carry over. In $\mathbb{Z}_{13}$ every nonzero element has an inverse, while in $\mathbb{Z}_{21}$ the class 7 has none and in $\mathbb{Z}_{24}$ nonzero elements multiply to zero. Which classes can we divide by? The next article, Units and Zero Divisors in the Integers Modulo n, answers with the greatest common divisor.

References

  • Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.), §2.2 and the opening of §2.3. Brooks/Cole, Cengage Learning. The course text: addition and multiplication of classes are independent of the representatives (Theorem 2.6), the laws of arithmetic in $\mathbb{Z}_n$ (Theorem 2.7), and the convention of writing $a$ for $[a]$. record · 44 pages
  • ISO/IEC 9899:2011. Information technology: Programming languages: C, §6.2.5, paragraph 9 (unsigned arithmetic is reduced modulo one more than the largest representable value) and §6.5, paragraph 5 (out-of-range results are undefined). Cited from the final committee draft, WG14 N1570 (April 2011). record · 2 pages
  • Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026), §3.1.1, The Integers mod $n$, including Proposition 3.1.4 (the laws of arithmetic in $\mathbb{Z}_n$). Free online at judsonbooks.org. record · 44 pages