1. Limited time only! Sign up for a free 30min personal 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!

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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Looks ok!! :smile:
     
  8. Aug 27, 2011 #7
    Thank you for all of your help. A moderator can delete this thread now.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Incredibly close to a modular arithmetic proof by minimum counterexample!
  1. Modular Arithmetic Proof (Replies: 22)

Loading...