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

[Jameson]

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.
--------------------
Remember to read the POTW submission guidelines to find out how to submit your answers!

 

[Jameson]

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:

Spoiler

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:

Spoiler

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)\]

The answers are,

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

Since we are looking for a four digit number the only possible answer is,

\[n=9376\]