Use Fermat little theorem, and factorise .

gcd(r,p)=1, now because r is primitve root of p, is the lowest power such that r^k =1 mod p, which means that:

Now if there's a lowers integer s.t then where k is smaller than (p-1)/2, and thus 2k is smaller than p-1, contradiction.

From this follows your claim.