Questions: Modular Arithmetic and Congruences

Question 1

To compute 97 × 53 (mod 7), Student A multiplies first to get 5141, then reduces. Student B says '97 ≡ 6 and 53 ≡ 4 (mod 7), so the answer is 6 × 4 = 24 ≡ 3 (mod 7).' Is Student B's approach valid?

• A. No — you must compute the full product before reducing; intermediate reduction changes the result
• B. Yes — because congruences are compatible with multiplication, you can reduce operands before multiplying and get the same result
• C. No — Student B made an arithmetic error; 97 is not congruent to 6 mod 7
• D. Yes, but only when both operands are smaller than n²

Answer: (B)

97 = 13×7 + 6, so 97 ≡ 6 (mod 7). 53 = 7×7 + 4, so 53 ≡ 4 (mod 7). Then 6×4 = 24 ≡ 3 (mod 7). Verification: 97×53 = 5141 = 734×7 + 3. ✓ The compatibility of congruences with multiplication is exactly what makes modular arithmetic so powerful: you can reduce at any point without changing the final result, keeping numbers small throughout long computations.

Question 2

In ℤ₆, which equation has no solution, and why?

• A. 2x ≡ 4 (mod 6) — because 2 divides 6 and the result is even
• B. 3x ≡ 1 (mod 6) — because gcd(3, 6) = 3 ≠ 1, so 3 has no multiplicative inverse in ℤ₆
• C. 5x ≡ 1 (mod 6) — because 5 is greater than 6/2
• D. 4x ≡ 0 (mod 6) — because 4 and 6 share a common factor

Answer: (B)

For a to have a multiplicative inverse in ℤₙ, we need gcd(a, n) = 1. gcd(3, 6) = 3 ≠ 1, so 3x ≡ 1 (mod 6) has no solution. The other equations are satisfiable: 2x ≡ 4 has solution x = 2; 5x ≡ 1 has solution x = 5 (since 5×5 = 25 ≡ 1 mod 6, and gcd(5,6) = 1); 4x ≡ 0 has solutions x = 0 and x = 3.

Question 3

If a ≡ b (mod n), then a and b are equal as integers.

• T. True
• F. False

Answer: False

Congruence modulo n means n divides (a − b), not that a = b. For example, 17 ≡ 2 (mod 5) because 5 divides 15, but 17 ≠ 2. Congruence is an equivalence relation that groups integers into residue classes; elements of the same class are congruent but not identical. This distinction is the foundation of the subject.

Question 4

When n is prime, every nonzero element in ℤₙ has a multiplicative inverse.

• T. True
• F. False

Answer: True

When p is prime, gcd(a, p) = 1 for every a with 1 ≤ a ≤ p−1, because p has no divisors other than 1 and itself. The existence of a multiplicative inverse in ℤₙ requires gcd(a, n) = 1, so every nonzero element qualifies. This makes ℤₚ a field — division by nonzero elements always works — and explains why prime moduli are standard in cryptography.

Question 5

What makes the reduction principle in modular arithmetic computationally powerful, and in what types of problems does this become especially important?

Model answer: The reduction principle says that because congruences are compatible with addition and multiplication, you can reduce operands at any stage of a computation and still get the correct final result mod n. This prevents numbers from growing large during intermediate steps. In cryptography, for example, computing something like 2^1000 mod n would be intractable without this — intermediate powers would require astronomically large integers. Instead, you square-and-reduce at each step, keeping all values in {0, ..., n−1}. The same principle applies to primality testing, hashing, and error-correcting codes.

The key insight is that modular arithmetic lets you stay 'small' throughout a long computation. Without the reduction principle, modular problems involving large exponents or products would be computationally infeasible. The compatibility of congruences with arithmetic operations is not just a theoretical nicety — it is the foundation of practical algorithms.