- Thread starter
- Admin
- #1

- Jan 26, 2012

- 4,043

--------------------

Remember to read the POTW submission guidelines to find out how to submit your answers!

- Thread starter Jameson
- Start date

- Status
- Not open for further replies.

- Thread starter
- Admin
- #1

- Jan 26, 2012

- 4,043

--------------------

Remember to read the POTW submission guidelines to find out how to submit your answers!

- Thread starter
- Admin
- #2

- Jan 26, 2012

- 4,043

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:

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:

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

- Status
- Not open for further replies.