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 <br /> 1 + a + a^2 + a^3 + ... + a^p^-^2 \equiv 0 mod p <br />

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!