# Thread: Primitive root modulo 169

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. Originally Posted by tda120
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. 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. Originally Posted by tda120
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.

$$\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. Originally Posted by Opalg
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.

#### Posting Permissions

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