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

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.

-
Why don't you check some small cases and see if any pattern appears? –  Jack Rousseau Feb 2 '13 at 7:12
Write a short program if it stumps you. –  copper.hat Feb 2 '13 at 7:14
@copper.hat So, you think this would help. How precisely? –  Did Feb 2 '13 at 10:04
@copper.hat Sure, one would get the answer in one minute (plus the time to write down the program)... And then what? This would bring zero insight about the situation (and we are not really interested in the solution itself, are we?). Insight might come from staring at the results and thinking hard about them to understand where they are coming from. So, one may as well try from the start to understand what is going on rather than being distracted from that by using a program, don't you think? –  Did Feb 2 '13 at 16:09
Did not mean to be patronizing, sorry if my comment sounded so to you. The crucial point is the following: if one has no idea about a proof and one is being told the solutions, which insight does one gain? To deduce a proof from the solutions (25 and 76) requires a kind of reverse engineering that I find more difficult than the exercise itself. But maybe this is me? –  Did Feb 2 '13 at 17:49

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

-
Would you please explain why "one of n or n−1 must be a multiple of 4 while the other must be a multiple of 25"? –  ᴊ ᴀ s ᴏ ɴ Feb 3 '13 at 3:11
Because neither $n$ nor $n-1$ could be divisible by $100$. –  awllower Feb 3 '13 at 6:56
@jasoncube: if either were divisible by both 4 and 25, then $n\equiv0\pmod{100}$ or $n-1\equiv0\pmod{100}$; that is, $n\equiv0\text{ or }1\pmod{100}$. However, neither $0$ nor $1$ is between $9$ and $99$. –  robjohn Feb 3 '13 at 7:24

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$

-
Would the down-voter please point out the mistake? –  lab bhattacharjee Feb 2 '13 at 17:35

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

-
Don't need no Alpha. Since $x$ and $x-1$ are relatively prime, one of $x$ or $x-1$ has to be divisible by $25$. –  André Nicolas Feb 2 '13 at 7:15
Two upvotes for summoning WA when there is no need? Hmmm... –  Did Feb 2 '13 at 10:02
@AndréNicolas: I didn't notice your comment before I wrote up my answer +1, for what it's worth. –  robjohn Feb 2 '13 at 14:14
@Did: perhaps Stephen W has an account here :-D –  robjohn Feb 2 '13 at 14:16
Notice that it is 3 upvotes minus 1 downvote here. –  awllower Feb 3 '13 at 3:04
show 1 more comment

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

-

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.

-
Marvellous application of ring-theory! –  awllower Feb 3 '13 at 3:09
Thus, as an easy generalisation, one sees that, for $(p,q)=(8,125)$, the only two non-trivial answers are 625 and 376. In fact, it could be concluded easily that, for any $p, q$, there are always two answers. Thanks for the nice answer then. –  awllower Feb 3 '13 at 6:49