Solve Congruence Problem for Prime & Integer

  • Thread starter Ed Aboud
  • Start date
In summary, the student is trying to find a solution to a homework equation where p is prime and a is an integer not divisible by p. They proved that 1+a+a^2+a^3+...+a^p^-^2 equals 0 mod p. They are stuck and need help to continue.
  • #1
Ed Aboud
201
0

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]

Homework Equations


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:
Physics news on Phys.org
  • #2
What are you trying to prove? The problem statement only has the 'Let' part.
 
  • #3
Oh sorry.

Show that
[tex] 1 + a + a^2 + a^3 + ... + a^p^-^2 \equiv 0 mod p [/tex]
 
  • #4
Can you show a^(p-1)-1=(a-1)(1+a+a^2+...+a^(p-2))?
 
  • #5
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.
 
  • #6
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.
 
  • #7
Ok. Sorry I don't know how to factor [itex] a^p^-^1 [/itex]
 
  • #8
Dick said:
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?
 
  • #9
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] .
 
  • #10
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.
 
  • #11
Oh ok. Cool it all makes sense now.
Thanks for your help, appreciate it!
 

1. What is a congruence problem?

A congruence problem is a mathematical problem in which you are required to find a number that satisfies a given congruence equation. This means that the number has the same remainder when divided by a certain number.

2. What is a prime number?

A prime number is a positive integer that is only divisible by 1 and itself. This means that it has no other factors besides 1 and itself.

3. How do you solve a congruence problem for a prime number?

To solve a congruence problem for a prime number, you need to use the properties of modular arithmetic. This includes adding, subtracting, and multiplying the congruence equation by the same number on both sides until you isolate the unknown variable.

4. Can any integer be a solution to a congruence problem?

No, not all integers can be a solution to a congruence problem. The solution must satisfy the given congruence equation and be within the range of numbers that the equation is defined for.

5. Is it possible to have multiple solutions to a congruence problem?

Yes, it is possible to have multiple solutions to a congruence problem. This is because there can be more than one number that satisfies the given congruence equation.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
  • Precalculus Mathematics Homework Help
Replies
16
Views
2K
  • Precalculus Mathematics Homework Help
Replies
6
Views
821
  • Precalculus Mathematics Homework Help
Replies
14
Views
1K
  • Precalculus Mathematics Homework Help
Replies
27
Views
2K
  • Precalculus Mathematics Homework Help
Replies
12
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
887
  • Precalculus Mathematics Homework Help
Replies
5
Views
888
  • Precalculus Mathematics Homework Help
Replies
7
Views
762
  • Precalculus Mathematics Homework Help
Replies
5
Views
1K
Back
Top