Question

Determine the set of solutions of: X ? 1 (mod 81) and X ? 7 (mod 12), as the solutions to a single congruence.

Answer 1

Given system of congruences is : and

Here the moduli of the congruences 81 and 12 are not prime to each other.

gcd(81,12) = 3 and 7-1 = 6 is divisible by gcd(81,12). Therefore the congruences have a simultaneous solution.

The general solution of the first congruence has the form :

x = 1+81s, where s is an integer

i.e., x = 1+3*27s...............(i)

The general solution of the second congruence has the form :

x = 7+12t, where t is an integer

i.e., x = 1+3*(2+4t)...............(ii)

if t =13+27u, where u is an integer, then 2+4t is a multiple of 27 and in the case (i) and (ii) become identical.

The common solution is :

x = 1+3*[2+4*(13+27u)]

i.e., x = 1+6+12*(13+27u)

i.e., x = 7+156+324u

i.e., x = 163+324u, where u is an integer.

Therefore the solution is given by .