Congruence proof

comssa · #1 $Old$ November 9th, 2009, 07:52 PM

Show that if $p\mid\phi(m)$ and $p$ doesn't divide $m$ then there is at least one prime
factor $q$ of $m$ such that $q \equiv 1 (\mbox{mod p})$ .

tonio · #2 $Old$ November 9th, 2009, 09:10 PM

Quote:

Originally Posted by comssa $View Post$

Show that if $p\mid\phi(m)$ and $p$ doesn't divide $m$ then there is at least one prime
factor $q$ of $m$ such that $q \equiv 1 (\mbox{mod p})$ .

Hint: $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)$ $=\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)$ $=\prod_{i=1}^np_i^{a_i-1}\prod\limits_{i=1}^n(p_i-1)$

Tonio

comssa · #3 $Old$ November 10th, 2009, 11:03 AM

$q \mbox{ would be of the form} = p_{i}$

$p \mbox{ would be of the form} = p_{i}^{a_{i}-1}$

$p_{i}^{a_{i}-1} \mbox{won't divide m if} a_{i}=0$

so $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 $\phi(m)= \prod_{i=1}^np_i^{a_i-1}\prod\limits_{i=1}^n(p_i-1)$

$p \mid \phi(m), \mbox{so } p \mid p_{i}^{a_{j}-1} \mbox{or } p \mid p_{i}-1$
$p \nmid p_{i}^{a_{j}-1}$ because otherwise $p \mid p_{i}, \mbox{or } p \mid m$ , which contradicts with the given conditions.

$p \mid p_{i}-1$ for some i between 0 and n because it is the only possible way that p divides $\phi(m)$ but not m.

If q is a factor of m, then we can let q be $p_{i}$ for some i between 0 and n.

since $p \mid p_{i}-1$ , then we can substitute $p_{i}$ with q to get
$p\mid q - 1$ , which can be expressed as $q \equiv 1 \mbox{(mod p)}$