Incredibly close to a modular arithmetic proof by minimum counterexample

[jdinatale]

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 p^m | (1 + p)^{p^{m - 1}} - 1)

Homework Statement

Let p be an odd prime and let n be a positive integer. Show that(1 + p)^{p^{n - 1}} \cong 1 \mod p^n

Homework Equations

The professor said as a hint, "Use the binomial theorem."
(a+b)^n = \displaystyle\sum\limits_{i=0}^n {n \choose i}a^{n - i}b^i

The Attempt at a Solution

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

 

[micromass]

The last step looks fishy. There is no reason why you should expect

\frac{p^{k-1}!}{(p^k-m)!m!}

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 1\leq i<p, it holds that p^k divides \binom{p^k}{i}. Prove this by noticing that

\binom{p^k}{i}=\frac{p^k}{i}\binom{p^k-1}{i-1}

Can you adjust this argument such that it also holds for i\geq p?

 

[jdinatale]

The last step looks fishy. There is no reason why you should expect

\frac{p^{k-1}!}{(p^k-m)!m!}

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 1\leq i<p, it holds that p^k divides \binom{p^k}{i}. Prove this by noticing that

\binom{p^k}{i}=\frac{p^k}{i}\binom{p^k-1}{i-1}

Can you adjust this argument such that it also holds for i\geq p?

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:

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

And you said to prove this by noticing that \binom{p^k}{i}=\frac{p^k}{i}\binom{p^k-1}{i-1}. Well I don't think a direct proof would work because we don't know that \frac{1}{i}\binom{p^k-1}{i-1} 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.

 

[micromass]

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:

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

And you said to prove this by noticing that \binom{p^k}{i}=\frac{p^k}{i}\binom{p^k-1}{i-1}. Well I don't think a direct proof would work because we don't know that \frac{1}{i}\binom{p^k-1}{i-1} 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.

The point is that we do know that

\frac{1}{i}\binom{p^k-1}{i-1}

is an integer. Indeed, we know that

\frac{p^k}{i}\binom{p^k-1}{i-1}

is an integer since it is a binomial coefficient. But i cannot divide p^k (since p is prime), so i must divide \binom{p^k-1}{i-1}!

 

[jdinatale]

The point is that we do know that

\frac{1}{i}\binom{p^k-1}{i-1}

is an integer. Indeed, we know that

\frac{p^k}{i}\binom{p^k-1}{i-1}

is an integer since it is a binomial coefficient. But i cannot divide p^k (since p is prime), so i must divide \binom{p^k-1}{i-1}!

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.

 

[micromass]

Looks ok!

 

[jdinatale]

Looks ok!

Thank you for all of your help. A moderator can delete this thread now.