# Order modulo a prime

• Mar 22nd 2010, 12:17 PM
tarheelborn
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).
• Mar 22nd 2010, 12:42 PM
chiph588@
Quote:

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$.
• Mar 22nd 2010, 12:47 PM
tarheelborn
I can't untangle the algebra of this move... Sorry, can you break it down into a couple of steps? Thanks.
• Mar 22nd 2010, 12:51 PM
chiph588@
Quote:

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)$?
• Mar 22nd 2010, 01:19 PM
tarheelborn
You would get (a*a^(t-1)+a*a^(t-2)+...+a^2+a-a^(t-1)-a^(t-2)-1), right?
• Mar 22nd 2010, 01:22 PM
chiph588@
Quote:

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$.
• Mar 22nd 2010, 01:24 PM
tarheelborn
Yes, actually I did notice that...
• Mar 22nd 2010, 01:30 PM
tarheelborn
So since a^t == 1 (mod p), (a^t)-1 == 0 (mod p), is that the idea?
• Mar 22nd 2010, 02:25 PM
chiph588@
Quote:

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

yep