• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Congruence problem.

  • Thread starter Ed Aboud
  • Start date
197
0
1. Homework Statement

Let p be a prime and let a be an integer not divisible by p satisfying [itex] a \not \equiv 1 mod p [/itex]
Show that


[tex]
1 + a + a^2 + a^3 + ...... + a^p^-^2 \equiv 0 mod p
[/tex]
2. Homework Equations



3. The Attempt at a Solution

[tex] a^\phi^(^p^) = a^p^-^1 \equiv 1 mod p [/tex]

[tex] a^p^-^1 -1 \equiv 0 mod p [/tex]

[tex] (a^p^-^1 -1)^p \equiv 0 mod p [/tex]



From a previous theorem that we did in class we showed that [itex] p [/itex] | [itex] p\choose m [/itex]

[tex] a^p^(^p^-^1^) - a^p^-^1^(^p^-^1^) + .......
- a^(^p^-^1^) \equiv 0 mod p[/tex]

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:

Dick

Science Advisor
Homework Helper
26,258
618
What are you trying to prove? The problem statement only has the 'Let' part.
 
197
0
Oh sorry.

Show that
[tex] 1 + a + a^2 + a^3 + ...... + a^p^-^2 \equiv 0 mod p [/tex]
 

Dick

Science Advisor
Homework Helper
26,258
618
Can you show a^(p-1)-1=(a-1)(1+a+a^2+...+a^(p-2))?
 
197
0
Yeah I can show that by dividing [itex] a - 1 [/itex] into [itex] a^p^-^1 [/itex].
But I don't understand where you got the [itex] a -1 [/itex] from.
 

Dick

Science Advisor
Homework Helper
26,258
618
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.
 
197
0
Ok. Sorry I don't know how to factor [itex] a^p^-^1 [/itex]
 

Dick

Science Advisor
Homework Helper
26,258
618
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?
 
197
0
You can say that p|a or p|b .

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

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

I'm just wondering how did you factor [itex] a^p^-^1 -1 [/itex] into [itex] a^p^-^1 -1 [/itex] by [itex] 1 + a + a^2 + ....... + a^p^-^2 [/itex] .
 

Dick

Science Advisor
Homework Helper
26,258
618
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.
 
197
0
Oh ok. Cool it all makes sense now.
Thanks for your help, appreciate it!
 

Related Threads for: Congruence problem.

  • Posted
Replies
9
Views
2K
  • Posted
Replies
4
Views
2K
  • Posted
Replies
3
Views
1K
  • Posted
Replies
2
Views
1K
  • Posted
Replies
7
Views
981
Replies
6
Views
918
Replies
9
Views
2K
Replies
3
Views
1K

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

Hot Threads

Top