To prove this we need to use the following fact: if for then . To prove this we write and so where is everything in between the binomial expansion, here we are using a well-known fact that divides the innermost binomial coefficients, but because of the presence of it means that the innermost binomial coefficients are all divisible by too, and so everything in the middle is divisible by , thus, . Now we have the tool to prove what you wish to show. Suppose is a primitive root of , . This means the order of is . Now we claim that is a primitive root of too, this means we have to show the order of mod is . Suppose it is not a primitive root with order then using the above result it means but , and so it contradicts the fact that is a primitive root of . Now we can prove that is a primitive root of , i.e. the order is , suppose the order of was then and that means but then which is a contradiction. And now work yourself down by induction. And thus, for we have that is primitive root of .