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