1
$\begingroup$

Let $F(n) = \underbrace{111..11}_{n \text{times}}$
Proof that if $p|F(n)$ then $gcd(n, p-1) > 1$
(p - prime and $p>3$)

My approach

If $n$ is even it is true because $p-1$ is even too so $$gcd(n, p-1) \ge 2 > 1 $$

But I completely don't know how to start with odd numbers...

Example

$n=5$ $F(n) = 11111 = 271\cdot 41$ $gcd(5,270) > 0$ $gcd(5,40) > 0$

Update:

From answer I know that $$ 10^{n}\equiv 10^{p-1}\equiv 1\mod p $$ so $$gcd(n,p-1) = gcd(log_{10}(pk+1), log_{10}(pt+1)) \text{ for some k,t} $$ I am trying to show that it implies thesis...

$\endgroup$
5
$\begingroup$

$9F(n)=10^n-1$, so if $p\mid F(n)$ then $10^n\equiv 1\pmod p$, that is, $n$ is a multiple of the order of $10$ in $\Bbb Z_p^\times$, which is a non trivial divisor of $p-1$.

$\endgroup$
  • 1
    $\begingroup$ Just to put it in other words: $10^{n}\equiv 10^{p-1}\equiv 1\mod p$ So, $ord_p(10)$ divides $(n,p-1)$. $\endgroup$ – Julian Mejia May 14 at 17:04
  • $\begingroup$ what is $ord_p(10)$? I didn't have orders and groups on my lecture :( $\endgroup$ – Witalij May 14 at 17:16
  • $\begingroup$ and how you got $10^{p-1}\equiv 1\mod p$? $\endgroup$ – Witalij May 14 at 17:30
  • $\begingroup$ @Witalij If $p$ is neither $2$ or $5$, then $10^{p-1} \equiv 1 \pmod p$ due to Fermat's little theorem. $\endgroup$ – John Omielan May 15 at 2:47
  • $\begingroup$ Can it be solved without informations about $ord_p(10)$? $\endgroup$ – Witalij May 15 at 10:06

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.