# Does every prime $p \neq 2, 5$ divide at least one of $\{9, 99, 999, 9999, \dots\}$? [duplicate]

I was thinking of decimal expressions for fractions, and figured that a fraction of the form $\frac{1}{p}$ must be expressed as a repeating decimal if $p$ doesn't divide $100$. Thus, $\frac{p}{p}$ in decimal would equal $0.\overline{999\dots}$ for some number of $9$s, thus there must be some amount of $9$s such that $p | 999...$ in order for a decimal representation of $\frac{1}{p}$ to be possible.

Furthermore, the question could be rephrased to "an infinite number of" since if it divides $999\dots$ where there are $k$ nines, it also divides when there are $2k, 3k, \dots$ nines.

Is this reasoning correct? If so, this is how I thought about proving it:

We can reduce the set to $\{1, 11, 111, 1111, \dots\}$ since $p=3$ obviously works.

Let $a_k = 111\dots$ where there are $k$ ones. This satisfies the recursion $a_k = 10a_{k-1} + 1$

But I'm unsure what to do past this point (tried looking at modular cases or something but wasn't able to get anywhere). Am I on the right track at all? Is this "conjecture" even correct?

-

## marked as duplicate by Micah, Rebecca J. Stones, GEdgar, Lost1, Nick PetersonFeb 6 '14 at 2:28

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 3 Answers

$$10^{p-1} \equiv 1 \pmod p$$

-
Oh right! I forgot Fermat's little theorem. It seems reducing the set to $\{1, 11, \dots\}$ put me on the wrong track! – Soke Feb 6 '14 at 2:05

Essentially, you wish to find a $k$ such that $10^k - 1 \equiv 0 \pmod p$. This is equivalent to $10^k \equiv 1 \pmod p$. There are many reasons that such a $k$ exists: (for $p \ne 2,5$), but I'd argue the cleanest one is this:

• $\mathbb{Z}_p$ is a field, and so $(\mathbb{Z}_p)^\times$ is a group under multiplication. Since the group is finite, $10$ has finite order.
-

Even without knowledge of little Fermat you can solve this. By the pigeonhole (box) principle, the map $\rm\:k\mapsto 10^k\ (mod\ n)\:$ from $\,\Bbb N\,$ to $\rm\,\Bbb Z/n\Bbb Z\:$ is not $1$-$1,$ therefore there exist naturals $\rm\:j\!+\!k > j\:$ such that $\rm\: 10^{\,j+k}\equiv\,10^{\,j}\ (mod\ n),\$ i.e. $\rm\ n\:|\:10^j(10^k-1).$ Thus $\,(n,10)=1\,\Rightarrow\,n\mid 10^k-1\,$ follows by Euclid's Lemma.

-