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.