# A number and its square

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

• If i understand this correctly you want us to give a number like 1111 and square it (which would make: 1234321) then the 4 right most digits (4321) should be 1111 again? (obviously 1111 doesn't work but it's a simple example) Apr 13 '15 at 15:15
• @VincentAdvocaat Exactly. Apr 13 '15 at 15:17
• So if i'm not a total fool the last number must always be 5 or 6 (xxx5 or xxx6) since those 2 are the only once to produce their same number onces squared (5^2 = 25 and 6^2 = 36). hmm interesting. O great whilst typing this JLee came up with an answer, too bad. Apr 13 '15 at 15:19
• This might have been better with a [no-computers] tag Apr 13 '15 at 15:29
• except brute forcing is the only answer (so it seems) so that makes it a bit impossible with no computer.. Apr 13 '15 at 16:41

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$.

I think this is the only one:

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

• Yes, normally there would be two of them of a given length, but $0625$ fails due to the leading zero. Apr 13 '15 at 15:19
• I am curious in what Kik was asking as well. A program can easily get it but is there like a general formula / strategry that's associate with?
– Alex
Apr 13 '15 at 15:22
• it's an: automorphic number, wikipedia has an article about it and it has an algorithm for finding out how many of those numbers there are in the given number space. though i don't know of something to make it easyer to find them Apr 13 '15 at 15:29
• @VincentAdvocaat - Thanks for the link. Maybe I am a nerd, but I was expecting an ideal answer to incorporate how this is realized (i.e. the algorithm). Apr 13 '15 at 17:02
• @Snowbody: no, it is not a coincidence. When there are two $n$ digit automorphic numbers they sum to $10^n+1$. For example $25^2=625, 76^2=5776, 25+76=101$. Apr 13 '15 at 20:51

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;
}

• Hmm, sort of unlucky that you answered late.
– user88
Apr 14 '15 at 4:47
• So, this is getting downvoted while an answer with even less explanation is at +10/-0?
– xnor
Apr 14 '15 at 6:56
• @xnor Well, at least the other answer showed why 9376 works. Apr 14 '15 at 9:38
• @randal'thor i edited and gave the solution to find it. Apr 14 '15 at 9:41
• @KishanKumar Thanks for editing! :-) Apr 14 '15 at 9:43

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



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.
`