Show that if $\displaystyle p\mid\phi(m)$ and $\displaystyle p$ doesn't divide $\displaystyle m$ then there is at least one prime
factor $\displaystyle q$ of $\displaystyle m$ such that $\displaystyle q \equiv 1 (\mbox{mod p})$.
Hint: $\displaystyle If\,\,m=p_i^{a_1}\cdot...\cdot p_n^{a_n}=\prod\limits_{i=1}^np_i^{a_i}\,,\,\,p_i\ ,\,primes\,,\,\,0< a_i\in \mathbb{N}\,,\,\,then\,\,\phi(m)$ $\displaystyle =\prod\limits_{i=1}^np_i^{a_i}\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdot...\cdot \left(1-\frac{1}{p_n}\right)$ $\displaystyle =\prod_{i=1}^np_i^{a_i-1}\prod\limits_{i=1}^n(p_i-1)$
Tonio
$\displaystyle q \mbox{ would be of the form} = p_{i}$
$\displaystyle p \mbox{ would be of the form} = p_{i}^{a_{i}-1}$
$\displaystyle p_{i}^{a_{i}-1} \mbox{won't divide m if} a_{i}=0$
so $\displaystyle p \mbox{would be of the form} p_{i}^{-1}$
How would you link p and q together so that q divides (p-1)? Thanks.
-------------------------------------------------------------------
Edit:
Would this be a good proof?
Using $\displaystyle \phi(m)= \prod_{i=1}^np_i^{a_i-1}\prod\limits_{i=1}^n(p_i-1) $
$\displaystyle p \mid \phi(m), \mbox{so } p \mid p_{i}^{a_{j}-1} \mbox{or } p \mid p_{i}-1$
$\displaystyle p \nmid p_{i}^{a_{j}-1} $ because otherwise $\displaystyle p \mid p_{i}, \mbox{or } p \mid m$, which contradicts with the given conditions.
$\displaystyle p \mid p_{i}-1$ for some i between 0 and n because it is the only possible way that p divides $\displaystyle \phi(m)$ but not m.
If q is a factor of m, then we can let q be $\displaystyle p_{i}$ for some i between 0 and n.
since $\displaystyle p \mid p_{i}-1$, then we can substitute $\displaystyle p_{i}$ with q to get
$\displaystyle p\mid q - 1$, which can be expressed as $\displaystyle q \equiv 1 \mbox{(mod p)}$