order question, with congruence

scubasteve123 · #1 $Old$ November 3rd, 2009, 09:13 PM

Show that if a has order t (mod p) then
a^(t-1) + a^(t-2)+....+1 is congruent to 0 (mod p)

tonio · #2 $Old$ November 3rd, 2009, 09:49 PM

Quote:

Originally Posted by scubasteve123 $View Post$

Show that if a has order t (mod p) then
a^(t-1) + a^(t-2)+....+1 is congruent to 0 (mod p)

$a^t=1\!\!\pmod p\Longrightarrow a^t-1=0\!\!\pmod p$ $\Longrightarrow(a-1)(a^{t-1}+a^{t-2}+...+a+1)=0\!\!\pmod p$ ...

Tonio

scubasteve123 · #3 $Old$ November 3rd, 2009, 10:01 PM

I dont really understand how you did that.
a^t = 1 mod p makes sense clearly by definition of order
but then in the third step im a bit lost. Can you expand?
Thanks so much for ur help

tonio · #4 $Old$ November 4th, 2009, 04:27 AM

Quote:

Originally Posted by scubasteve123 $View Post$

I dont really understand how you did that.
a^t = 1 mod p makes sense clearly by definition of order
but then in the third step im a bit lost. Can you expand?
Thanks so much for ur help

The third step is high school algebra:

$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+...+ab^{n-2}+b^{n-1})\,,\,\,\forall\,n\in \mathbb{N}$

This follows from the formula for the sum of geometric sequences.

Tonio