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
    10
    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
    10
    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
    10
    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, 01:48 PM
  2. Primitive roots mod p
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 11th 2009, 03:03 PM
  3. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 15th 2008, 07:58 PM
  4. [SOLVED] another primitive root problem
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: August 25th 2008, 07:55 AM
  5. problem in primitive roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 14th 2008, 08:14 PM

Search Tags


/mathhelpforum @mathhelpforum