Does an integer $9
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.
 A: 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$.
A: this problem is equivalent to $n^2\equiv n \pmod{100}$. and by wolframalpha, solution of this equation is $n=25,76$.
A: 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$.
A: 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.
