4
$\begingroup$

If $n$ is an integer not divisible by 2 or 5 then prove that there is a multiple of $n$ consisting of ones only.

I had proved this for primes using Fermat's theorem. But I can't prove it for composite numbers. Any help will be appreciated.

$\endgroup$
  • 1
    $\begingroup$ Hint: start with $a$ such that $10^a\equiv 1 \; mod(n)$ $\endgroup$ – lulu Oct 3 '15 at 15:08
  • 1
    $\begingroup$ For composites, use Euler's theorem. $\endgroup$ – Dylan Oct 3 '15 at 15:08
2
$\begingroup$

Consider the remainders when $10^1$, $10^2$, $10^3$, and so on are divided by $9|n|$. By the Pigeonhole Principle, there exist natural numbers $i$ and $j$ such that $i\lt j$ and $10^i$ and $10^j$ have the same remainder on division by $9|n|$.

It follows that $9|n|$ divides $10^{i}(10^{j-i}-1)$. Since $10^i$ and $9|n|$ are relatively prime, we conclude that $9|n|$ divides $10^{j-i}-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.