The reason for the correctness of this claim is as follows: if the first equivalence holds for a, we can deduce that a and n are coprime.
Conversely, if n is prime, then there exists a primitive root modulo n, or generator of the group (Z/nZ)*.
Note that if there exists an a < n such that the first equivalence fails, a is called a Fermat witness for the compositeness of n. For example, take n = 71.
We randomly select an a=17 < n. Now we compute: For all integers a it is known that Therefore, the multiplicative order of 17 (mod 71) is not necessarily 70 because some factor of 70 may also work above.
Now we compute: Again, this does not show that the multiplicative order of 11 (mod 71) is 70 because some factor of 70 may also work.