Finding the smallest $n$ such that $n^{2}$ ends with $00001$

Question

The problem is to find the smallest natural number $n$ so that its square's last $5$ digits are $00001$. $n$ and $n^{2}$ cannot begin with $0$.

I know that we have a lower bound on $n$, namely $\sqrt{100001}≈316.23$. Intuitively, I think the smallest natural number with the property has to be $100001$ and I have not found any counterexamples to this (in fact I checked using some code and it seems to be correct). I haven't been successful in proving this rigorously however. Do I use the lower bound in some way? How to approach this type of questions in general, i.e. how do digits respond to squaring/cubing?

All help is appreciated.

Answer 1

You want to find $n$ such that $n^2 \equiv 1 \pmod {10^5}$.

By Chinese remainder theorem, this is equivalent to $n^2 \equiv 1 \pmod {2^5}$ and $n^2 \equiv 1 \pmod {5^5}$.

We have $$n^2 \equiv 1\pmod {2^5} \iff n \equiv \pm 1 \pmod {2^4}$$ and $$n^2 \equiv 1 \pmod {5^5} \iff n \equiv \pm 1\pmod {5^5}.$$ Again by Chinese remainder theorem, these congruence relations give four possibilities of $n \mod 5\cdot 10^4$, namely $$n\equiv 1, 18751, 31249, 49999 \pmod {50000}.$$ From here, we see that the smallest such $n$ is $18751$.

Answer 2

We first have to realize that since n^2 must end in 00001, the units digit of n is either 1 or 9 because 1^2 = 1 and 9^2 = 81 (ends in 1). Then, to find a number n such that n^2 is ending in 001, the only last 2 possible digits of n can be 51, 49, or, 99. We can then repeat the process for 0001, ..., uptil 00001 to find that the smallest value of n is 18751.

Answer 3

Just to give a somewhat different approach, we have $10^5\mid(n-1)(n+1)$, so in particular $5^5=3125$ divides either $n-1$ or $n+1$, since two numbers that differ by $2$ cannot both be divisible by $5$. We may as well assume it divides $n-1$ (and then look for the smallest value of $|n|$). Since $n$ is obviously odd, we must have $n=6250m+1=32\cdot195m+10m+1$ for some $m$. Now, since $\gcd(n-1,n+1)=2$, we must have either $16\mid10m$ or $16\mid10m+2$. The smallest (nonzero) value of $m$ that satisfies one of these is $m=3$ (for which $16\mid10m+2$). So $n=6250\cdot3+1=18751$ is the smallest value of $n$ (greater than $1$) for which $n^2$ ends in $00001$.