Results 1 to 7 of 7

Math Help - [SOLVED] primitive roots problem

  1. #1
    Junior Member
    Joined
    Aug 2008
    Posts
    42

    [SOLVED] primitive roots problem

    The search on primitive roots got me some good info, but I can not seem to bring it together to answer this problem.

    Show that if (a,15) = 1, then a^(phi(15)/2) congruent 1(mod15) and hence 15 has no primitive roots. [Hint: Examine the congruence (mod 3) and (mod 5).]

    I am unsure of how to integrate the hint into the problem.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Proggy View Post
    The search on primitive roots got me some good info, but I can not seem to bring it together to answer this problem.

    Show that if (a,15) = 1, then a^(phi(15)/2) congruent 1(mod15) and hence 15 has no primitive roots. [Hint: Examine the congruence (mod 3) and (mod 5).]

    I am unsure of how to integrate the hint into the problem.
    We know that a^8 \equiv 1 ~ (15).
    Thus, a^8 \equiv 1 ~ (3) and a^8 \equiv 1 ~ (5).
    Thus, (a^4 - 1)(a^4 + 1)\equiv 0 ~ (3) and (a^4 - 1)(a^4+1) \equiv 0 ~ (5).

    Look at the first congruence.
    It means a^4 \equiv 1 ~ (3) or a^4 \equiv -1  ~ (3).
    But the first one is true and second one is false because a^2 \equiv 1 ~ (3).
    Thus, a^4 \equiv 1 ~ (3).

    Look at second congruence.
    Thus, a^4 \equiv 1 ~ (3) or a^4 \equiv -1 ~ (3).
    But the first one is true and second one is false because a^4 \equiv 1 ~ (5).
    Thus, a^4 \equiv 1 ~ (5).

    Since \gcd(3,5)=1 it means a^4 \equiv 1 ~ (15).
    Now 4 = \phi(15)/2.
    This means it cannot have primitive roots.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2008
    Posts
    42
    Quote Originally Posted by ThePerfectHacker View Post
    a^4 \equiv 1 ~ (3) or a^4 \equiv -1 ~ (3).
    But the first one is true and second one is false because a^2 \equiv 1 ~ (3).
    Thus, a^4 \equiv 1 ~ (3).
    Okay, at one point earlier I had gotten to the +/-1 step, but I was not sure how to eliminate the negative. It just is not sinking in. What makes a^2 congruent to 1? Are you simply taking the square root of both sides and can not take the square root of a negative number, so it is therefore invalid? That seems too simple.


    Quote Originally Posted by ThePerfectHacker View Post
    Since \gcd(3,5)=1 it means a^4 \equiv 1 ~ (15).
    Now 4 = \phi(15)/2.
    Where does this last step come from? I can not seem to find a theorem or equation that makes that connection. Thanks for the guidance TPH!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Proggy View Post
    Okay, at one point earlier I had gotten to the +/-1 step, but I was not sure how to eliminate the negative. It just is not sinking in. What makes a^2 congruent to 1? Are you simply taking the square root of both sides and can not take the square root of a negative number, so it is therefore invalid? That seems too simple.
    That is just Fermat's theorem, if \gcd(a,p)=1 then a^{p-1} \equiv 1 ~ (p).



    Where does this last step come from? I can not seem to find a theorem or equation that makes that connection. Thanks for the guidance TPH!
    If p| N and q|N and \gcd(p,q)=1 then pq|N.
    Can you see it now ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Aug 2008
    Posts
    42
    Quote Originally Posted by ThePerfectHacker View Post
    That is just Fermat's theorem, if \gcd(a,p)=1 then a^{p-1} \equiv 1 ~ (p).




    If p| N and q|N and \gcd(p,q)=1 then pq|N.
    Can you see it now ?
    gah, I just smacked myself on the forehead on the Fermat's theorem miss!

    But either my question was not clear or I still do not see the second one. What i am asking is how you went from this:
    Since \gcd(3,5)=1 it means a^4 \equiv 1 ~ (15).
    to this
    Now 4 = \phi(15)/2.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Proggy View Post
    But either my question was not clear or I still do not see the second one. What i am asking is how you went from this:
    Since \gcd(3,5)=1 it means a^4 \equiv 1 ~ (15).
    to this
    Now 4 = \phi(15)/2.
    a^4 \equiv 1 ~ (3) means 3 | (a^4 - 1).
    a^4 \equiv 1 ~ (5) means 5 | (a^4 - 1).
    Since \gcd(3,5)=1 it means 15| (a^4-1).
    Thus, a^4 \equiv 1 ~ (15).

    Finally \phi(15) = 8 thus 4 = \phi(15)/2.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Aug 2008
    Posts
    42
    i was copying this down in my notes just now and as i said it out loud as I wrote, I realized that last line was not a formula at all. It just happened to be what it worked out to be for this problem. So yes, I get it now, thanks so much for the help on this one. Several problems spawn off of this one, but I understand it now and should be able to do those. Thanks again TPH. And I was reading the latex forum in between your posts so I can ask my questions in nicer format from now on! I do have another question I will post shortly. 13 of 16 lessons done, really getting thought-provoking at this point.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: December 18th 2009, 12:48 PM
  2. Primitive roots mod p
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 11th 2009, 02:03 PM
  3. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 15th 2008, 06:58 PM
  4. [SOLVED] another primitive root problem
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: August 25th 2008, 06:55 AM
  5. problem in primitive roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 14th 2008, 07:14 PM

Search Tags


/mathhelpforum @mathhelpforum