Results 1 to 3 of 3

Thread: Congruence proof

  1. #1
    Newbie
    Joined
    Oct 2009
    From
    In limbo
    Posts
    18

    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})$.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by comssa View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    From
    In limbo
    Posts
    18
    $\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)}$
    Last edited by comssa; Nov 10th 2009 at 01:39 PM. Reason: I got an idea
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence Proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Apr 4th 2011, 04:16 AM
  2. A Congruence Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Jun 5th 2009, 09:34 AM
  3. Congruence Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 15th 2009, 06:12 AM
  4. Proof of a congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Mar 19th 2009, 06:08 AM
  5. Proof congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Nov 19th 2007, 09:13 AM

Search Tags


/mathhelpforum @mathhelpforum