# Is it true that $76^n=76\pmod{100}$ for all $n>0$?

Note

$76^2=5776,$

$76^3=438976,$

$76^4=33362176,$

$76^5=2535525376,$

$$\cdots$$

Hence I guess that

$$76^n = 76 \pmod{100}$$ for any natural number $n$.

Is it correct?

And are there other numbers that have this property?

• How about $25$? – Lubin Feb 19 '18 at 23:13
• trivial: 0, 1, the smallest: 25 – z100 Feb 19 '18 at 23:13
• Hint: $\;76^n - 76 =76\cdot(76^{n-1}-1) = 4 \cdot 19 \cdot (76-1)(\cdots) = 300 \,\cdot\, (\cdots)\,$. – dxiv Feb 19 '18 at 23:14
• Are you aware that if $a \equiv k \mod n$ and $b \equiv m \mod n$ then $ab \equiv km\mod n$? So $76^k= 76^{k-2}*76^2 \equiv 76^{k-2}*76=76^{k-1} =76^{k-3}*76^2\equiv 76^{k-3}*76 = 76^{k-2}=...... \mod 100$. – fleablood Feb 20 '18 at 0:08
• Oh, @fleablood, I meant that $25^n\equiv25\pmod{100}$ – Lubin Feb 20 '18 at 2:33

This is true because $76^{2}\equiv 76 \left(\mathrm{mod}\,100\right)$. For other examples, you have to find $1\leq a\leq 99$ with $a^{2}\equiv a\left(\mathrm{mod}\,100\right)$, i.e. $a(a-1)$ is multiple of 4 and 25. This is true when $$\begin{cases} a\equiv 0, 1 \,(\mathrm{mod}4) \\ a\equiv 0, 1\,(\mathrm{mod}25) \end{cases}$$ since $a$ and $a-1$ is coprime. Hence we have 4 cases $$a\equiv 0, 1, 25, 76.$$

Not so long ago, I was chewed up for giving an unsatisfactory treatment of this, but I’ll try again:

The $10$-adic numbers, $\Bbb Z_{10}$, have a natural decomposition, $$\Bbb Z_{10}\>\cong\>\Bbb Z_2\oplus\Bbb Z_5\,,$$ those are the $2$-adic numbers and the $5$-adic numbers. When you recognize that $\Bbb Z_{10}=\projlim_n(\Bbb Z/10^n\Bbb Z)$, just as $\Bbb Z_2=\projlim_n(\Bbb Z/2^n\Bbb Z)$ and $\Bbb Z_5=\projlim_n(\Bbb Z/5^n\Bbb Z)$, as well as the importance of Chinese Remainder Theorem, which says that $\Bbb Z/10^n\Bbb Z\cong(\Bbb Z/2^n\Bbb Z)\oplus(\Bbb Z/5^n\Bbb Z)$, it all falls out.

Skip the abstract stuff: there are $10$-adic numbers, $$E_2=\dots8212890625;\quad\text{and}\quad E_5=\dots1787109376;\,,$$ which correspond to the quantities $1\oplus0$ and $0\oplus1$, respectively, in $\Bbb Z_2\oplus\Bbb Z_5$. Naturally $E_2^2=E_2$ and $E_5^2=E_5$: just try $90625^2$ and $9376^2$ to see that the results have last five digits $90625$ and $09376$, respectively.

Notice here that the last two digits of $E_2$ are $\equiv1\pmod{2^2}$ but $\equiv0\pmod{5^2}$. Same for the last six digits of $E_2$: congruent to $1$ modulo $2^6$ but divisible by $5^6$. Corresponding facts hold for $E_5$, as well as for any number of digits.

Finally, notice that as $10$-adic numbers, $E_2E_5=0$ while $E_2+E_5=1$, as is necessary if they really are the orthogonal idempotents in a direct sum of two rings.

It follows by induction:

If $a^2 \equiv a \mod n$ then $a^k \equiv a \mod n$ for all natural numbers $k$.

Pf: Base case: $a^1 \equiv a \mod n$.

Inductive step: If $a^n \equiv a \mod n$ then $a^{n+1} =a^n*a\equiv a*a=a^2 \equiv a \mod n$.

Even if $a^2 \not \equiv a \mod n$ but if you have instead $a^{m+1}\equiv a \mod n$ then $a^{km +1}\equiv a \mod n$ for all $k$.

example $51^2=2601 \equiv 1 \mod 100$ and $51^3 =132651\equiv 51 \mod 100$ so $51^{1 + 2k} \equiv 51 \mod 100$.

====

To find out if there are others we need $(10a + b)^2 = 100a + 20ab + b^2$ to end with $10a + b$.

Only $0, 1, 5,6$ when squared will end with itself.

$(10a + 0)^2 = 100a^2$ will end with $00$ so $0$ is one such number.

$(10a + 1)^2 = 100a^2 + 20a + 1$ so we need $20a$ to end with $a$ so $a = 0$ and $1$ is another such number.

$(10a + 5)^2 = 100a^2 + 100a + 25$ so we need $a=2$ and so $25$ is another such number.

Finally $(10a + 6)^2 = 100a^2 + 120a + 36$ so we need $2a + 3$ to end with $a$.

If $a = 0,1,2,3,4,5,6,7,8,9$ then $2a + 3 = 3,5,7,9,11,13,15,17,19,21$. Only $2*7 + 3 = 17$ will end with $a$. So $76$ is the last such number.

$0,1,25$ and $76$ are the only such numbers.

Note that: $$100n+m\equiv m\ (\mathrm{mod}100)$$ You know: $$76*76=76^2=5776\equiv76(\mathrm{mod}100)$$ So for any integer $n$, we have: $$(100n+76)*76\equiv76(\mathrm{mod}100)$$ Then the answer comes.

Just note that for all $a$, $a \equiv a^2 \equiv \cdots (\mod 1000)$ iff $a^2 \equiv a(\mod 1000)$. Since $1000 | 76^2-76$, the conculusion followes.