3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ – Quintofron May 12 '13 at 15:28
  • $\begingroup$ $A(n)=(10^n-1)/9,p|A(n),$ so $p|9A(n)=10^n-1$ $\endgroup$ – lsr314 May 12 '13 at 15:44
  • $\begingroup$ Ah, right, I didn't notice that. Everything clear now, thanks! :) $\endgroup$ – Quintofron May 12 '13 at 16:00
1
$\begingroup$

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$

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