Congruence problem.

Ed Aboud

1. 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$$
2. Homework Equations

3. 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^) + ....... - 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!

Last edited:
Related Precalculus Mathematics Homework Help News on Phys.org

Dick

Homework Helper
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

Homework Helper
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

Homework Helper
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

Homework Helper
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

Homework Helper
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!

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving