# 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