7
$\begingroup$

Show that if $p$ is a prime number different from 2 and 5, then it divides at least one of the elements of the set $\left \{ 1,11,111,1111,...\right \}$.

$\endgroup$
4
$\begingroup$

Expanding on my comment, here is a direct solution.

Consider the sequence $u_{n+1}=10u_n\mod p$, with $u_0=1$. It can undertake only a finite number of values, so it's periodic, with some period $k$.

You have also that $u_n=10^n\mod p$, so periodicity reads:

$$10^{n+k}\equiv10^n\pmod{p}$$

And since $p$ is coprime to $10$, you can factor out $10^n$, and

$$10^{k}\equiv1\pmod{p}$$

That is, $p$ divides $10^k-1=999\dots999$.

If the prime number $p$ is greater that $5$, you are done, by dividing by $9$. The remaining case $p=3$ divides $111$.

Notice that repetitively computing $10u_n \mod p$, with $u_0=1$, is just another way to write the long division of $1$ by $p$.

$\endgroup$
1
$\begingroup$

Let $x=0.\overline{a_1a_2a_3\dots a_n}$ be the decimal number with $n$ periodic decimals in base $10$. Then: $$10^nx=\overline{a_1a_2a_3\dots a_n}.\overline{a_1a_2a_3\dots a_n}$$ $$10^nx-x=\overline{a_1a_2a_3\dots a_n}$$ $$(10^n-1)x=\overline{a_1a_2a_3\dots a_n}$$ $$x=\dfrac{\overline{a_1a_2a_3\dots a_n}}{10^n-1}$$ From this you can see that any number $\overline{a_1a_2a_3\dots a_n}$ is divisible by $10^n-1$ iff $x$ have periodic decimals. There is no positive integer which divided by $2$ and $5$ give periodic decimal number, so for any other number it is divisible by $10^n-1$.

$\endgroup$
0
$\begingroup$

The transformation $f(x) = 10x + 1$ is invertible in $\mathbb{Z}_p$ for $p$ coprime with 10. Since $f(0) = 1$, 0 and 1 are on the same orbit. The set $\{1, 11, 111, \ldots\}$ is precisely this orbit.

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