Results 1 to 3 of 3

Math Help - Congruence proof

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

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

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    From
    In limbo
    Posts
    18
    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)}
    Last edited by comssa; November 10th 2009 at 02: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: April 4th 2011, 05:16 AM
  2. A Congruence Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 5th 2009, 10:34 AM
  3. Congruence Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 15th 2009, 07:12 AM
  4. Proof of a congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 19th 2009, 07:08 AM
  5. Proof congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 19th 2007, 10:13 AM

Search Tags


/mathhelpforum @mathhelpforum