1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Congruence problem.

  1. Nov 24, 2008 #1
    1. The problem statement, all variables and given/known data

    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. Relevant 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: Nov 24, 2008
  2. jcsd
  3. Nov 24, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    What are you trying to prove? The problem statement only has the 'Let' part.
     
  4. Nov 24, 2008 #3
    Oh sorry.

    Show that
    [tex] 1 + a + a^2 + a^3 + ...... + a^p^-^2 \equiv 0 mod p [/tex]
     
  5. Nov 24, 2008 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Can you show a^(p-1)-1=(a-1)(1+a+a^2+...+a^(p-2))?
     
  6. Nov 24, 2008 #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.
     
  7. Nov 24, 2008 #6

    Dick

    User Avatar
    Science Advisor
    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.
     
  8. Nov 24, 2008 #7
    Ok. Sorry I don't know how to factor [itex] a^p^-^1 [/itex]
     
  9. Nov 24, 2008 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  10. Nov 24, 2008 #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] .
     
  11. Nov 24, 2008 #10

    Dick

    User Avatar
    Science Advisor
    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.
     
  12. Nov 24, 2008 #11
    Oh ok. Cool it all makes sense now.
    Thanks for your help, appreciate it!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Congruence problem.
  1. Linear congruence (Replies: 4)

  2. Linear congruence (Replies: 3)

Loading...