# Congruence proof

• Nov 9th 2009, 06:52 PM
comssa
Congruence proof
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})$.
• Nov 9th 2009, 08:10 PM
tonio
Quote:

Originally Posted by comssa
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
• Nov 10th 2009, 10:03 AM
comssa
$\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)}$