Questions: Linear Congruences and Solutions

Question 1

How many solutions does 6x ≡ 4 (mod 9) have?

• A. No solutions
• B. Exactly one solution modulo 9
• C. Exactly 2 solutions modulo 9
• D. Exactly 3 solutions modulo 9

Answer: (A)

The solvability condition is that gcd(a, n) must divide b. Here gcd(6, 9) = 3, and 3 does not divide 4 (since 4 = 3 × 1 + 1). Therefore, no solutions exist. A common mistake is checking only whether a and n are coprime — that is the condition for a unique solution, not for existence. When gcd(6, 9) = 3, solutions exist only if b is a multiple of 3, which 4 is not.

Question 2

For ax ≡ b (mod n) where gcd(a, n) = 1, which statement best describes the solution set?

• A. No solution exists, because a and n share no common factors
• B. Exactly one solution modulo n
• C. Infinitely many solutions
• D. Exactly gcd(a, n) = 1 solutions, meaning no solution

Answer: (B)

When gcd(a, n) = 1, the solvability condition gcd(a, n) | b is automatically satisfied for any b, and there is exactly one solution modulo n. This is the coprime case — the cleanest scenario. Options A and D reflect a misreading: gcd = 1 is favorable, not problematic. Exactly one solution means a has a unique modular inverse modulo n, the foundation of modular division.

Question 3

The congruence 4x ≡ 2 (mod 6) has exactly 2 distinct solutions modulo 6.

• T. True
• F. False

Answer: True

gcd(4, 6) = 2, and 2 divides 2, so solutions exist. By the theorem, the number of distinct solutions modulo n equals gcd(a, n) = 2. The two solutions are x ≡ 2 (mod 6) and x ≡ 5 (mod 6). Check: 4 × 2 = 8 ≡ 2 (mod 6) ✓; 4 × 5 = 20 ≡ 2 (mod 6) ✓.

Question 4

If ax ≡ b (mod n) has at least one solution, then gcd(a, n) is expected to equal 1.

• T. True
• F. False

Answer: False

The existence of a solution requires only that gcd(a, n) divides b — not that gcd(a, n) = 1. For example, 4x ≡ 2 (mod 6) has solutions (x = 2 and x = 5) even though gcd(4, 6) = 2 ≠ 1. The condition gcd = 1 guarantees a unique solution; it is sufficient but not necessary for existence.

Question 5

Explain why the condition gcd(a, n) | b is both necessary and sufficient for ax ≡ b (mod n) to have integer solutions. What does this mean in terms of the values you can 'reach' with ax − nk?

Model answer: The congruence ax ≡ b (mod n) is equivalent to the Diophantine equation ax − nk = b. By Bezout's theorem, the set of all integers expressible as ax − nk (as x and k range over integers) is exactly the set of multiples of gcd(a, n). Therefore b must be a multiple of gcd(a, n) for a solution to exist — and this is also sufficient, since if gcd(a, n) divides b, scaling a particular Bezout solution finds x.

The key insight is that linear combinations ax − nk can only produce multiples of gcd(a, n). No matter how you choose x and k, you can never reach a b that isn't in this set. Once b is in this set, dividing through by gcd(a, n) reduces the problem to a coprime case with a unique solution modulo n/gcd(a, n).