Find the smallest integer $n$ greater than $1$ such that the last $3$ digits of $n^2$ are the same as the last $3$ digits of $n$.

Question

Find the smallest integer $n$ greater than $1$ such that the last $3$ digits of $n^2$ are the same as the last $3$ digits of $n$.

So far I've got $n^2 = 1000k + n$ which means $n^2 ≡ n \mod 1000$. I don't know how to proceed since 1000 seems to be a bit high.

Answer 1

$$n(n-1)\equiv0\pmod{2^35^3}$$

As $(n,n-1)=1,$ we can have following four cases

$$n\equiv0\pmod{2^35^3}$$

$$n-1\equiv0\pmod{2^35^3}$$

$$n-1\equiv0\pmod{2^3}\text{ and } n\equiv0\pmod{5^3}$$

$$n-1\equiv0\pmod{5^3}\text{ and } n\equiv0\pmod{2^3}$$

For the last two cases use Chinese Remainder Theorem

Answer 2

$n^2 \equiv n \pmod{1000}$ can be rearranged to $n(n-1) \equiv 0 \pmod{1000}$ Since $n$ and $n-1$ are coprime and $1000 = 2^3 \cdot 5^3$, what can you conclude about $n$?

A small amount of case analysis may be necessary.

Answer 3

Clearly $n\geq 100$. Since $$125\cdot 8\mid n(n-1)\implies 125 \mid n\;\;\; \vee \;\;\;125\mid n-1$$ and $$8 \mid n\;\;\; \vee \;\;\;8\mid n-1$$

so $$n\in \{100,101,125,126,250,251,375,376,...\}$$ so ...

Answer 4

Another way:

$(\pm1)^2\equiv1,(\pm2)^2\equiv4,(\pm3)^2\equiv9,(\pm4)^2\equiv6\pmod{10}$

The last digit of $n^2,n$ will be same if $n=10m,10m+1,10m+5,10m+6$

$(10m+6)^2\equiv36+20m\pmod{100}$

We need $10m+6\equiv36+20m\pmod{100}\iff10m\equiv-30\pmod{100}\iff m\equiv-3\pmod{10}$

WLOG $m=10r-3$

$10m+6=10(10r-3)+6=100r-24$

$(100r-24)^2\equiv576-4800r\pmod{1000}\equiv576+200r$

We need $100r-24\equiv576+200r\pmod{1000}\iff100r\equiv-600\equiv400\pmod{1000}\iff r\equiv4\pmod{10}$

$r=10s+4\implies100r-24=100(10s+4)-24=1000s+376$

Similarly for $10m+1,10m+5$

Answer 5

As explained here, we solve a modular quadratic via CRT as in the Remark below, here using also that a prime power $\,p^n\mid x(x\!-\!1)\iff p^n\mid x\ $ or $\ p^n\mid x\!-\!1,\,$ by $\,x,\,x\!-\!1\,$ coprime, which yields

$$x(x\!-\!1)\equiv 0\!\!\!\pmod{\!8\cdot 125}\iff \begin{align} &x\equiv 0,1\!\!\!\pmod{\!8}\\ &x\equiv 0,1\!\!\!\pmod{\!125}\end{align}\qquad\qquad $$

By the Remark they combine to $\,4\,$ roots $\,x\equiv (\color{#90f}{{0,0}}),\,(\color{#0a0}{1,1}),\,(0,1),\,(1,0)\,$ mod $(8,125).\,$ By CCRT the first two lift to $\,x\equiv \color{#90f}{0},\,\color{#0a0}{1} \pmod{\!1000},\,$ the third root $\,(0,1)\bmod (8,125)$ lifts by CRT as

$\!\bmod\, \color{#c00}{8}\!:\:\ 0 \equiv\, x \equiv 1+125\,\color{#c00}k \equiv 1-3k \iff 3k\equiv1\equiv9 \iff \color{#c00}{k \equiv 3}$

hence we infer $\ x = 1+125(\color{#c00}{3+8}n) = 376+1000n,\ $ so $\ (0,1)\,\mapsto 376.\,$ Like in Vieta, the final $4\rm'th$ root $\,(1,0)\,$ is easy using $\, (1,0) + \smash[b]{\underbrace{(0,1)^{\phantom{|^{|^|}}}\!\!\!\!}_{\large 376}}\equiv \smash[b]{\underbrace{(1,1)}_{\large 1}}_{\phantom{._{|_{|_{|_|}}}}}\!\!\!\!\!$ $\Rightarrow (1,0)\,\mapsto\, 1\!-\!376\equiv 625$

Remark $ $ For more complex examples it is usually easier to solve the CRT system first for generic (symbolic) roots, then plug in the specific root values for all combinations, e.g. see here and here.

If $\,m,n\,$ are coprime then, by CRT, solving a polynomial $\,f(x)\equiv 0\pmod{\!mn}\,$ is equivalent to solving $\,f(x)\equiv 0\,$ mod $\,m\,$ and mod $\,n.\,$ By CRT, each combination of a root $\,r_i\bmod m\,$ and a root $\,s_j\bmod n\,$ corresponds to a unique root $\,t_{ij}\bmod mn,\,$ i.e.

$$\begin{eqnarray} f(x)\equiv 0\!\!\!\pmod{\!mn}&\overset{\,\,\rm CRT}\iff& \begin{array}{}f(x)\equiv 0\pmod{\! m}\\f(x)\equiv 0\pmod{\! n}\end{array} \\ &\,\,\iff& \begin{array}{}x\equiv r_1,\ldots,r_k\pmod{\! m}\phantom{I^{I^{I^I}}}\\x\equiv s_1,\ldots,s_\ell\pmod{\! n}\end{array}\\ &\,\,\iff& \left\{ \begin{array}{}x\equiv r_i\pmod{\! m}\\x\equiv s_j\pmod {\! n}\end{array} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}^{\phantom{I^{I^{I^I}}}}\\ &\overset{\,\,\rm CRT}\iff& \left\{ x\equiv t_{i j}\!\!\pmod{\!mn} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}\\ \end{eqnarray}\qquad\qquad$$

Answer 6

In a practical way, the number $N$ is, $\forall p>=0$ $$p\times1000+(100a+10b+c)$$ We can ignore the prefix $p\times1000$ as it doesn't affect the $3$ last digits of $N^2$

We want $c$ and the last digit of $c^2$ to be equal $$c\equiv c^2\pmod{10}$$ That only works for $$\bbox[7px,border:1px solid gray]{c\in\{0,1,5,6\}}$$ For $b$, we want the second digit of $(10b+c)^2$ to be equal to $b$ (note: $\lfloor x\rfloor$ denotes the integer part of $x$) $$b\equiv \lfloor\frac{(10b+c)^2}{10}\rfloor\pmod{10}$$ Plugging our $c$ values, $b$ can only be $0$ if $c=0$, also $0$ if $c=1$, $2$ if $c=5$ and $7$ if $c=6$ $$\bbox[7px,border:1px solid gray]{c=0\implies b = 0}\\ \bbox[7px,border:1px solid gray]{c=1\implies b = 0}\\ \bbox[7px,border:1px solid gray]{c=5\implies b = 2}\\ \bbox[7px,border:1px solid gray]{c=6\implies b = 7}\\$$ Not so many valid candidates after all.
Finally, for $a$, we want the third digit of $(100a+10b+c)^2$ to be equal to $a$ $$a\equiv \lfloor\frac{(100a+10b+c)^2}{100}\rfloor\pmod{10}$$ We have only $4$ cases to check since $b$ and $c$ values are strongly correlated. Injecting our $(b,c)$ values,we get $$\bbox[7px,border:1px solid gray]{c=b=0\implies a = 0}\\ \bbox[7px,border:1px solid gray]{c=1,b=0\implies a = 0}\\ \bbox[7px,border:1px solid gray]{c=5,b=2\implies a = 6}\\ \bbox[7px,border:1px solid gray]{c=6,b=7\implies a = 3}\\$$ Meaning the last $3$ digits of $N$ can be any of $$000, 001, 625, 376$$ Since we want the smaller valid number $>1$, the answer is $$\bbox[8px,border:1px solid blue]{376}\\$$