Congruence proof

Printable View

November 9th 2009, 06:52 PM
comssa

Congruence proof

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})$ .
November 9th 2009, 08:10 PM
tonio

Quote:

Originally Posted by comssa

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
November 10th 2009, 10:03 AM
comssa

$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)}$