- #1

- 2,259

- 1

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

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter pivoxa15
- Start date

- #1

- 2,259

- 1

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

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,950

- 19

- #3

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

Hurkyl said: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.

- #4

- 2,259

- 1

shmoe said: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

- #5

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

pivoxa15 said: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.

- #6

CarlB

Science Advisor

Homework Helper

- 1,231

- 25

pivoxa15 said: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

Last edited:

- #7

- 2,259

- 1

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

- #8

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,950

- 19

Try proving the contrapositive.

- #9

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

pivoxa15 said:

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?

- #10

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

pivoxa15 said: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.

Share: