We will show that is a primitive root modulo . If is not a primitive root then must be a quadradic residue. This is because . It cannot be for that would force to be the order of since is a power of . Therefore, there is such that . Let be the solution to . Then, and so . Thus, we see that has order . That gives us a contradiction because then divides which is impossible. Since is a primitive root it means and so . We see that divides .