Exercise 2.8.34 (If $p \mid \phi(m), p
mid m$, then $q \equiv 1 \pmod p$ for some prime factor of $m$)

Question

Show that if $p \mid \phi(m)$ and $p 
mid m$ then there is at least one prime factor $q$ of $m$ such that $q \equiv 1 \pmod p$.

Richard Ganaye · Accepted Answer

\begin{proof} 
Write $m= q_1^{a_1}\cdots q_l^{a_l}$ the decomposition of $m$ in prime factors, where $a_i \geq 1$ for all indices $i$. Since $p \mid \phi(m)$ and $p 
mid m$,
$$p \mid q_1^{a_1 - 1}(q_1 - 1)\cdots q_l^{a_l - 1}(q_l - 1), \qquad p 
mid q_i \ (1 \leq i  \leq l).$$
Therefore
$$p \mid (q_1 - 1)\cdots (q_l - 1).$$
Since $p$ is a prime, $ p \mid q_i - 1$ for some index $i \in [\![1,l]\!]$. So there is at least one prime factor $q$ of $m$ such that $q \equiv 1 \pmod p$.
\end{proof}

Exercise 2.8.34 (If $p \mid \phi(m), p \nmid m$, then $q \equiv 1 \pmod p$ for some prime factor of $m$)

Answers

Comments

Exercise 2.8.34 (If $p \mid \phi(m), p \nmid m$, then $q \equiv 1 \pmod p$ for some prime factor of $m$)

Answers

Comments

Add answer