Solutions of the Congruence

Question

If $x^{10}\equiv 1\pmod{\!55^2}$, how do I know one must have $x^{10}\equiv 1\pmod{\!5^2}$ and $x^{10}\equiv 1\pmod{\!11^2}$?

Answer 1

If $55$ divides a number $n$, then any divisor of $55$ must also divides the number $n$. $5$ and $11$ are divisors of $55$. Hence, $5$ and $11$ must both divide $x^{10}-1$. This mean we want $x$ such that \begin{align} x^{10} & \equiv 1\pmod5\\ x^{10} & \equiv 1\pmod{11} \end{align} From Fermat's little theorem, we have that $x^4 \equiv 1 \pmod5$ for $x \in \{1,2,3,4\}\pmod5$ and $x^{10} \equiv 1 \pmod{11}$, for $x \in \{1,2,3,4,5,6,7,8,9,10\}\pmod{11}$. This means we have $x^{10} \equiv x^2 \equiv 1\pmod{5}$.

Hence, our $x$ must be $\pm1 \pmod5$ and $x \equiv \pm1,\pm2,\pm3,\pm4,\pm5\pmod{11}$.

This gives us $20$ possible solutions.

Answer 2

Definition: $a\equiv b\pmod{\!n}\iff n\mid a-b$.

So $x^{10}\equiv 1\pmod{\!5^211^2}\,\Rightarrow\, 5^2,11^2\mid 5^211^2\mid x^{10}-1$

$\,\Rightarrow\, x^{10}\equiv 1\pmod{\!5^2},\: x^{10}\equiv 1\pmod{\!11^2}$.

We used the fact $ab\mid n\,\Rightarrow a,b\mid ab\mid n$, which is true because $n=ab(k)=a(bk)=b(ak)$ for some $k\in\Bbb Z$ by definition of divisibility and which by transitivity implies $a,b\mid n$.