Solve Congruence Problem for Prime & Integer

[Ed Aboud]

Homework Statement

Let p be a prime and let a be an integer not divisible by p satisfying $a \not \equiv 1 mod p$
Show that $$1 + a + a^2 + a^3 + ... + a^p^-^2 \equiv 0 mod p$$

Homework Equations

The Attempt at a Solution

$$a^\phi^(^p^) = a^p^-^1 \equiv 1 mod p$$

$$a^p^-^1 -1 \equiv 0 mod p$$

$$(a^p^-^1 -1)^p \equiv 0 mod p$$
From a previous theorem that we did in class we showed that $p$ | $p\choose m$

$$a^p^(^p^-^1^) - a^p^-^1^(^p^-^1^) + ... <br /> - a^(^p^-^1^) \equiv 0 mod p$$

I'm stuck here. I think I can sense that I am on the right track but I don't know which direction to go from here.

Any help would be greatly appreciated!

 

[Dick]

What are you trying to prove? The problem statement only has the 'Let' part.

 

[Ed Aboud]

Oh sorry.

Show that
$$1 + a + a^2 + a^3 + ... + a^p^-^2 \equiv 0 mod p$$

 

[Dick]

Can you show a^(p-1)-1=(a-1)(1+a+a^2+...+a^(p-2))?

 

[Ed Aboud]

Yeah I can show that by dividing $a - 1$ into $a^p^-^1$.
But I don't understand where you got the $a -1$ from.

 

[Dick]

I just factored a^(p-1)-1. You know that's 0 mod p. It's in your attempt at a solution. It's Fermat's little theorem.

 

[Ed Aboud]

Ok. Sorry I don't know how to factor $a^p^-^1$

 

[Dick]

Can you show a^(p-1)-1=(a-1)(1+a+a^2+...+a^(p-2))?

You answered 'yes' to this question. That's a factorization of a^(p-1)-1. If p is prime and a*b=0 mod p, what can you say about a mod p or b mod p?

 

[Ed Aboud]

You can say that p|a or p|b .

I answered yes because I was able to show that $a^p^-^1 -1$ divided by $a - 1$ equals $1 + a + a^2 + ... + a^p^-^2$.

If you hadn't told me that $a^p^-^1 -1 = (a - 1)(1 + a + a^2 + ... + a^p^-^2)$
I wouldn't have been able to factor $a^p^-^1 -1$ into $a - 1$ by $1 + a + a^2 + ... + a^p^-^2$.

I'm just wondering how did you factor $a^p^-^1 -1$ into $a^p^-^1 -1$ by $1 + a + a^2 + ... + a^p^-^2$ .

 

[Dick]

It's a really common sort of factorization. You can always factor a^n-b^n into (a-b)*(a^(n-1)+a^(n-2)*b+..+a*b^(n-2)+b^(n-1)). I just recognized it. Like a^2-b^2=(a-b)(a+b), a^3-b^3=(a-b)(a^2+ab+b^2) etc etc.

 

[Ed Aboud]

Oh ok. Cool it all makes sense now.
Thanks for your help, appreciate it!