1. ## Prove that GCD>1

We know that $\displaystyle n>1$ and $\displaystyle n|a^n-1$ ($\displaystyle a,n\in\mathbb{Z}^+$). Prove that $\displaystyle \left(a-1;n\right)>1$.

2. Originally Posted by james_bond
We know that $\displaystyle n>1$ and $\displaystyle n|a^n-1$ ($\displaystyle a,n\in\mathbb{Z}^+$). Prove that $\displaystyle \left(a-1;n\right)>1$.
Here is a start. First now that $\displaystyle \gcd(a,n)=1$. And it is also safe to say that $\displaystyle n$ is odd.

First, start easy, say $\displaystyle n=p$, a prime. Then $\displaystyle a^p \equiv 1( \bmod p)$, but $\displaystyle a^{p-1}\equiv 1(\bmod p)$ by Fermat's little theorem. Thus, $\displaystyle a^p \equiv a^{p-1}(\bmod p) \implies a \equiv 1(\bmod p)\implies p|(a-1)$. Thus, certainly $\displaystyle \gcd(p,a-1)>1$.

We can now prove this for prime powers. If $\displaystyle p^k|a^{p^k} -1$ it means $\displaystyle p|(a^{p^{k-1}})^p - 1$ using what we just proved it means $\displaystyle p|a^{p^{k-1}}-1\implies p|(a^{p^{k-2}})^p - 1\implies p|a^{p^{k-2}}-1$, continuing we arrive at $\displaystyle p|(a-1)$. Thus, certainly $\displaystyle \gcd(p^k,a-1)>1$.

We will show now that if $\displaystyle n=pq$ for two distinct primes then it works too, more specifically $\displaystyle p|a-1$ or $\displaystyle q|a-1$. Say, $\displaystyle pq|a^{pq} - 1$. Then it means $\displaystyle p|(a^q)^p -1 \mbox{ and }q|(a^p)^q - 1$. Using the above results it means $\displaystyle a^q\equiv 1(\bmod p)$ and $\displaystyle a^p\equiv 1(\bmod q)$. If the order of $\displaystyle a$ mod $\displaystyle p$ is $\displaystyle 1$ the argument is complete, similarly if the order of $\displaystyle a$ mod $\displaystyle q$ is $\displaystyle 1$ the argument is complete. Thus, we can assume the order of $\displaystyle a$ mod $\displaystyle p$ and $\displaystyle q$ is not $\displaystyle 1$. But since $\displaystyle a^q \equiv 1(\bmod p)$ it means the order must be $\displaystyle q$ (since the order divides $\displaystyle q$). Similarly since $\displaystyle a^p \equiv 1(\bmod q)$ it means the order of $\displaystyle a$ must be $\displaystyle p$. But since $\displaystyle a^{p-1}\equiv 1(\bmod p)$ and $\displaystyle a^{q-1}\equiv 1(\bmod q)$ it means (by properties of orders) that $\displaystyle p|q-1 \mbox{ and }q|p-1$. But this is impossible, for then $\displaystyle p\leq q-1$ and $\displaystyle q\leq p-1$ which would imply $\displaystyle p\leq q-1\leq p-2$ which is impossible.

Now we can generalize this for $\displaystyle n=pqr$ for three distinct primes. WLOG say $\displaystyle p>q>r$. If $\displaystyle pqr|a^{pqr} - 1$ then $\displaystyle p|(a^{qr})^p -1 \mbox{ and }qr|(a^p)^{qr} -1$. By using the above results it means $\displaystyle a^{qr} \equiv 1(\bmod p)$ and $\displaystyle a^p\equiv 1(\bmod q)\mbox{ or }a^p\equiv 1(\bmod r)$. If the order of $\displaystyle a$ mod $\displaystyle p$ or $\displaystyle q$ or $\displaystyle r$ is $\displaystyle 1$ then the proof is complete, i.e. $\displaystyle p|(a-1)\mbox{ or }q|(a-1)\mbox{ or }r|(a-1)$. Thus it is safe to assume that the order of $\displaystyle a$ mod any of those primes is greater than $\displaystyle 1$. Thus, the order of $\displaystyle a$ mod $\displaystyle r$ or $\displaystyle q$ is $\displaystyle p$, WLOG say $\displaystyle q$, but then $\displaystyle p|q-1\implies p\leq q-1\implies p<q$ which is impossible since we said $\displaystyle p>q$.

The last paragraph easily shows how we can generalize this argument for $\displaystyle n=p_1p_2...p_k$ for distinct primes by using induction.

Thus, now we know it works for prime powers and distinct primes. We can think of $\displaystyle n$ as a product of distinct primes and prime powers. This is the final step that remains.