A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • one year ago

Find all primitive roots of 41 and 82.

  • This Question is Closed
  1. misssunshinexxoxo
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    This should help https://answers.yahoo.com/question/index?qid=20150407193751AAnlAo6

  2. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    If you knew that 41 is a prime number, has no integer factors and that this number will divide into 82, would that help?

  3. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Is there a formula that would help me find the roots? @robtobey

  4. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    It is easy to find all the primitive roots after finding one primitive root

  5. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    If \(n\) has a primitive root, then it has exactly \(\phi(\phi(n))\) primitive roots. These can be found trivially by using any known primitive root.

  6. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    So you may try finding one primitive root by trial and error

  7. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @ganeshie8 Would you please show me an example.

  8. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    Lets work primitive roots of 41

  9. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    \(\phi(41) = 40\), so if \(a\) is a primitive root, then the order of \(a\) must be \(40\)

  10. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    So there are 16 primitive roots

  11. UsukiDoll
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    can we not post links to yahoo answers? What is the point? thanks.

  12. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    There is no known analytic method for finding a primitive root. Once you find one primitive root, there is an easy way to find all other primitive roots. So lets go ahead and find one primitive root by work each integer : \(\large 2\) : \(2^{20} \equiv (2^5)^4\equiv (-9)^4 \equiv 81^2\equiv (-1)^2\equiv 1 \pmod{41}\) That means the order of \(2\) must be \(\le 20\). so \(2\) cannot be a primitive root of \(41\)

  13. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    \(\large 3\) : \(3^8 \equiv 81^2 \equiv 1 \pmod{41}\) so this is a fail too

  14. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    \(\large 5\) : \(5^{20} \equiv (5^5)^4 \equiv 9^4 \equiv 81^2 \equiv 1 \pmod{41}\) so this is a fail too

  15. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    \(\large 6\) : \(6^{20} \equiv (6^2)^{10} \equiv (-5)^{10} \equiv 9^2 \equiv \color{red}{-1} \pmod{41}\) Also \(6^{8} \equiv (6^2)^4 \equiv (-5)^4 \equiv \color{red}{10} \pmod{41}\) so we got lucky just now, \(6\) is a primitive root of \(41\). we can go use this to find all other primitive roots

  16. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    see if everything makes sense so far, all we did is tested each interger successively for primitive root

  17. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    And yes there are exactly \(\phi(\phi(41)) = 16\) incongruent primitive roots for \(41\)

  18. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Then how would we use 6 to find the rest @ganeshie8

  19. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    Since \(6\) is a primitive root of \(41\), any coprime intger is congruent to an integer of form \(6^{k}\), where \(1\le k\le 30\). You must be knowing that the order of \(6^k\) is given by \[\dfrac{41}{\gcd(k,~40)}\] This will equal \(41\) if and only if \(\gcd(k, 40)=1\). so \(k \in\{1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39\}\) and the corresponding primitive roots are \(\{6^{1},6^{3},6^{7},6^{9},6^{11},6^{13},6^{17},6^{19},6^{21},6^{23},6^{27},6^{29},6^{31},6^{33},6^{37},6^{39}\}\) you may reduce them under mod 41 if you wish

  20. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I think I can follow your steps to get for 82. Thanks @ganeshie8

  21. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    Yw, as you can see almost all the effort was spent finding one primitive root, once you know one primitive root, generating the remaining is trivial.

  22. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.