4

The number $9376$ has a property that the last four digits of $9376^2$ remain the same.

How many $4$ digit numbers have this property? Are there values of $n>4$ such that a $n$-digit number has $n$ digits unchanged at the end after squaring?

Thank you for your help!

Tyler Clark
  • 1,742
Yang Lu
  • 67

3 Answers3

7

It suffices to find the solutions to $x^2 \equiv x \mod 16$ and $x^2 \equiv x \mod 625$. As these polynomials are degree two and we're looking at solutions mod prime powers, there are at most two solutions to each by Hensel's lemma. Each has only the solutions $x \equiv 0, 1$. These extend via CRT to solutions $0, 1, 625, 9376$.

The OEIS lists a sequence of least $n$-digit integers such that $a_n^2$ ends in $a_n$.

EDIT: Ross Millikan, in the comments below, notes that the CRT solution given here gives us two non-trivial (not $0$ and not $1$) such integers for each $n$. Let $x$ be one of them and $y$ be the other. Then one is $0$ mod $2^n$ and the other is $0$ mod $5^n$; their product is $0$ mod $10^n$. So $(x+y)^2 = x^2 + 2xy + y^2 \equiv x^2 + y^2 \equiv x+y \mod 10^n$; this gives us another solution to $x^2 \equiv x$ that is not divisible by $2$; so it is $1$. Thus $x+y \equiv 1 \mod 10^n$. This, along with the fact that neither $x$ nor $y$ are $1$, proves that there exists such an integer of length $n$ for all $n$.

  • 1
    If you allow leading zeros like $0625$ for four digits, there are two of each length. Your CRT solution guarantees this. They will add to $1 \pmod {10^n}$ – Ross Millikan Mar 10 '14 at 14:44
  • @RossMillikan Ah, I see - and this guarantees the existence of one of length $n$. I'll add this. –  Mar 10 '14 at 14:47
  • Why mod 16 and mod 625? – Emily Mar 10 '14 at 14:54
  • 1
    By experiment, you can find the $n$ digit ones by taking the last $n$ digits of the square of the $n-1$ digit ones. It would be nice to prove this. – Ross Millikan Mar 10 '14 at 14:54
  • @Arkamis: because $2^4=16,5^4=625$ We are factoring $10^4$ into coprime factors to use CRT – Ross Millikan Mar 10 '14 at 14:55
  • @Arkamis This is the decomposition of $10^4 = 10000$ into products of prime powers $2^4 = 16$ and $5^4 = 625$. Polynomials are well-behaved modulo prime powers by Hensel's lemma, and we can glue together the solutions with CRT. –  Mar 10 '14 at 14:55
  • Ah, I had missed that the OP was only looking for 4 digit solutions, was wondering where the connection to 10000 came from. But that clears it up, thanks! – Emily Mar 10 '14 at 14:58
6

It seems that http://oeis.org/A094190 doesn't provide complete list of such numbers. Complete list (without leading zeros is here: http://oeis.org/A003226).

If not consider trivial $0$ and $1$, then for each $n$ there are $2$ $n$-digital such numbers, that last $n$ digits of their square are the same that number (sometimes solution has leading zeroes):

$$ \begin{array}{|l|rr|rr|} \hline \\ n & A & A^2 & B & B^2 \\ \hline \\ 1) & 5^2= & 2\color{red}{\bf 5} & 6^2= & 3\color{red}{\bf 6} \\ 2) & 25^2= & 6\color{red}{\bf{25}} & 76^2= & 57\color{red}{\bf{76}} \\ 3) & 625^2= & 390\color{red}{\bf{625}} & 376^2= & 141\color{red}{\bf{376}} \\ 4) & 0625^2= & 39\color{red}{\bf{0625}} & 9376^2= & 8790\color{red}{\bf{9376}} \\ 5) & 90625^2= & 82128\color{red}{\bf{90625}} & 09376^2= & 879\color{red}{\bf{09376}} \\ 6) & 890625^2= & 793212\color{red}{\bf{890625}} & 109376^2= & 11963\color{red}{\bf{109376}} \\ 7) & 2890625^2= & 835571\color{red}{\bf{2890625}} & 7109376^2= & 5054322\color{red}{\bf{7109376}} \\ ... & ... & ... & ... & ... \end{array} $$

Easy way to construct:

If $n$-digital number $A = \overline{a_{n-1}...a_2a_15}$, and $A^2 = \overline{...q_n \color{red}{a_{n-1}...a_2a_1 5 }}$, then first digit of next such $(n+1)$-digital number $A$ is $a_n=q_n$.

If $n$-digital number $B = \overline{b_{n-1}...b_2 b_1 6}$, and $B^2 = \overline{...r_n \color{red}{b_{n-1}...b_2 b_1 6}}$, then first digit of next such $(n+1)$-digital number $B$ is $b_n=10-q_n (\mod ~10)$.

Example: if $109376^2 = ...3\color{red}{109376}$, then first digit of next ($7$-digital) such number is $10-3 (\mod ~10) = 7$, so next number in "$B$-sequence" is $7109376$.

Just for curiosity:

$...580863811000557423423230896109004106619977392256259918212890625^2$

$...419136188999442576576769103890995893380022607743740081787109376^2$

Oleg567
  • 17,295
1

I know that this question has been sufficiently answered already, but just in case you're curious, I made this python program that finds these numbers:

x = input("Input Amount of Digits")  
y = 1  
z = 9  
for a in range(1, int(x)):  
    y = y*10 #Lower Bound  
    a = a+1  
for b in range(1, int(x)):  
    z = ((z*10)+9)  
    b = b+1      
print("Puzzle: There is one x-digit whole number n, such that the last x digits   of n2 are in fact the original number n.")  
print("Answers:")  
for c in range(y, z):  
    numstring = str(c**2)  
    if(int(numstring[-(int(x)):]) == c):  
        print(c)  
    else:  
        c = c+1  
input("Done. Press Enter to Exit.")
Lukas
  • 11