Welcome to our community

Be a part of something great, join today!

Number Theory Primitive root modulo 169

tda120

New member
Oct 31, 2013
8
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)..?.
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,702
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 this link, 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.
 

mathbalarka

Well-known member
MHB Math Helper
Mar 22, 2013
573
tda120 said:
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.
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,774
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$$
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,774
Hi tda, and welcome to MHB. You might be interested in this link, 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.