Chinese Remainder Theorem

Hi,

How would one approach solving equations using the CRT if n (the modulo) is not made of only primes.

For example, n=63=3*3*7.

And suppose 15x=12 mod 63.

Under mod 3, clearly x = {0,1,2}
and under mod 7, x=5

So, to find a solution in mod 63,
I started with x=0 mod 3.
x=9t mod 3 for any t
and also
x = 5 mod 7,
so 9t = 5 mod 7,
so t=20=6+7s
and so x=9*(7s + 6)=63s + 54.
x mod 63 = 54.

But 54 is not a solution.
By brute force, the solution under mod 63 should be {5,26,47}
Using what I did above for all three x values under mod 3 (i.e x={0,1,2}), I get x={54,19,47}.

The only reason why I got one of them right is that it seems that those numbers that I get are multiples of 21 and 47 gives a multiple of 63.

So I don't know how to go about this problem :S

To solve a congruence with modulus 63 by the CRT, you need to solve it mod 9 (not 3) and mod 7. But in cases like this, it's often quicker to cancel by a common factor first.

The congruence is equivalent to . The reason for this is that if 15x+12=63k then you can divide by the common factor 3 to get 5x+4=21k.

The congruence has the solution x=5, and you get the solutions to the original congruence by adding multiples of 21.

EDIT: Too slow. Same as ^