7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ How about $25$? $\endgroup$ – Lubin Feb 19 '18 at 23:13
  • $\begingroup$ trivial: 0, 1, the smallest: 25 $\endgroup$ – z100 Feb 19 '18 at 23:13
  • 2
    $\begingroup$ Hint: $\;76^n - 76 =76\cdot(76^{n-1}-1) = 4 \cdot 19 \cdot (76-1)(\cdots) = 300 \,\cdot\, (\cdots)\,$. $\endgroup$ – dxiv Feb 19 '18 at 23:14
  • $\begingroup$ 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$. $\endgroup$ – fleablood Feb 20 '18 at 0:08
  • 2
    $\begingroup$ Oh, @fleablood, I meant that $25^n\equiv25\pmod{100}$ $\endgroup$ – Lubin Feb 20 '18 at 2:33
15
$\begingroup$

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.$$

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.