0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ if $p=5,k=2$ then $p^1+1=6$ and $\gcd(4,6)>1$. $\endgroup$ – lulu Dec 5 '17 at 14:34
  • $\begingroup$ @lulu, is that a counter-example supporting what Arthur said? $\endgroup$ – Elimination Dec 5 '17 at 14:36
  • 2
    $\begingroup$ 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$. $\endgroup$ – lulu Dec 5 '17 at 14:38
  • $\begingroup$ @lulu, got it - Thanks! $\endgroup$ – Elimination Dec 5 '17 at 14:42
  • $\begingroup$ If you wish, you can write it as an answer $\endgroup$ – Elimination Dec 5 '17 at 14:42
1
$\begingroup$

As requested in the comments.

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Alright, but the end goal is $(S_{k-1}, p-1) = 1$ isn't it? $\endgroup$ – Elimination Dec 5 '17 at 14:38
1
$\begingroup$

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

$\endgroup$

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.