Practice question · Multiple choice
The congruence 2x ≡ 3 (mod 4) has no solution, while 3x ≡ 3 (mod 4) has exactly one. Why does the coefficient decide whether solutions exist at all?
Hints
- Compute 2x mod 4 for x = 0, 1, 2, 3. Which residues can you reach?
- The condition involves gcd(a, n). Compute it in both cases.
Show the answer
C. Because ax ≡ b is solvable exactly when gcd(a, n) divides b.
Why
Work out what 2x reaches mod 4: 0, 2, 0, 2, multiplying by 2 collapses four classes onto two, so 3 is out of range. Multiplying by 3 permutes them instead, hitting every target once. The rule: ax ≡ b is solvable exactly when gcd(a, n) divides b. And 2 is prime with no inverse mod 4, so what matters is coprimality to n, not primality.
Practise Congruences and Applications
The app has 6 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.