# Proof that $gcd(n, p-1) > 1$

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

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

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