0
$\begingroup$

Using Euler’s Theorem, prove that if n is a number not divisible by 2 or 5, then n divides a number consisting of all 9’s.

If n is not a number divisible by 2 or 5, then the number $n$ is odd and does not end in a 0 or 5. These are some divisibility rules that come to mind, but what can I do with these?

$\endgroup$

2 Answers 2

1
$\begingroup$

The thing about a number consisting of all $9$'s is that it's equal to $10^k-1$, where $k$ is some positive integer. If a prime $p$ divides such a number, that means that $10^k\equiv 1\pmod{p}$. Does Euler's theorem give you any reason to think that such a $k$ exists, when $p$ is a prime other than $2$ or $5$?

$\endgroup$
1
  • $\begingroup$ maybe using 10^phi(n) tells us a prime other than 2 or 5 exists $\endgroup$ Jul 25, 2017 at 23:37
0
$\begingroup$

Theorem: (Euler) Suppose that a is relatively prime to n. Then $a^{φ(n)}≡1 (mod n)$.

Suppose now that n is divisible neither by 2 nor by 5, and let a=10. Then a and n are relatively prime, and therefore $$10^{φ(n)}≡1(modn)$$ For any k≥1, the number $10^k−1$ has decimal representation that consists only of 9's. So we have shown that if n is divisible neither by 2 nor by 5, then the number consisting of φ(n) 9's is divisible by n.

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