5
$\begingroup$

A natural number $a$ has four digits and $a^2$ ends with the same four digits as that of $a$. Find the value of $a$?

This question appeared in a math contest. I tried for a while and came up with this condition: $10^4|(a-1)a$. But I'm not able to take it further. It is clear that out of the two ($a-1$ and $a$) the one which is odd will contain no powers of 2 and hence the other one would contain the $2^4$. But there are to many possibilities for one to see by trial and error.

$\endgroup$

3 Answers 3

5
$\begingroup$

The equation $a^2 = a$ has exactly two solutions ($0$ and $1$) modulo any prime power, because:

  • Mod $p$, it has only two roots $0$ and $1$, because it's quadratic, and $\mathbb F_p$ is a field;
  • By Hensel's lemma, since the derivative of $a^2-a$ is $2a-1$ and is nonzero when $a=0$ or $a=1$ we can lift those solutions.

So we know that:

  • $a^2 \equiv a \pmod{2^4}$ only if $a \equiv 0 \pmod{2^4}$ or $a \equiv 1 \pmod{2^4}$,
  • $a^2 \equiv a \pmod{5^4}$ only if $a \equiv 0 \pmod{5^4}$ or $a \equiv 1 \pmod{5^4}$.

However, modulo $10^4$, we have more freedom, because we can glue these solutions any way we like by the Chinese remainder theorem. Our options are \begin{align} a\equiv 0 \pmod{2^4}\text{ and }a\equiv 0 \pmod{5^4} &\implies a \equiv 0 \pmod{10^4} \\ a\equiv 0 \pmod{2^4}\text{ and }a\equiv 1 \pmod{5^4} &\implies a \equiv 9376 \pmod{10^4} \\ a\equiv 1 \pmod{2^4}\text{ and }a\equiv 0 \pmod{5^4} &\implies a \equiv 625 \pmod{10^4} \\ a\equiv 1 \pmod{2^4}\text{ and }a\equiv 1 \pmod{5^4} &\implies a \equiv 1 \pmod{10^4} \end{align}

(To compute the two middle values, take $2^4$ times the inverse of $2^4$ modulo $5^4$, and $5^4$ times the inverse of $5^4$ modulo $2^4$, respectively.)

So in general (modulo $10^n$ for other $n$) there's two solutions other than $0$ and $1$, but because $625$ is not actually a four-digit number, the correct one here is just $9376$.


I guess a simpler way to get to the Chinese remainder step is to observe that if $10^4 \mid a(a-1)$, one of $a$ and $a-1$ is odd, and one of $a$ and $a-1$ is not divisible by $5$, so we must have $2^4 \mid a$ and $5^4 \mid a-1$ or the reverse to get a nontrivial solution. But I don't see a way to avoid the Chinese remainder theorem.

$\endgroup$
4
  • $\begingroup$ I wasn't able to understand. Could you explain in more simpler terms? I'm not acquainted with congruences and the Chinese remainder theorem. $\endgroup$ Mar 29, 2017 at 2:11
  • $\begingroup$ It's not true that a quadratic equation has exactly two solutions mod any prime power...there could be less than two solutions (e.g. $x^2=2$ mod $4$) or more than two solutions (e.g. $x^2=0$ mod $9$). You need to use something more specific about $a^2=a$. $\endgroup$ Mar 29, 2017 at 2:11
  • $\begingroup$ @EricWofsey Thank you; hopefully I fixed it in a way that won't embarrass my undergrad-knowing-number-theory past self. Of course, now the argument is even more technical. $\endgroup$ Mar 29, 2017 at 2:19
  • $\begingroup$ Instead of using Hensel's lemma, you can say that $a$ and $a-1$ are relatively prime, so only one can contribute powers of $p$. $\endgroup$ Mar 29, 2017 at 2:25
4
$\begingroup$

In addition to only one of $a$ and $a-1$ being even, you can also say that only one of them is divisible by $5$. It follows that one of them must be divisible by $5^4$, and the other must be divisible by $2^4$ (you can't have one of them divisible by both $2^4$ and $5^4$ because then $a$ could not have four digits). It is not too bad to check all possible 4-digit multiples of $5^4=625$ (and in fact, you only need to check such multiples that are odd). For each such multiple $n$, you want to check whether $n\pm 1$ is divisible by $2^4$ (if $n+1$ is, then $n+1$ can be $a$, and if $n-1$ is, then $n$ can be $a$).

You can further greatly reduce the amount of work you need to do with a little modular arithmetic. Note that $625\equiv 1\pmod{16}$, so $625k\equiv k\pmod{16}$ for any integer $k$. So if you want $n=625k$ to be either $1$ more or $1$ less than a multiple of $16$, then $k$ needs to be $\pm 1$ mod $16$. The values of $k$ that give 4-digit numbers are $2\leq k\leq 15$, and so the only one that works is $k=15$. This gives $n=625\cdot 15=9375$, which is $1$ less than a multiple of $16$, so the value of $a$ you want is $n+1=9376$.

$\endgroup$
1
  • $\begingroup$ Well, I feel really stupid now. :) $\endgroup$ Mar 29, 2017 at 2:25
0
$\begingroup$

$a$ and $a^2$ have the same last four digits. So, $a^2-a$ is divisible by $10,000$. $$a(a-1)=10,000k=16*625k----(Eq.1)$$ Now, $a$ and $a^2$ have same last digit only if a ends with $0, 1, 5$ or $6$. $a$ can't end with $0$ as squaring it will give double the zeroes and $a^2$ won't have same last four digits.
For example, if $a$ ends with $10$, $a^2$ ends with $100$. Thus, this is not possible.
Say $a$ ends with 1, $$a=10x+1$$ $$a^2=10x^2+20x+1$$ Thus, they will differ in second last digit. (From the equation, ten's digit for $a$ is $x$ and for $a^2$ is $2x$.)
So, only possible solutions are if $a$ ends with $5$ or $6$.
From Eq. 1 we get two cases,

  1. $a=625x$ and $a-1=16y$, $625x=16y+1$
  2. $a=16y$ and $a-1=16y$, $625x=16y+1$

So, $625$ is divisible by $16$ with remainder $1$ or $-1$.
Now, $$625\equiv1(\mod16)$$ $$625x\equiv x(\mod16)$$ Hence, solution is $x=15$, which follows then 2nd Case. $$625*15=9375=16*586-1$$ $\therefore a=16y=16*586=9376$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.