# find all the solutions: chinese remainder + fermat theorem

I have following congruences, in first congruence I know I have to use the Fermat theorem for finding the solution but I couldn't understand how, because most of the samples in internet using some numbers instead of x. could somebody please explain it for me in simple way?

1) $x^2 \equiv 1 \pmod{3}$

$3x \equiv 6 \pmod{15}$

2) what about the following case? $x^3 \equiv 1 \pmod{3}$

by the way I know this link but as I said it explain by numbers.

• @Timbuc. I know also x2≡1(3) = x≡(+ - )1(3) and x≡−1(3)=x≡2(3) but why? what about if I have x4≡1(5)? Apr 29, 2015 at 8:36
• You can write $3x\equiv 6 (15)$ in the expanded equivalent form $3x=6+15n$ - can you solve that for $x$ Apr 29, 2015 at 8:37
• Note that $3x\equiv6\bmod{15}$ is the same as $x\equiv2\bmod5$. Apr 29, 2015 at 9:51

For (1) You know by fermat's little theorem that $x$ must be coprime with $3$ and so you have $x=1,2$ and so $x \equiv 1 \pmod 3 \space \textbf{or} \space x \equiv 2 \pmod3$ And you can even try it $1^2 \equiv 1 \pmod3$ $\space$ and $\space$ $2^2 \equiv \pmod 3$

now you have $3x \equiv 6 \pmod{15}$

And since $3,6$ and $15$ are all divisible by $3$ then You can divide the congruence by $3$ to get $x \equiv 2 \pmod5$ Now how can you use the Chinese remainder theorem ?

the answer is any x =2+5(3k) or x=2+5(1+3k). For the second equation gives x-2=5k or x=2+5k and upon squaring we get k=0 or 1 mod 3. The result follows.