MHB Finding Primitive Roots Modulo 169: Is There a Smarter Way?

[tda1201]

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]

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]

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.

 

[I like Serena]

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$$

 

[I like Serena]

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.