Help With primitive roots

• Oct 27th 2007, 11:59 PM
BruceBronson
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

http://img100.imageshack.us/img100/7879/27501917bt9.jpg
• Oct 28th 2007, 12:36 AM
Soltras
Well remember by the Fermat-Euler theorem that $a^{\phi(n)} \equiv 1 \mod n$, where $\phi(n)$ 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 $\phi(n)$ before it gives back 1 though.
For example, $\phi(8) = 4$, and while $3^4 = 81 \equiv 1 \mod 8$, it is also true that $3^2 \equiv 1 \mod 8$. 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 $3^2 \equiv 1\mod 8$, but no lower power will work.

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

In the problem you have, we are looking for primitive roots mod 1607.
Now 1607 is prime, so $\phi(1607) = 1606$ 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, $2^{1303}$ 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.
• Oct 28th 2007, 12:52 AM
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?

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?
• Oct 28th 2007, 12:58 AM
Soltras
Quote:

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.
• Oct 28th 2007, 01:01 AM
BruceBronson
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
• Oct 28th 2007, 02:37 PM
ThePerfectHacker
The primitive root of a prime $p$ is such a number $a$ (say between $1$ and $p-1$) so that the order of $a$ is $p-1$. Now by Fermat's theorem we know that $a^{p-1} \equiv 1$, 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 $a^k\not = 1$ for $k=1,2,...,p-2$ by checking each possible case. We can use the fact that the order of the element divides $p-1$ and just check the possible orders of an element. That is what the problem was doing.