Skip to content
Tutorials Center
My learning

Topics

Lesson 4 of 37 · Getting Started

Modular Arithmetic and the Integers

Review the division algorithm, gcd, the Euclidean algorithm and arithmetic mod n, and find which residues have multiplicative inverses.

The integers and the remainders mod n are the first, and most important, source of examples in abstract algebra. This lesson collects the number theory you need: the division algorithm, greatest common divisors, Bézout's identity and arithmetic mod n.

The division algorithm

For integers a and b > 0, there are unique integers q (quotient) and r (remainder) with

a = b·q + r, where 0 ≤ r < b.

For example 47 = 5·9 + 2. Python's divmod(47, 5) returns (9, 2), and for a positive divisor it also gives a nonnegative remainder when a is negative: divmod(-7, 5) is (-2, 3).

Congruence and ℤ_n

We write a ≡ b (mod n) when n divides a - b. This is an equivalence relation, and it has exactly n classes, represented by 0, 1, ..., n-1. Addition and multiplication of classes are well defined: if a ≡ a' and b ≡ b' then a + b ≡ a' + b' and ab ≡ a'b'. So ℤ_n gets an addition and a multiplication.

Greatest common divisor

The gcd of a and b is the largest positive integer dividing both. The Euclidean algorithm computes it by repeating gcd(a, b) = gcd(b, a mod b) until the remainder is 0. Bézout's identity says there are integers x, y with a·x + b·y = gcd(a, b). The extended Euclidean algorithm finds them.

Python Extended Euclidean algorithm

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If gcd(a, b) = 1 we say a and b are coprime.

Inverses mod n

In ℤ_n, an element a has a multiplicative inverse b when ab ≡ 1 (mod n). Such a b exists exactly when gcd(a, n) = 1. Reason: if gcd(a, n) = 1, Bézout gives ax + ny = 1, so ax ≡ 1 (mod n). If gcd(a, n) = d > 1, then ab ≡ 1 would make d divide 1, which is impossible.

The set of elements with inverses is the group of units U(n). Its size is Euler's totient φ(n), the count of numbers in 1..n coprime to n.

Python Units of ℤ_12 and ℤ_7

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that U(7) contains every nonzero residue, because 7 is prime. In general, ℤ_n is a field exactly when n is prime, which is the starting point of finite fields later in the course.

In ℤ_n you can have zero divisors: nonzero elements whose product is 0. For example 3 · 4 ≡ 0 (mod 12). Rings with zero divisors cannot be fields.

Fast powers

Computing a^k mod n for huge k uses repeated squaring, which Python provides as pow(a, k, n). Python 3.8 and later also computes inverses with pow(a, -1, n).

Python Powers and inverses with pow

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Summary of facts to keep

flowchart TB
    A["gcd(a, n) = 1"] <--> B["a has an inverse mod n"]
    B --> C["a ∈ U(n)"]
    N["n prime"] --> F["every nonzero a is a unit<br/>ℤ_n is a field"]

Units are exactly the residues coprime to the modulus.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What are the quotient and remainder when 47 is divided by 5?

    47 = 5·9 + 2 with 0 ≤ 2 < 5.
  2. 2. Which residue mod 12 has a multiplicative inverse?

    gcd(7, 12) = 1, and 7·7 = 49 ≡ 1 (mod 12). The others share a factor with 12.
  3. 3. How many elements does U(10) have?

    The units are 1, 3, 7, 9, so φ(10) = 4.
  4. 4. For which n is every nonzero element of ℤ_n invertible?

    If n is prime, every a from 1 to n-1 is coprime to n.

Summary

  • Every integer division gives a unique quotient and remainder.
  • ℤ_n has well-defined addition and multiplication of residue classes.
  • gcd(a, n) = 1 is the exact condition for a to have an inverse mod n; the extended Euclidean algorithm finds it.
  • U(n) has φ(n) elements, and ℤ_n is a field when n is prime.

Next: What Is a Group?