# Congruence mod396

A question in to the numbertheory: give a non-trivial soloution for the equation $x^6\equiv x\ mod\ 396$. And how many soloutions does this congruence have?

I know by the Chinese Remainder Theorem that the congruence is equivalent to the system:$x^6\equiv x\ mod\ 2$, $x^6\equiv x\ mod\ 3$ and $x^6\equiv x\ mod\ 11$. Thereafter you can say that $\phi(2)=1$, $\phi(3)=2$ and $\phi(11)=10$ such that: $x^6\equiv x\ mod\ 2$, $x^3\equiv x\ mod\ 3$ and $x^6\equiv x\ mod\ 11$.

This doesn't seem to help. Can somebody help me? Thanx in advance!

## 2 Answers

$396=4\times9\times11$, so we have to solve $x^6\equiv x\pmod m$ for $m=4$, $m=9$, and $m=11$, and then use the Chinese Remainder Theorem.

By just trying everything, the solutions to $x^6=x\pmod4$ are $x\equiv0\pmod4$ and $x\equiv1\pmod4$.

Also, the solutions to $x^6\equiv x\pmod9$ are $x\equiv0\pmod9$ and $x\equiv1\pmod9$.

The solutions to $x^6\equiv x\pmod{11}$ are $x\equiv0,1,3,4,5,9\pmod{11}$.

OK?

Using the equations above, the values of x are 9,36,37,45,64,81,100,108,136,144,180,181,280,289,297,352,361,388,and 396.