# Primitive roots?

1. Oct 12, 2005

### pivoxa15

How would I go about finding a number that is a primitive root modulo 125?

There definitely exists a primitive root since 5^3 =125

The problem basically comes down to finding 'a' (primitive root);
a^50 congruent to -1 (mod 125)

Anyone know a way apart from trial and error?

Thanks

2. Oct 12, 2005

### Hurkyl

Staff Emeritus
Most numbers are primitive roots, aren't they? Aside from special cases where you might have formulae, I seem to recall that trial and error is the most efficient method.

3. Oct 12, 2005

### shmoe

Less than half are here. There are phi(phi(125))=40 primitive roots here out of the phi (125)=100 candidates. (phi being the usual Euler phi function)

If m is a primitive root mod 125 then it's a primitive root mod 5. This limits your search since there are only 2 primitive roots mod 5, so you have only 50 candidates to try (mod 125), and you know 40 of them work.

Alternatively, the proof that prime powers have primitive roots will help if you've seen it. It starts with x, a primitive root mod p, then shows either x or x+p is a primitive root mod p^2, and so on. So you don't have to do much searching this way.

4. Oct 12, 2005

### pivoxa15

I don't understand why I have 50 candidates to choose from? Where are the 50 candidates? Are they from 1-50?

Thanks

5. Oct 13, 2005

### shmoe

If g is a primitive root mod 125, then it's a primitive root mod 5. There are 2 options for g mod 5, either 2 or 3. If g is 2 mod 5 then g is 2, 7, 12, 17, ... or 122 mod 125, for 25 possibilities (anoter 25 possibilites for 3 mod 5).

However, the proof of existence of primitive roots for (odd) prime powers shows that if g is a primitive root of p and p^2, then it's a primitive root of p^n for all n. What I mentioned before makes finding such a g easy, find any primitive root of p, if the one you found isn't a primitive root mod p^2 as well, then add p to it and you're good.

6. Oct 13, 2005

### CarlB

If you use the right algorithm, computing a^50 mod (125) is pretty dang easy.

Here's how.

First, note that 8*125 = 1000, so if you have a calculator, you're going to work the problem out modulo 1000 and look for a result of 124, 249, 374, 499, etc.

Take a^50 = (a^5)^5^2, so compute a^5 and then keep only the bottom 3 digits. Repeat and again keep only the bottom 3 digits. Double and keep the bottom 3 digits.

Here's an example calculation, for a=42, using the calculator built into windows.

42^5 = 130,691,232
232^5 = 672,109,330,432
432^2 = 186,624.

So there you have it, as in the movie, 42 is the (well "an") answer.

The problem of finding an algorithm that locates a primitive root without explicit calculation is a very tough one. If I recall, the largest known primes are found using an algorithm that just happens to work for certain numbers.

Carl

Last edited: Oct 13, 2005
7. Oct 15, 2005

### pivoxa15

I only need to find one primitive root modular 125. So it would probably be best to show a proof of 'If g is a primitive root mod 125, then it's a primitive root mod 5'. And give a primitive root mod 5.

But I tried ages and cannot construct this proof. Anyone know how?

8. Oct 15, 2005

### Hurkyl

Staff Emeritus
Try proving the contrapositive.

9. Oct 15, 2005

### shmoe

A primitive root of 5 is not guaranteed to be a primitive root of 125, it's a necessary but not sufficient condition (of the list of 50 to try I gave, all are primitive roots mod 5 but 10 of them are not primitive roots mod 125). You can show this condition directly, use the fact that powers of g get everything mod 125, then reduce mod 5.

Did you understand what I've said about using the proof of existence of primitive roots of prime powers? Have you seen this proof?

10. Oct 15, 2005

### shmoe

I meant to comment on this earlier, this is a necessary but not sufficient condition for a to be a primitive root. e.g 32^50=-1 mod 125 but the order of 32 mod 125 is only 20. You have to check more than just the power of 50.