# Thread: Order modulo a prime

1. ## Order modulo a prime

I am not sure how to prove this:

If a has order t modulo a prime p, show that a^(t-1)+a^(t-2)+...+a+1 == 0(mod p).

2. Originally Posted by tarheelborn
I am not sure how to prove this:

If a has order t modulo a prime p, show that a^(t-1)+a^(t-2)+...+a+1 == 0(mod p).
$\displaystyle 1+a+\cdot\cdot\cdot+a^{t-2}+a^{t-1} = \frac{1-a^t}{1-a} \equiv 0\mod{p}$ since $\displaystyle a^t\equiv 1 \mod{p}$.

Note that it's necessary that $\displaystyle \text{ord}_p(a)>1$, otherwise $\displaystyle (1-a)^{-1}$ doesn't exist modulo $\displaystyle p$.

3. I can't untangle the algebra of this move... Sorry, can you break it down into a couple of steps? Thanks.

4. Originally Posted by tarheelborn
I can't untangle the algebra of this move... Sorry, can you break it down into a couple of steps? Thanks.
This is a geometric series.

What do you get when you multiply $\displaystyle (a-1)(a^{t-1}+a^{t-2}+\cdot\cdot\cdot+a+1)$?

5. You would get (a*a^(t-1)+a*a^(t-2)+...+a^2+a-a^(t-1)-a^(t-2)-1), right?

6. Originally Posted by tarheelborn
You would get (a*a^(t-1)+a*a^(t-2)+...+a^2+a-a^(t-1)-a^(t-2)-1), right?
Correct, now notice how the majority of the terms cancel out, so you end up with $\displaystyle a^t-1$.

7. Yes, actually I did notice that...

8. So since a^t == 1 (mod p), (a^t)-1 == 0 (mod p), is that the idea?

9. Originally Posted by tarheelborn
So since a^t == 1 (mod p), (a^t)-1 == 0 (mod p), is that the idea?
yep