# Proving the $\gcd$ is divided by $p-1$

Given $m=p^k$ where $p$ is an odd prime and $k\ge 2$. Show that $$\gcd (m-1, \phi(m)) \mid p-1$$

So I have done the following development:

$$\gcd(m-1,\phi(m)) =\gcd\left(m-1,p^{k-1}(p-1)\right) =\gcd\left(p^{k}-1,p^{k-1}(p-1)\right) =\gcd\left((p-1)(p^{k-1}+\cdots+1),(p-1)\right)$$

If I knew that $(p^{k-1} +\cdots +1)$ and $p-1$ are co-prime then we're done.

How can it be done?

• if $p=5,k=2$ then $p^1+1=6$ and $\gcd(4,6)>1$. – lulu Dec 5 '17 at 14:34
• @lulu, is that a counter-example supporting what Arthur said? – Elimination Dec 5 '17 at 14:36
• It is a counterexample to the notion that $p^{k-1}+\cdots+1$ is always co-prime with $p-1$. It is clear that $\gcd(p^k-1,p-1)$ can not exceed $p-1$. As it is obviously at least $p-1$ it must equal $p-1$. – lulu Dec 5 '17 at 14:38
• @lulu, got it - Thanks! – Elimination Dec 5 '17 at 14:42
• If you wish, you can write it as an answer – Elimination Dec 5 '17 at 14:42

It is not true that $p^{k-1}+\cdots +1$ is always co-prime to $p-1$. Indeed, taking $p=5,k=2$ gives a counterexample (more generally, for odd $p$ the parity of the sum depends on the parity of $k$ so $2$ is frequently a divisor of both).
That said, the original claim is certainly true. Indeed $\gcd\left(m-1,\varphi(m)\right)=p-1$. That follows from your expression! Obviously $p-1$ divides $\gcd((p-1)(p^{k-1}+\cdots +1,p-1)$ but as that gcd can be no greater than $p-1$ they must in fact be equal.
$S_{k-1}=\sum_{r=0}^{k-1}p^r=1+p\sum_{r=0}^{k-2}p^r$ $$\implies(S_{k-1},p)=1$$ right?
• Alright, but the end goal is $(S_{k-1}, p-1) = 1$ isn't it? – Elimination Dec 5 '17 at 14:38
$\gcd(m-1,\phi(m)) =\gcd\left(p^{k}-1,p^{k-1}(p-1)\right) =\gcd\left((p-1)(p^{k-1}+\cdots+p+1),p^{k-1}(p-1)\right) =(p-1)\gcd\left(p^{k-1}+\cdots+p+1,p^{k-1}\right) =(p-1)\cdot1$