# Math Help - Prove that GCD>1

1. ## Prove that GCD>1

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

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

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

We can now prove this for prime powers. If $p^k|a^{p^k} -1$ it means $p|(a^{p^{k-1}})^p - 1$ using what we just proved it means $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 $p|(a-1)$. Thus, certainly $\gcd(p^k,a-1)>1$.

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

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

The last paragraph easily shows how we can generalize this argument for $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 $n$ as a product of distinct primes and prime powers. This is the final step that remains.