order question, with congruence

**scubasteve123** · November 3rd 2009, 07: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** · November 3rd 2009, 07:49 PM

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

**scubasteve123** · November 3rd 2009, 08: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** · November 4th 2009, 02:27 AM

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

Thread: order question, with congruence

LinkBack

Thread Tools

Display

order question, with congruence

Similar Math Help Forum Discussions

congruence question

Possible Congruence Question

Congruence question

Congruence question

Congruence question

Search Tags