Does an integer $9<n<100$ exist such that the last 2 digits of $n^2$ is $n$?

Question

Does an integer $9<n<100$ exist such that the last 2 digits of $n^2$ is $n$? If yes, how to find them? If no, prove it.

This problem puzzled me for a day, but I'm not making much progress. Please help. Thanks.

Answer 1

We are solving $n(n-1)=n^2-n\equiv0\pmod{100}$. Since $\gcd(n,n-1)=1$, one of $n$ or $n-1$ must be a multiple of $4$ while the other must be a multiple of $25$.This leads to the equations $$ \begin{align} 4x-25y=+1\tag{1}\\ 4x-25y=-1\tag{2} \end{align} $$ For $(1)$, $n=4x$ and $n-1=25y$. For $(2)$, $n=25y$ and $n-1=4x$.

Using the Euclidean algorithm, $(1)$ has solutions $(x,y)=(-6+25k,-1+4k)$ and $(2)$ has solutions $(6+25k,1+4k)$. The two solutions that give $4x$ and $25y$ between $9$ and $99$ are $(19,3)$ and $(6,1)$.

$(19,3)$ solves $(1)$ so $n=4x=76$ and $76^2=5776\equiv76\pmod{100}$

$(6,1)$ solves $(2)$ so $n=25y=25$ and $25^2=625\equiv25\pmod{100}$

Thus, the two integers that satisfy the given condition are $25$ and $76$.

Answer 2

So, we need $n^2\equiv n\equiv{100}\iff 100\mid n(n-1)$

Now, $(n.n-1)=1$ and $100=2^25^2$

So,

either (i) $100\mid n\implies n=100k$ where integer $k\ge0$

So we need $0<100k<100\implies 0<k<1$ which is not possible .

or (ii) $100\mid (n-1)\implies n=100k+1$ where integer $k\ge0$

So we need $0<100k+1<100\implies 0<k<1$ which is not possible .

or (iii) $4\mid n$ and $25\mid (n-1)$

(a) $n\equiv0\pmod 4$ and $n\equiv1\pmod{25}$

Applying well-known Chinese Remainder Theorem,

$$n\equiv0\cdot b_1\cdot\frac{25\cdot4}4+1\cdot b_2\cdot\frac{25\cdot4}{25}\pmod{100}\equiv4b_1\pmod{100}$$

where $b_1\cdot\frac{25\cdot4}4\equiv1\pmod4$ and $b_2\cdot\frac{25\cdot4}{25}\equiv1\pmod{25}$

But we don't need $b_1$ as its coefficient is already $0$

and $4b_2\equiv1\pmod{25}\implies b_2\equiv4^{-1}\pmod{25}$

Using the Convergent property of continued fraction, $\frac{25}4=6+\frac14$

So, the last but one convergent is $\frac61\implies 25\cdot1-4\cdot6=1\implies 4^{-1}\equiv-6\pmod{25}$

$\implies b_2\equiv(-6)\pmod{25}\implies x\equiv4(-6)\pmod{100}\equiv-24$

(b)We have $n=4d,n-1=25e\implies 4d-25e=1$

$\implies 25e=4d-1 \implies 25(e+1)=4(d+6)\implies \frac{4(d+1)}{25}=e+1$ an integer

So, $25\mid(d+6)$ as $(25,4)=1$ $\implies d=25f-6$ for some integer $f$

$\implies n=4d=4(25f-6)=100f-24$

Using $(a)$ or $(b),$ we need $9<100f-24<100\implies 1\le f<2\implies f=1\implies n=76$

or (iv) $4\mid (n-1)$ and $25\mid n\implies n-1=4a,n=25b\implies 25b-4a=1$

Applying one of the two approaches $(a),(b)$ mentioned above, we get $n=100c+25 $

So we need $9<100c+25<100\implies 0\le c<1\implies c=0\implies n=25$

Answer 3

this problem is equivalent to $n^2\equiv n \pmod{100}$. and by wolframalpha, solution of this equation is $n=25,76$.

Answer 4

Write $n=10a+b$. Then $n² \equiv 20ab+b² \pmod{100}$. So the problem is reduced to solving $20ab+b²\equiv 10a+b \pmod{100}$. Hence $100|b(20a+b-1)-10a$. So $10|b(b-1)$. But $0\leq b<10$, thus either b is even and $b-1$ is divisible by $5$ or $b-1$ is even and $b$ is a multiple of $5$.
In the former case, $b$ must be $6$ and $100|110a+30$, viz. $a=7$ and $n=76$.
In the latter, $b$ must be $5$, so that $100|90a+20$, namely, $a$=$2$ and $n=25$.

Answer 5

More generally, instead of $4,25,$ let $\rm\,p, q\,$ be coprime prime powers. By $\rm\,n,n\!-\!1\,$ coprime

$$\rm pq\,|\,n(n\!-\!1)\ \Rightarrow\ p\,|\,n\ \ or\ \ p\,|\,n\!-\!1\ \ \ and\ \ \ q\,|\,n\ \ or\ \ q\,|\,n\!-\!1$$

This yields $4$ possibilities. Write $\rm\: n \equiv (a,b)\,\ (mod\ p,q)\:$ for $\rm\:n\equiv a\,\ (mod\ p),\ n\equiv b\,\ (mod\ q)$

$$\begin{eqnarray}\rm p,q\,|\,n &\iff&\,\rm n \equiv (0,0)\ \ (mod\ p,q)\\ \rm p,q\,|\,n\!-\!1 &\iff&\,\rm n \equiv (1,1)\ \ (mod\ p,q)\\ \rm p\,|\,n,q\,|\,n\!-\!1 &\iff&\,\rm n \equiv (0,1)\ \ (mod\ p,q)\\ \rm p\,|\,n\!-\!1,q\,|\,n &\iff&\,\rm n \equiv (1,0)\ \ (mod\ p,q)\\ \end{eqnarray}$$

By CRT, $\rm\ mod\ pq\!:\ (0,0) \equiv 0,\:$ and $\rm\:(1,1)\equiv 1,\:$ and for the sought nontrivial idempotents:

$$\rm\begin{eqnarray}(1,0) \!&\equiv&\rm\, q(q^{-1}\ mod\ p)\,\ (mod\ pq)\ [\equiv 25(25^{-1}\ mod\ 4)\equiv \color{#C00}{25}\,\ (mod\ 100)\ \ if\ \ p,q = 4,25]\\ \\ \Rightarrow\ \ \rm (0,1)\! &\equiv& (1,1)-(1,0)\:[\equiv 1-25\equiv -24 \equiv \color{#C00}{76}]\end{eqnarray}$$

Remark $\ $ Readers familiar with ring theory may note that the pair $\rm\:(a,b)\:$ is naturally viewed as an element of the product ring $\rm\:\Bbb Z/p \times \Bbb Z/q \,\cong\, \Bbb Z/pq\:$ via CRT (by $\rm\:p,q\:$ coprime). Generally such product decompositons are governed by idempotents (e.g. $(0,1),(1,0)),$ cf. Peirce decomposition.