Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Incredibly close to a modular arithmetic proof by minimum counterexample!

  1. Aug 27, 2011 #1
    As stated in the title, I am trying to prove a statement by minimum counterexample involving modular arithmetic. My problem is producing the contradiction, but I feel so close!

    (The contradiction is [itex]p^m | (1 + p)^{p^{m - 1}} - 1[/itex])

    1. The problem statement, all variables and given/known data
    Let [itex]p[/itex] be an odd prime and let [itex]n[/itex] be a positive integer. Show that[itex](1 + p)^{p^{n - 1}} \cong 1 \mod p^n[/itex]



    2. Relevant equationsThe professor said as a hint, "Use the binomial theorem."
    [itex](a+b)^n = \displaystyle\sum\limits_{i=0}^n {n \choose i}a^{n - i}b^i[/itex]



    3. The attempt at a solution

    I took a picture of the latex .pdf file since the latex code would not work here.

    forumproof.jpg
     
  2. jcsd
  3. Aug 27, 2011 #2
    The last step looks fishy. There is no reason why you should expect

    [tex]\frac{p^{k-1}!}{(p^k-m)!m!}[/tex]

    to be an integer. So the right factor doesn't need to be an integer. You still need to prove this.

    Try to prove that for [itex]1\leq i<p[/itex], it holds that [itex]p^k[/itex] divides [itex]\binom{p^k}{i}[/itex]. Prove this by noticing that

    [tex]\binom{p^k}{i}=\frac{p^k}{i}\binom{p^k-1}{i-1}[/tex]

    Can you adjust this argument such that it also holds for [itex]i\geq p[/itex]?
     
  4. Aug 27, 2011 #3
    Thank you very much for taking the time to try to help me. I am a little confused about what you are saying. You said to try proving:

    [itex]1\leq i<p[/itex], it holds that [itex]p^k[/itex] divides [itex]\binom{p^k}{i}[/itex]

    And you said to prove this by noticing that [itex]\binom{p^k}{i}=\frac{p^k}{i}\binom{p^k-1}{i-1}[/itex]. Well I don't think a direct proof would work because we don't know that [itex]\frac{1}{i}\binom{p^k-1}{i-1}[/itex] will be an integer. So I thought to use induction, however this statement has three variables, so how do I know which one to use induction on?

    Again, thank you for your time.
     
  5. Aug 27, 2011 #4
    The point is that we do know that

    [tex]\frac{1}{i}\binom{p^k-1}{i-1}[/tex]

    is an integer. Indeed, we know that

    [tex]\frac{p^k}{i}\binom{p^k-1}{i-1}[/tex]

    is an integer since it is a binomial coefficient. But i cannot divide [itex]p^k[/itex] (since p is prime), so i must divide [itex]\binom{p^k-1}{i-1}[/itex]!!
     
  6. Aug 27, 2011 #5
    I did not go that route, but your post has convinced me that I have found a Q.E.D!!!!

    I would like to hear your thoughts on my complete proof.

    forumproof1.jpg

    forumproof2.jpg
     
    Last edited: Aug 27, 2011
  7. Aug 27, 2011 #6
    Looks ok!! :smile:
     
  8. Aug 27, 2011 #7
    Thank you for all of your help. A moderator can delete this thread now.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook