Let n>2 be a positive integer. Say that n has a primitive root, call it r. Consider the set , this set is the complete set of numbers relatively prime to . Now is a primitive root means must also be a complete set of numbers relatively prime to . If then thus the order of is at least but since we require that it means the only possible value for is . Now (for the converse) say . We will argue that cannot be congruent to eachother and hence by pigeonhole principle they must contain all the relatively prime numbers to . Note, if then but that means since it means so since . Thus, this shows that the only numbers congruent are those to themselves, i.e. distinct numbers leave distinct remainders mod n.