Find Primitive Root Modulo 125 - The Easier Way

[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

 

[Hurkyl]

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.

 

[shmoe]

Most numbers are primitive roots, aren't they?

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.

 

[pivoxa15]

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.

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

Thanks

 

[shmoe]

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

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.

 

[CarlB]

Anyone know a way apart from trial and error?

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

 

[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?

 

[Hurkyl]

Try proving the contrapositive.

 

[shmoe]

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?

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?

 

[shmoe]

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

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.