Show that $11^{10} \equiv 1 (\mod 100)$ $11^{10} \equiv 1 \pmod{100}$
I tried to solve by using euler's theorem, But I got stuck.
$\gcd(11, 100) = 1$
$11^{φ(100)} \equiv 1 \pmod{100}$
$11^{40} \equiv 1 \pmod{100}$
I don't know how to go on as $11^{40}$ is bigger than $11^{10}$
 A: Hint:
$$(1+10)^n\equiv1+\binom n110^1\pmod{10^2}$$ for positive integer $n$
A: Well..., you got $11^{40} \equiv 1 \pmod{100}\Rightarrow (11^{10}-1)(11^{10}+1)(11^{20}+1)\equiv 0 \pmod{100}$
Now it is easy to see that $(11^{10}+1)$ and $(11^{20}+1)$ end with $2$. Then $(11^{10}-1)\equiv 0 \pmod{25}$
Again $11^{2} \equiv 1 \pmod{4}\Rightarrow 11^{10} \equiv 1 \pmod{4}$
Since $\gcd(25,4)=1$, we will have $11^{10} \equiv 1 \pmod{100}\space\space\space\space\space\blacksquare$
A: $11^{10}-1$
$=(1+10)^{10}-1$
$=(1+\binom{10}{1}10+\binom{10}{2}10^2+...+10^{10})-1$
$=\binom{10}{1}10+\binom{10}{2}10^2+...+10^{10}$
is divisible by $100$.
A: You can use the binomial theorem if you want, but here it is a silly solution:
$11^2=21\operatorname{mod}100$, thus $11^{10}=(11^2)^5=21^5\operatorname{mod}100$.
If you compute $21^5=4.084.101=1\operatorname{mod}100$.
A: Alternatively:
$$11^{10}-1=(11^5-1)(11^5+1)=(11-1)(11^4+11^3+11^2+11+1)(11^5+1)=$$
$$10\cdot (...5)(...2)=...00.$$
A: Here is an indirect proof
Note that $\varphi (4) = 2$ and $\varphi (25) = 20$ so that if $r$ has no factor in common with $100$ we have $r^{20}\equiv 1 \bmod 4, \text{ and } \bmod 25 \text { hence also } \bmod 100$.
Note also that $6^2=36 \equiv 11 \bmod 25$
We have $$11^{10}=(11^2)^5 \equiv 1\bmod 4$$ and also $$11^{10}\equiv 6^{20}\equiv 1 \bmod 25$$ so that $$11^{10}\equiv 1 \bmod 100$$
Note that $11$ is not a square modulo $4$ or $100$, but the reduction of exponent by a factor of $2$ (which doesn't apply to the factor $4$ - with $\varphi (4)=2$ needing no reduction - $2$ is still a factor of the target exponent $10$) suggests looking for a square root modulo $25$.
A: $$\qquad{11^2\equiv 121\equiv 21\mod 100\\\\
(11^2)\times 11\equiv 231\equiv 31\mod 100\\
(11^4)\equiv 31\times 11\equiv 341\equiv 41\mod 100\\
(11^5)\equiv 41\times 11\equiv 451\equiv 51\mod 100\\
(11^6)\equiv 51\times 11\equiv 61\mod 100\\
(11^7)\equiv 61\times 11\equiv 71\mod 100\\
(11^8)\equiv 71\times 11\equiv 81\mod 100\\
(11^9)\equiv 81\times 11\equiv 91\mod 100\\
(11^{10})\equiv 91\times 11\equiv 1001\equiv 1\mod 100\\}$$
