1. ## Index Arithmetic

The question asks to show that if p is an odd prime, and r is a primitive root of p, then ind_r (p-1) = (p-1)/2

I don't even know where to start -- r^(p-1) = r^(phi(p)) which is congruent to one modulo p. Writing this out, I would have that r^(p-1) = kp +1.

I'm just starting on modular arithmetic today, so forgive me for my lack of knowledge...

2. ## Re: Index Arithmetic

Use Fermat little theorem, $\displaystyle r^{p-1} =1 mod p$ and factorise $\displaystyle (r^{\frac{p-1}{2}}-1)(r^{\frac{p-1}{2}}+1)=0 mod p$.
gcd(r,p)=1, now because r is primitve root of p, $\displaystyle \phi(p) =p-1$ is the lowest power such that r^k =1 mod p, which means that:
$\displaystyle r^{\frac{p-1}{2}}= -1 mod p = (p-1) mod p$
Now if there's a lowers integer s.t $\displaystyle r^k = p-1 mod p$ then $\displaystyle r^{2k} =1 mod p$ where k is smaller than (p-1)/2, and thus 2k is smaller than p-1, contradiction.

3. ## Re: Index Arithmetic

Thanks Invisibleman! Admittedly, though, I'm confused as to how you can jump to r^(p-1 /2) congruent to -1 mod p. Is that a common identity?

4. ## Re: Index Arithmetic

Originally Posted by jsndacruz
The question asks to show that if p is an odd prime, and r is a primitive root of p, then ind_r (p-1) = (p-1)/2

I don't even know where to start -- r^(p-1) = r^(phi(p)) which is congruent to one modulo p. Writing this out, I would have that r^(p-1) = kp +1.

I'm just starting on modular arithmetic today, so forgive me for my lack of knowledge...

$\displaystyle r$ is primitive root of $\displaystyle p$ therefor $\displaystyle \text{ind}_r1=p-1$.

Now,$\displaystyle p-1= \text{ind}_r(-1)(-1)\overset{Theorem}{\equiv}$

$\displaystyle \equiv\text{ind}_r(-1)+\text{ind}_r(-1)=2\text{ind}_r(-1)(\mod p-1)$.

Therefor:

$\displaystyle \text{ind}_r(-1)\equiv \frac{p-1}{2}(\mod p-1)$

and by definition of the index...

$\displaystyle \text{ind}_r(-1)= \frac{p-1}{2}$

5. ## Re: Index Arithmetic

Originally Posted by jsndacruz
Thanks Invisibleman! Admittedly, though, I'm confused as to how you can jump to r^(p-1 /2) congruent to -1 mod p. Is that a common identity?
because if r^((p-1)/2) is congruent to 1 then we have a contradiction to the fact that p-1 is the smallest power that r^k is congruent to 1.
After this I am using the fact that (r^((p-1)/2)-1)(r^((p-1)/2)+1) = 0 mod p to deduce that r^((p-1)/2) = -1 mod p.

6. ## Re: Index Arithmetic

Ahh that makes sense InvisibleMan. I didn't see that step when I was running through it. Thanks so much!