Thread: Help With primitive roots

Hi guys, i dont understand WHAT is going on in this question...

How do they just "choose" 2, 3 and 5 to check for ?

Also in the power why is it 1606/2 then 1606/11???

I really dont understand whats going on

heres the question and solution

Well remember by the Fermat-Euler theorem that , where is the number of things less than n that are relatively prime to n.

Often times, a number doesn't need to be raised all to the way to before it gives back 1 though.
For example, , and while , it is also true that . So 3 is not a primitive root mod 8.

We call the order of a number the smallest positive number that number is raised to in order to get 1. In the above example, the order of 3 is 2, because , but no lower power will work.

So a primitive root mod n is a number whose order is equal to . It is a proven fact that the order of a number will always divide . This fact will be used.

In the problem you have, we are looking for primitive roots mod 1607.
Now 1607 is prime, so because everything less than it is obviously relatively prime to it.

If a number were NOT primitive, then its order would be less than 1606, but also its order would divide 1606.

A good strategy for finding primitive roots is just to test numbers.
1 is obviously not primitive because its order is 1.
Looking at 2, we raise it to powers that divide 1606; Try raising it to 1303 power (which is 1606/2, as was done in the solution). Sure enough, this gives 1, so the order of 2 is at most 1303, which means 2 cannot be primitive. (by the way, I'm guessing you know how at least to raise numbers to very high powers using mods without working out massive calculations. On a normal day, outside the world of mods, is a daunting task at best.)
Next we look at 3, and do the same thing. Again, we get 1 back, so 3 cannot be a primitive root.
Now next would be 4, but 4 is skipped because it's a power of 2, and we already threw 2 away as a possibility.

Next is 5, and actually the solution you posted has a typo in it.
First we check the 1606/2 power, and instead of 1 we get -1. So far so good.
Next we check 1606/11 power, and again we don't get 1. Good news again.
Finally, we check the last power, which is 1606/73 (in the pic posted, they have this printed wrong) and again we don't get 1. So 1606 must be the order of 5, and so 5 is a primitive root.

Hey,thanks for the help..

I still dont understand how you can just "divide" the number by 2 and know that it gives 1?

I know (Now) its just easy to read the soultion and say "yes this gives 1" but when your trying to solve it from scratch, When i power numbers i use the fast powering algorithm, which is (relativley) time consuming, so how can i be trying all these numbers inorder to get somthing congruent to 1?

for example there id need to calculate 2^803, which would take a good 5 minutes?

Is the fast powering algorithm optimal to be using in an exam?

Originally Posted by BruceBronson

Hey,thanks for the help..

I still dont understand how you can just "divide" the number by 2 and know that it gives 1?

When i power numbers i use the fast powering algorithm, which is (relativley) time consuming, so how can i be trying out all these numbers inorder to get somthing congruent to 1?

for example there id need to calculate 2^803, which would take a good 5 minutes?

Is the fast powering algorithm optimal to be using in an exam?

I've never heard it called that, but I'm sure that's the standard method. If it only takes 5 minutes to do that, you're probably using the right method.
Of course I don't know your professor, but in my experience exam questions are not made unnecessarily complicated in terms of calculation.

Fast powering is the method where u have thre 3 columns and the first is half the entry in the previous, 2nd is the square mod m of the previous, and the last is the product of 2 entries mod m

Is that the fastest possible way to do it?

Ps. thanks for the help

The primitive root of a prime is such a number (say between and ) so that the order of is . Now by Fermat's theorem we know that , but it is not necessaryiliy the smallest possible exponent. So we need to check whether or not it is the smallest.

However, it does not need we need to show for by checking each possible case. We can use the fact that the order of the element divides and just check the possible orders of an element. That is what the problem was doing.