A number and its square

Question

Find a four-digit number which is equal to the four least significant (rightmost) digits of its own square.

Answer 1

The equation

$$x^2 = x \bmod 10^4$$

is true exactly if $10^4$ is a divisor of $x (x -1)$. This requires that the prime factorizations of $x$ and $x-1$ jointly contain $2^4$ and $5^4$. Since they are relatively prime, each of $2^4$ and $5^4$ must be divisor of one of them. A factor of both would be a multiple of $10^4$ and thus not 4 digits, so each number must be a multiple of one factor:

• $2^4 \mid x $ and $5^4 \mid x-1$, or
• $5^4 \mid x $ and $2^4 \mid x-1$

We can use the Chinese remainder theorem algorithm to find the corresponding residue classes

• $x = 9376 \mod 10000$
• $x = 625 \mod 10000$

The second doesn't correspond to any four-digit numbers, so the only solution is $9376$.

Answer 2

I think this is the only one:

9,376 * 9,376 = 87,909,376

Answer 3

Its 9376. I ran a brute force and calculated it using below program.

#include<cmath>
#include<iostream>
using namespace std;
int last4digit(int n)
{
        int x = n / 10000;
        n -= x * 10000;
        return n;
}
int main()
{
    for (int i = 1000; i < 10000; i++)
    {
        if (i == last4digit(pow(i, 2))) 
            cout << i;
    }
    system("pause");
    return 0;
}

Answer 4

My solution with no knowledge of the Chinese remainder theorem and no sophisticated thinking! It must end in 5 or 6 (0² and 1² are of course equal to 0 and 1 but the 'tens' digit always fails) Choose 5 or 6 and and let the first, second and third digits be a,b,c. I'll use 6. Treat it as if abc6 were a proper decimal number and square it by long multipication, spacing the columns wide enough, though we only need the four rightmost columns (bc in the 'thousands' column will mean b×c thousands etc) I'll put in more steps than I suspect are needed, for clarity:

   a         b      c     6
  ~~~~~~~~~~~~~~~~~~~~~~~~~
  6a        6b     6c    36
  bc        c²     6c
  bc        6b  
  6a
 ___________________________
 12a+2bc  12b+c²   12c  36     then tidy a bit

  2a+2bc+b 2b+c²+c 2c+3  6 

Using ≡ to mean is equivalent to, mod 10; 
and working columns right to left

2c+3 ≡ c
c+3 ≡ 0
c = 7         2c+3 = 17 so add 1 to next column

2b+c²+c+1 ≡ b
 b+57≡0
 b=3          2b+c²+c+1 = 63 so add 6 to next column

12a+2bc+b+6 ≡ a
11a+42+3+6 ≡ 0
11a+51 ≡ 0
  a+1 ≡ 0
  a=9

So answer = 9376

It is even easier for the other solution leading to 30 ≡ a at the end. With a little care this technique can of course be used in other bases than 10, and any number of final digits.

Update: This was a dangerous question for me; I tried it in base 60, 
like the Sumerians used. Here's the six results 
complete with squares, and translations into base 10. 
With the sums at the bottom:

   44,45,56,16     33,23,57,41,44,45,56,16   966 9376    9349683222 9376
   50,22,13,21     42,17,10,28,50,22,13,21  1088 0001   11837442176 0001
   24,51,50,25     10,18,13,07,24,51,50,25   537 0625    2884361289 0625
   35,08,09,36     20,34,32,18,35,08,09,36   758 9376    5759862806 9376
   09,37,46,40     01,32,43,47,09,37,46,40   208 0000     432640000 0000
   15,14,03,45     03,52,05,10,15,14,03,45   329 0625    1082821289 0625 

03,00,00,00,03  01,51,58,42,34,00,00,00,03

Notice that pairs add up to 01,00,00,00,00,01 as we might expect,
but also look at the last four digits of the translations.
I didn't expect that. Time for more thinking.