# order question, with congruence

• Nov 3rd 2009, 07:13 PM
scubasteve123
order question, with congruence
Show that if a has order t (mod p) then
a^(t-1) + a^(t-2)+....+1 is congruent to 0 (mod p)
• Nov 3rd 2009, 07:49 PM
tonio
Quote:

Originally Posted by scubasteve123
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
• Nov 3rd 2009, 08:01 PM
scubasteve123
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
• Nov 4th 2009, 02:27 AM
tonio
Quote:

Originally Posted by scubasteve123
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