ABSTRACT
It follows from the theorem that if p is prime, then there exists an element b e U(p ), whose order is p — 1. In other words,
f -1 = t but r ^ i if r < p — 1. This suggests the following strategy. Suppose that an odd integer n > 0 is given, and that we somehow find b e U (n ) with order n — 1. By Lagrange’s theorem the order of b must divide the order of U (ri). Hence n — 1 must divide 4>(n). However, 0(n) < n — 1, so that 0(n) = n — 1. Thus n is prime. According to the primitive root theorem, such a b always exists if n is prime. But this is not to say that it is going to be easy to find it; for that we will need a good deal of luck.
