Note that since and so -since p is prime- or , but the former is not possible since r is a primitive root.

Thus so your problem is equivalent to showing that is coprime to .

But and so is either 1 or 2.

Now note that 4 doesn't divide p+1, since p-1 is divisible by 4, and so (p+1)/2 must be odd.