Facebook Page
Twitter
RSS
+ Reply to Thread
Results 1 to 5 of 5
  1. MHB Apprentice

    Status
    Offline
    Join Date
    Oct 2013
    Posts
    8
    Thanks
    6 times
    Thanked
    2 times
    #1
    How can I find a primitive root modulo 169?
    I found the primitive roots mod 13 by testing 2, and then concluding that any 2^k with (k, 12)=1 would do. So that gave me 2, 6, 7 and 11. But modulo 13 I have no idea how to start.. Iím sure thereís a smarter way than trying 2^the orders that divide phi(13^2)..?.

  2. MHB Oldtimer
    MHB Site Helper
    MHB Math Scholar
    Opalg's Avatar
    Status
    Offline
    Join Date
    Feb 2012
    Location
    Leeds, UK
    Posts
    2,092
    Thanks
    704 times
    Thanked
    5,899 times
    Thank/Post
    2.820
    Awards
    Graduate POTW Award (2016)  

MHB Analysis Award (2016)  

Graduate POTW Award (2015)  

Graduate POTW Award (Jul-Dec 2013)  

MHB Pre-University Math Award (Jul-Dec 2013)
    #2
    Quote Originally Posted by tda120 View Post
    How can I find a primitive root modulo 169?
    I found the primitive roots mod 13 by testing 2, and then concluding that any 2^k with (k, 12)=1 would do. So that gave me 2, 6, 7 and 11. But modulo 13 I have no idea how to start.. Iím sure thereís a smarter way than trying 2^the orders that divide phi(13^2)..?.
    Hi tda, and welcome to MHB. You might be interested in , which tells you that the answer to your question is either $2$ or $2+13=15$. That still leaves you with the work of testing to see if $2$ works. If it does not, then $15$ does.

  3. MHB Journeyman
    MHB Math Helper
    mathbalarka's Avatar
    Status
    Offline
    Join Date
    Mar 2013
    Location
    West Bengal, India
    Posts
    573
    Thanks
    699 times
    Thanked
    1,378 time
    Thank/Post
    2.405
    Trophies
    8 Highscores
    Awards
    Graduate POTW Award (Jul-Dec 2013)
    #3
    Quote Originally Posted by tda120
    How can I find a primitive root modulo 169?
    There is no simple method. You can cobble up together some basic theories on primitive roots, find a bit of a rough upperbound (although none is known to be useful for small cases) and some modular exponentiation to get a fast enough algorithm.

    As Opalg there indicated, that either 2 or 15 is primitive root modulo 169, can easily be found for this case. Try proving the former and then the later if it doesn't work.

  4. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    I like Serena's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    6,029
    Thanks
    4,067 times
    Thanked
    11,384 times
    Thank/Post
    1.888
    Awards
    MHB Model Helper Award (2016)  

MHB Best Ideas (2016)  

MHB LaTeX Award (2016)  

MHB Calculus Award (2014)  

MHB Discrete Mathematics Award (Jul-Dec 2013)
    #4
    Quote Originally Posted by tda120 View Post
    How can I find a primitive root modulo 169?
    I found the primitive roots mod 13 by testing 2, and then concluding that any 2^k with (k, 12)=1 would do. So that gave me 2, 6, 7 and 11. But modulo 13 I have no idea how to start.. Iím sure thereís a smarter way than trying 2^the orders that divide phi(13^2)..?.
    You don't have to check all the orders that divide $\phi(13^2)$.
    It suffices to check each of the orders that are $\phi(13^2)$ divided by one of the distinct primes it contains.

    In your case:
    $$\phi(13^2)=2^2\cdot 3 \cdot 13$$
    So the orders to verify are:
    $$2\cdot 3 \cdot 13,\quad 2^2 \cdot 13, \quad 2^2\cdot 3$$

  5. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    I like Serena's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    6,029
    Thanks
    4,067 times
    Thanked
    11,384 times
    Thank/Post
    1.888
    Awards
    MHB Model Helper Award (2016)  

MHB Best Ideas (2016)  

MHB LaTeX Award (2016)  

MHB Calculus Award (2014)  

MHB Discrete Mathematics Award (Jul-Dec 2013)
    #5
    Quote Originally Posted by Opalg View Post
    Hi tda, and welcome to MHB. You might be interested in , which tells you that the answer to your question is either $2$ or $2+13=15$. That still leaves you with the work of testing to see if $2$ works. If it does not, then $15$ does.
    Nice!

    From that link we also get that since 2 is a primitive root mod 13, it follows that the order of 2 mod 169 is either (13-1) or 13(13-1).
    So if $2^{13-1} \not\equiv 1 \pmod{169}$ that means that 2 has to be a primitive root mod 169. Or otherwise 15 has to be.

    In other words, no need to check any of the other powers.

Similar Threads

  1. Primitive root challenge
    By Poirot in forum Challenge Questions and Puzzles
    Replies: 3
    Last Post: April 27th, 2013, 08:26
  2. Diophantine equation, modulo
    By Petrus in forum Number Theory
    Replies: 6
    Last Post: April 22nd, 2013, 20:46
  3. [SOLVED] Primitive root
    By Poirot in forum Number Theory
    Replies: 3
    Last Post: April 12th, 2013, 15:46
  4. Replies: 2
    Last Post: January 9th, 2013, 04:29
  5. [SOLVED] square root in Q(root 2) means its in Z[root 2]
    By caffeinemachine in forum Linear and Abstract Algebra
    Replies: 2
    Last Post: June 28th, 2012, 12:28

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards