Well remember by the Fermat-Euler theorem that $\displaystyle a^{\phi(n)} \equiv 1 \mod n$, where $\displaystyle \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 $\displaystyle \phi(n)$ before it gives back 1 though.
For example, $\displaystyle \phi(8) = 4$, and while $\displaystyle 3^4 = 81 \equiv 1 \mod 8$, it is also true that $\displaystyle 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 $\displaystyle 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 $\displaystyle \phi(n)$. It is a proven fact that the order of a number will always divide $\displaystyle \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 $\displaystyle \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, $\displaystyle 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.
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?
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 $\displaystyle p$ is such a number $\displaystyle a$ (say between $\displaystyle 1$ and $\displaystyle p-1$) so that the order of $\displaystyle a$ is $\displaystyle p-1$. Now by Fermat's theorem we know that $\displaystyle 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 $\displaystyle a^k\not = 1$ for $\displaystyle k=1,2,...,p-2$ by checking each possible case. We can use the fact that the order of the element divides $\displaystyle p-1$ and just check the possible orders of an element. That is what the problem was doing.