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

Printable View

- Mar 22nd 2010, 12:17 PMtarheelbornOrder 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 PMchiph588@
$\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 PMtarheelborn
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 PMchiph588@
- Mar 22nd 2010, 01:19 PMtarheelborn
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 PMchiph588@
- Mar 22nd 2010, 01:24 PMtarheelborn
Yes, actually I did notice that...

- Mar 22nd 2010, 01:30 PMtarheelborn
So since a^t == 1 (mod p), (a^t)-1 == 0 (mod p), is that the idea?

- Mar 22nd 2010, 02:25 PMchiph588@