1
$\begingroup$

Written in a more formal way, proof that there are at the most $2$ numbers $n$ of six digits, that

$$n^2 \equiv n \mod 10^6$$

Research effort:

if $n^2 \equiv n \mod 10^6$ this means $10^6\mid n^2-n \rightarrow10^6\mid n(n-1)$

Given that $5^6\mid 10^6$ then $5^6\mid n(n-1)$ whitch means $5^6\mid n$ or $5^6\mid n-1$

Same for $2^6$, Given that $2^6\mid 10^6$ then $2^6\mid n(n-1)$ whitch means $2^6\mid n$ or $2^6\mid n-1$

By the chinese remainder theorem I got assured $4$ solutions, but I tried to solve the systems and it's not a very happy thing to do, so I think I did something wrong somewhere.

What do you think?

$\endgroup$
  • 4
    $\begingroup$ Two of the solutions are $0$ and $1$. You are looking for the other two. $\endgroup$ – Ross Millikan Mar 6 '14 at 17:12
  • $\begingroup$ Note that if you have $2^6|n$ and $5^6|n+1$ then you have also $2^6|10^6-n$ and $5^6|10^6-n-1$ giving you a second pair of consecutive numbers which will solve the problem. $\endgroup$ – Mark Bennet Mar 6 '14 at 17:28
0
$\begingroup$

If $\displaystyle2^6|(n-a)$ and $5^6|(n-a),$

$\displaystyle$ lcm$(2^6,5^6)|(n-a)$

As $(2,5)=1,(2^6,5^6)=(2,5)^6=1$

$\implies$ lcm$(2^6,5^6)=(2^6\cdot5^6)=10^6\iff n\equiv a\pmod{10^6}$

Here $a=0,1$

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