Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Primitive Roots helping please

  1. Dec 13, 2009 #1
    Please prove that if x is quadratic nonResidue modulo 109 and x also cubic nonresidue modulo 109 than x is guaranteed to be primitive root modulo 109 thanks you very much
  2. jcsd
  3. Dec 13, 2009 #2
    You have to look at the multiplicative group = 108 elements. Then check out the factors.
  4. Dec 13, 2009 #3
    What is this gorup? This is a number theory question not a group question? Can you show it with the number theory ? What is this group?
  5. Dec 13, 2009 #4
    It factors as 1 + 2^2*3^3 i know that
  6. Dec 13, 2009 #5
    However, 0 is not included under multiplication, so there are only 108 elements. This comes under Fermat's Little Theorem: [tex]a^{p-1} \equiv 1 \bmod p. [/tex] In this case the prime is 109.

    Now, while you may not understand group theory, I am going to quote a theorem of LaGrange: The order of the element divides the order of the group.

    Which is this case means that an element either requires the power of 108 (primitative root) or it requires a divisor of that number.

    Consider in the above we have the case that, the smallest power for a given a is 5, which does not divide 108, then [tex]a^5 \equiv 1 \bmod 108 [/tex] Well then since a^5 works, if we multiply this by 21, it should also work, and since 108 works then:

    [tex]a^{105}\equiv a^{108} \equiv 1 Mod 109 [/tex], which after division tells that some element we thought required the power of five, need only be cubed to become 1. A contradiction. (Of course, this could be carried on further considering 2x5-3x3 =1.)
    Last edited: Dec 14, 2009
  7. Dec 14, 2009 #6
    That seems like it has nothing to do with problem. where does 105 come in. No group,s no lagrange's it should be proven using number theory
  8. Dec 14, 2009 #7
    If we take a case like 5, which would not divide 108 and argue that this is the smallest power such that a becomes 1: [tex]a^5\equiv 1\bmod 109 [/tex] Then since its value is one, raising it to the 21st power should still give one. That gives then [tex]a^{105}\equiv 1\bmod 109 [/tex]

    But, since we know in all cases a^108 is 1 modulo 109, we have [tex]a^{105}\equiv a^{108} \bmod 109 [/tex]

    So dividing out by a^105 gives [tex]a^3\equiv 1 \bmod 109 [/tex], which gives a contradiction. In fact, carrying on in this way we could show that a^1 is congruent to 1 mod 109.

    What is the reason for the above? To show that the order of the element (the smallest power to make 1) must be a divisor of 108. That no element, for example, is of order 5.
    Last edited: Dec 14, 2009
  9. Dec 14, 2009 #8
    Well of course we know that it a divisor of 108, this is trivial fact no? It's not trivial to show that a^6 ~= 1 or a^4 ~= 1 or a^36 ~=1
  10. Dec 14, 2009 #9
    You can call it a trival fact if you like, but look at the original question below:

  11. Dec 14, 2009 #10
    Maybe you misunderstand? It is trivial that the order of a must divide phi(109). Great so then we have to consider the cases {a, a^2, a^3, a^4, a^6, a^9, a^12, a^18, a^36, a^54} only, I kniw that
  12. Dec 14, 2009 #11
    You are correct! There is another aspect to this problem. Take a primitive root and consider all its powers: a, a^2, a^3......a^108 = 1. Now the powers of a that are relatively prime is phi(108) = 36. These are all primitive roots.

    Fortunately, there is a now a very simple answer. If we go ahead and count all the powers of a that contain 2, they can be eliminated, and similarly the powers of 3. But there is overlap,namely the powers of 6, which are counted twice. Carrying out these simple calculations will tell you along with counting the primitive roots, that 108 cases are accounted for.
  13. Dec 14, 2009 #12
    i don't know how you can automatically say that. we kniw a^54 ~=1 by euler's criterion. so say a^2 = 1, then if you multiple out a^2 27 times you would get a^54 is 1 is rthat right?
  14. Dec 14, 2009 #13
    If a^2 congruent to 1 Mod 108, then a^54 congruent to 1 Mod 108, yes.

    What is important is that b^2 is congruent to a^54, or a^54 is a quadratic residue. Anything that is a quadratic residue will be congruent to 1 at the 54th power.
    Last edited: Dec 14, 2009
  15. Dec 14, 2009 #14
    i do not get it. what is b? what i meants was say a^2 = 1 then a^2*a^2*...*a^2 = 1 but that' can not happen because we knows a^54 = -1 i dont see what the b is and we are not given a^54 is not a quad res just that a is
  16. Dec 14, 2009 #15
    I have used a in more than one way. However, a^54 is a quadratic residue because we have a b=a^27.

    WHat I am using above is an "a" that is a primitative root. Then all the powers of a are different, some of which are primitative roots, but others are not. In any case an even power is a quadratic residue.
    Last edited: Dec 14, 2009
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook