# Incredibly close to a modular arithmetic proof by minimum counterexample!

1. Aug 27, 2011

### 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$)

1. The problem statement, all variables and given/known data
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$

2. Relevant equationsThe 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$

3. The attempt at a solution

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

2. Aug 27, 2011

### micromass

Staff Emeritus
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$?

3. Aug 27, 2011

### jdinatale

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.

4. Aug 27, 2011

### micromass

Staff Emeritus
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}$!!

5. Aug 27, 2011

### jdinatale

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
6. Aug 27, 2011

### micromass

Staff Emeritus
Looks ok!!

7. Aug 27, 2011

### jdinatale

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