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.

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


    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


    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


    is an integer. Indeed, we know that


    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.


    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