# A property of a prime divisor of a number consisting of 1s

For $n>0$ let $A(n) = \underbrace{111 \ldots 11}_{n}$. Prove that if $A(n)$ is divisible by a prime number $p>3$, then $\gcd(n, p-1) > 1$.

It is no huge discovery that if $n$ is even, then $2$ is a common divisor of $n$ and $p-1$, thus the implication holds. I don't know how to justify the general case though, so I would appreciate some hints.

If $10^n\equiv 1 \pmod p,(n,p-1)=1,(p,10)=1$,then there exist integer $x,y$, satisfies $xn+y(p-1)=1,$ hence $$10^1=10^{xn+y(p-1)}=(10^n)^x\cdot(10^{p-1})^y\equiv1^x\cdot 1^y=1 \pmod p$$ We get $p=3.$

• So basically we're trying to carry out a proof by contradiction here. $p = 5$ doesn't divide $A(n)$ for any $n$, so we can go ahead to $p>5$, for which clearly $(p, 10) = 1$. We take $p|A(n)$ and $(n, p-1) = 1$ is our assumption. I understand the transformations that follow, but one thing is unclear to me: $10^n$ is not necessarily congruent to $1 \pmod p$. How to generalize this approach? – Quintofron May 12 '13 at 15:28
• $A(n)=(10^n-1)/9,p|A(n),$ so $p|9A(n)=10^n-1$ – lsr314 May 12 '13 at 15:44
• Ah, right, I didn't notice that. Everything clear now, thanks! :) – Quintofron May 12 '13 at 16:00

If $p(>3)$ divides $\underbrace{111 \ldots 11}_n, p$ divides $\underbrace{999\ldots 99}_n\implies p$ divides $(10^n-1)$

$\implies 10^n\equiv1\pmod p\implies ord_p{10}$ divides $n$

Again, using Fermat's Little Theorem, $10^{p-1}\equiv1\pmod p\implies ord_p{10}$ divides $p-1$

$\implies ord_p{10}$ divides $(n,p-1)$

If $(n,p-1)=1,ord_p{10}$ divides $1\implies ord_p{10}=1\implies 10^1\equiv1\pmod p\implies p$ divides $9$ which is impossible as $p>3$