Questions: Modular Arithmetic and Congruences

Question 1

To compute 7¹⁰⁰ (mod 5), a student notes that 7 ≡ 2 (mod 5) and instead computes 2¹⁰⁰ (mod 5). What property of modular arithmetic justifies replacing 7 with 2?

• A. Since 7 and 2 are in the same residue class mod 5, all arithmetic operations on them produce the same result mod 5
• B. This substitution only works for exponents, not for addition or multiplication
• C. This only works because 5 is prime
• D. 7 and 2 are both single-digit numbers, so the substitution happens to work in this case

Answer: (A)

The fundamental property of modular arithmetic is that congruent numbers behave identically in arithmetic operations. If a ≡ b (mod n), then aᵏ ≡ bᵏ (mod n) for any positive integer k — and the same holds for addition and multiplication. This holds for any modulus, not just primes, and for large numbers just as much as small ones. The entire power of modular arithmetic comes from this substitution principle: replacing large numbers with small residues before computing.

Question 2

In Z/6Z (integers mod 6), which element has a multiplicative inverse, and why?

• A. 4, because 4 is even and even numbers pair nicely in mod 6
• B. 2, because 2 is small and divides 6
• C. 5, because gcd(5, 6) = 1, meaning 5 and 6 share no common factors
• D. 3, because 3 is half of 6

Answer: (C)

The modular inverse of a (mod n) exists if and only if gcd(a, n) = 1. In Z/6Z: gcd(2, 6) = 2, gcd(3, 6) = 3, gcd(4, 6) = 2 — none equal 1, so 2, 3, and 4 have no inverses. But gcd(5, 6) = 1, so 5 has an inverse: 5 × 5 = 25 ≡ 1 (mod 6), confirming 5⁻¹ ≡ 5 (mod 6). This is why prime moduli are preferred in cryptography — every nonzero element has an inverse.

Question 3

13 ≡ 1 (mod 4)

• T. True
• F. False

Answer: True

13 − 1 = 12, and 12 is divisible by 4 (12 = 3 × 4). So 13 and 1 leave the same remainder when divided by 4 (both leave remainder 1), confirming 13 ≡ 1 (mod 4). Alternatively: 13 = 3 × 4 + 1, so the remainder is 1.

Question 4

In modular arithmetic, if a × b ≡ 0 (mod n), then either a ≡ 0 (mod n) or b ≡ 0 (mod n).

• T. True
• F. False

Answer: False

This cancellation law holds for ordinary integers but fails for composite moduli. Counterexample: 2 × 3 = 6 ≡ 0 (mod 6), but 2 ≢ 0 (mod 6) and 3 ≢ 0 (mod 6). The elements 2 and 3 are called 'zero divisors' of Z/6Z. This is why prime moduli are important: when n is prime, Z/nZ has no zero divisors, and the cancellation property holds as expected.

Question 5

Why does the modular inverse of a (mod n) only exist when gcd(a, n) = 1? Give an example illustrating what goes wrong when gcd(a, n) > 1.

Model answer: The modular inverse of a is a number x such that ax ≡ 1 (mod n), meaning ax − 1 is divisible by n, i.e., ax − ny = 1 for some integer y. By Bézout's identity, this equation has integer solutions if and only if gcd(a, n) divides 1, which requires gcd(a, n) = 1. When gcd(a, n) = d > 1, every value of ax − ny is divisible by d, so it can never equal 1. Example: try to find x with 4x ≡ 1 (mod 6). Every multiple of 4 is even, and 1 + 6k is odd for all k, so 4x can never equal 1 + 6k. No inverse exists because gcd(4, 6) = 2.

This is why cryptographic systems like RSA use prime moduli or carefully chosen composite moduli — the need for every nonzero element to have an inverse is essential for encryption and decryption to work. When the modulus is prime, gcd(a, p) = 1 for all nonzero a, so every element is invertible.