Thread: 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).

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).

since .

Note that it's necessary that , otherwise doesn't exist modulo .

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

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 ?

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

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 .

Yes, actually I did notice that...

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

Originally Posted by tarheelborn

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

yep