- #1

pivoxa15

- 2,259

- 1

Can a number have more than 1 primitive root?

Thanks

Thanks

Last edited:

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

pivoxa15

- 2,259

- 1

Can a number have more than 1 primitive root?

Thanks

Thanks

Last edited:

- #2

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,967

- 19

This one's not too hard to work out for yourself: what's the defining property of a primitive root?

- #3

pivoxa15

- 2,259

- 1

Finding the primitive of a number, n (if it exists) is quiet a long process of trial and error is it not?

- #4

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,967

- 19

As I recall, there are quite a lot of them, so you just try things randomly, and you'll find one fairly quickly.

- #5

pivoxa15

- 2,259

- 1

How many numbers do have to try to ensure this number has no primitive roots?

Thanks Hurkyl

- #6

pivoxa15

- 2,259

- 1

Are one primitive root usually preferred to another?

- #7

pivoxa15

- 2,259

- 1

One excercise was find the primitive root of 12.

I did it by trying to find a number 'a' where the ord of the number 'a' to the base 12 equal phi(12)

phi(12) = 2

and so I found 5^2 is congruent to 1 (mod 12). The power of 5, that is 2 is also the smallest power for which 5^i is congruent to 1 (mod 12).

the gcd(5,12)=1

Hence i=phi(12)=ord5(mod12) which matches the definition of primitive root. 'a' or the primitive root therefore is 5.

But the back of the book said that 12 has no primitive root.

Is the book wrong or am I wrong?

Thanks

I did it by trying to find a number 'a' where the ord of the number 'a' to the base 12 equal phi(12)

phi(12) = 2

and so I found 5^2 is congruent to 1 (mod 12). The power of 5, that is 2 is also the smallest power for which 5^i is congruent to 1 (mod 12).

the gcd(5,12)=1

Hence i=phi(12)=ord5(mod12) which matches the definition of primitive root. 'a' or the primitive root therefore is 5.

But the back of the book said that 12 has no primitive root.

Is the book wrong or am I wrong?

Thanks

Last edited:

- #8

matt grime

Science Advisor

Homework Helper

- 9,426

- 4

in general p^n where p is any prime and 2p^n 4 are the only numbers that have primitive roots i think. (hard to prove)

if a is any primitive root mod n then so is a^k where k is relatively prime with n. (easy to prove)

Share:

- Last Post

- Replies
- 25

- Views
- 435

- Last Post

- Replies
- 5

- Views
- 621

- Replies
- 2

- Views
- 620

- Last Post

- Replies
- 1

- Views
- 430

- Replies
- 2

- Views
- 816

- Replies
- 4

- Views
- 739

- Replies
- 2

- Views
- 390

- Last Post

- Replies
- 14

- Views
- 2K

- Last Post

- Replies
- 5

- Views
- 799

- Last Post

- Replies
- 24

- Views
- 4K