# Problem of the week #31 - October 29th, 2012

Status
Not open for further replies.

#### Jameson

Staff member
There is one four-digit whole number n, such that the last four digits of $n^2$ are in fact the original number n. Find n.
--------------------

#### Jameson

Staff member
Congratulations to the following members for their correct solutions:

1) Sudharaka

Solution:

This problem can be approached in a brute force way so the interesting part of doing this problem is figuring out ways to eliminate the possibilities. Here is a non-rigorous method:

Looking at the last digit, the last digit must be either 0, 1, 5 or 6.

Then looking at the last two digits, the last two digits must be either 00, 01, 25 or 76.

Then looking at the last three digits, the last three digits must be either 000, 001, 625 or 376.

Then looking at the last four digits, the last four digits must be either 0000, 0001, 0625 or 9376.

Out of those, only 9376 is a 4 digit number.

Here is a much more advanced and rigorous approach from Sudharaka:

Since the last four digits of $$n^2$$ is the number $$n$$, if we subtract $$n$$ from $$n^2$$ we get four zeros in the last four digits. Therefore $$10^4$$ divides $$n^2-n$$. That is,

$n^2-n\equiv 0\mbox{ (mod }10^4)$

This is a quadratic congruence whose solutions can be found out using the the method explained here (http://www.cs.xu.edu/math/math302/04f/PolyCongruences.pdf). Since $$10^4=2^4\times 5^4$$ we have to solve the two congruences,

$n^2-n\equiv 0\mbox{ (mod }2^4)~~~~~~~~(1)$

and

$n^2-n\equiv 0\mbox{ (mod }5^4)~~~~~~~~~~~~~~(2)$

Although the first congruence can be solved by testing for each values from $$0$$ to $$15$$, solving the second congruence is tedious and we will be forced to use the Hansel's lemma (Hensel's lemma - Wikipedia, the free encyclopedia).

After solving the two congruences (1) and (2) we can use the Chinese remainder theorem (Chinese remainder theorem - Wikipedia, the free encyclopedia) to find out the solution to the original problem,

$n^2-n\equiv 0\mbox{ (mod }10^4)$

$n=0,1,625,9376\mbox{ (mod }10^4)$
$n=9376$