Number theory & modular arithmetic: practice problems with step-by-step solutions

1Remainders and congruences

Dividing a by n gives a quotient q and a remainder r: a = q·n + r with 0 ≤ r < n. The remainder is written a mod n. For a negative number q is negative too: −3 = −1·7 + 4, so −3 mod 7 = 4.

Two numbers are congruent modulo n, a ≡ b (mod n), when they leave the same remainder, that is when n divides a − b.

Remainders can be reduced at every step, which keeps the numbers small:

For example 47·58 mod 9: 47 ≡ 2 and 58 ≡ 4, so 47·58 ≡ 8 (mod 9).

2Euclid’s algorithm

The greatest common divisor gcd(a, b) is the largest number that divides both. Euclid’s algorithm uses gcd(a, b) = gcd(b, a mod b):

1. Divide: a = q·b + r.
2. Replace (a, b) with (b, r).
3. Repeat until the remainder is 0. The last nonzero remainder is the gcd.

The least common multiple follows from it: lcm(a, b) = a·b / gcd(a, b).

3Inverses and the extended algorithm

The inverse of a modulo n is the number x with a·x ≡ 1 (mod n). It exists exactly when gcd(a, n) = 1.

The extended Euclidean algorithm runs Euclid on (n, a) and keeps a coefficient t for each remainder, so that every remainder r ≡ t·a (mod n). Start with t = 0 for n and t = 1 for a; each new t is the t two rows up minus q times the t one row up. When the remainder 1 appears, its t is the inverse.

With the inverse, a congruence a·x ≡ b (mod n) is solved by x ≡ a⁻¹·b. When d = gcd(a, n) is larger than 1, there are d solutions if d divides b, and none otherwise.

Two congruences with coprime moduli, x ≡ r₁ (mod m₁) and x ≡ r₂ (mod m₂), have exactly one solution modulo m₁·m₂ (the Chinese remainder theorem). Write x = r₁ + m₁k and solve for k.

4Modular powers and RSA

Repeated squaring computes aᵏ mod n quickly: write k in binary, find a, a², a⁴, a⁸, … mod n by squaring and reducing, and multiply the powers whose bit is 1.

Fermat’s little theorem: for a prime p that does not divide a, aᵖ⁻¹ ≡ 1 (mod p). So the exponent can be reduced modulo p − 1.

RSA builds a key from two primes p and q:

1. n = p·q and φ(n) = (p − 1)(q − 1).
2. Choose e with gcd(e, φ(n)) = 1; (n, e) is the public key.
3. Compute d = e⁻¹ mod φ(n): the private key.
4. Encrypt c = mᵉ mod n; decrypt m = cᵈ mod n.

Euler’s φ(n) counts the numbers from 1 to n that are coprime to n: φ(p) = p − 1 for a prime, φ(pᵏ) = pᵏ − pᵏ⁻¹, and φ is multiplicative for coprime factors.

5Common mistakes

• Giving a negative remainder for a negative number: −17 mod 5 is 3, not −2.
• Stopping Euclid at the first remainder instead of the last nonzero one.
• Forgetting to add n to a negative coefficient from the extended algorithm.
• Computing the RSA exponent d modulo n instead of modulo φ(n).
• Reducing an exponent modulo p instead of p − 1 with Fermat’s theorem.

6How exam questions look

• Easy: gcd and remainders. You run Euclid’s algorithm for a gcd or lcm, find remainders of negative numbers, and reduce sums and products modulo n.
• Medium: inverses and congruences. You find modular inverses with the extended algorithm, solve linear congruences, combine two congruences with the Chinese remainder theorem, and compute Euler’s φ(n).
• Hard: modular powers and RSA. You use repeated squaring and Fermat’s theorem, solve congruences with several solutions, and find RSA private exponents, ciphertexts and decrypted messages.