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 theorderof a number thesmallest positive numberthat 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 modnis 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 nextwouldbe 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.