## Congruences With Composite Moduli

To solve a congruence with composite modulus, write the modulus as a product of prime powers, then solve the congruence simultaneously for modulus of each prime power.,br /> Example: Solve
$2x^2+5x \equiv 3 \; (mod \; 72)$
.
$72 =8 \times 9=2^3 \times 3^2$
so the congruence becomes
$2x^2+5x \equiv 3 \; (mod \; 8)$
(1)
$2x^2+5x \equiv 3 \; (mod \; 9)$
(2)
Solving (1) by exhaustion, trying
$x \equiv 0, \; 1, \; 2,..., \; 7 \; (mod \; 8)$
gives
$x \equiv 5 \; (mod \; 8$
as the only solution.
Then
$x \equiv 5, \; 13, \; 21, \; 29, \; 37, \; 45, \; 53, \; 61, \; 69 \; (mod \; 72)$
are possible solutions to the question.
Solving (2) by exhaustion, trying
$x \equiv 0, \; 1, \; 2,..., \; 8 \; (mod \; 9)$
gives
$x \equiv 5, \; 6 \; (mod \; 9$
as the only solutions.
Then
$x \equiv 5, \; 6, \; 14, \; 15, \; 23, \; 24, \; 32, \; 33, \; 41, \; 42, \; 50, \; 51 \; 59, \; 60 \; 68, \; 69 \; (mod \; 72)$
are possible solutions to the question.
The numbers in both lists of possible solutions 5, 69.