Results 1 to 3 of 3

Math Help - prime congruence help

  1. #1
    Newbie
    Joined
    Oct 2011
    Posts
    4

    prime congruence help

    Hey everyone, couple problems I am stuck on.

    1. Let p be an odd prime and p \equiv 3 \ mod \ 8. Show

    2^{\frac{p-1}{2}} \cdot (p-1)! \equiv 1 \ mod \ p

    2. a is an integer such that gcd(a,35)=1, show that

    a^{12} \equiv 1 \ mod \ 35

    and then deduce there exists no primitive roots modulo 35.



    I don't know how to do question 1 so need a lot of help for this one.

    For question 2, a must be coprime to 35, so is it good enough to just say a=2 and show 2^{12} \equiv 1 \ mod \ 35 ?
    And how do I do the second part of q2?

    Thanks all for your help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,971
    Thanks
    1121

    Re: prime congruence help

    Surely there are more numbers than just "2" that are coprime to 35?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    Re: prime congruence help

    since φ(35) = φ(5)φ(7) = 24, you must show that no integer a such that gcd(a,35) = 1 has multiplicative order 24 (mod 35).

    it suffices to check the list of such integers between 1 and 34, namely:

    {1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23,24,26,27 ,29,31,32,33,34}.

    you don't have to check every power, just 2,3,4,6,8, and 12 (if none of those powers are congruent to 1, you've found a primitive root).

    if you save your calculations, you can save some time, by noticing that:

    <2> = {2,4,8,16,32,29,23,11,22,9,18,1}, so none of these have order 24, since they are all powers of 2 (mod 35).

    so, for example: 29^12 = (2^5)^12 = (2^12)^5 = 1^5 = 1 (mod 35).

    for your first question, do you know wilson's theorem?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime numbers and congruence equations.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 21st 2010, 11:54 PM
  2. Finding remainder in non-prime congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 4th 2009, 05:38 PM
  3. Prime Power Congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 24th 2009, 08:44 PM
  4. Prime Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 15th 2008, 02:06 PM
  5. Prime Numbers Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 28th 2007, 04:43 AM

Search Tags


/mathhelpforum @mathhelpforum