Proof explanation: If $a\equiv b\pmod {p^n}$, then $a^p\equiv b^p\pmod {p^{n+1}}$ [duplicate]

Question

I'm having some trouble understanding this proof my teacher showed. We want to prove that:

Let $p$ be a prime number, $n\geq 1$ and $a,b\in \mathbb Z$.Then, if $a\equiv b\pmod {p^n}$, then $a^p \equiv b^p\pmod {p^{n+1}}$

The proof goes as follows:

---

If $a\equiv b\pmod {p^n}$, then $a = b + cp^n$ for some $c\in \mathbb Z$. Hence $$a^p=(b+cp^n)=\sum_{i=0}^p b^i(cp^n)^{p-i} =b^p+(cp^n)^p \equiv b^p\pmod{p^{n+1}}$$ Since, $p|\binom{p} i$ for all $1\leq i \leq p$.

---

I don't get the following equalities:

1. $$\sum_{i=0}^p b^i(cp^n)^{p-i} =b^p+(cp^n)^p$$

2. $$b^p+(cp^n)^p \equiv b^p\pmod{p^{n+1}}$$

I'm specially confused with the second one since $$b^p+(cp^n)^p=b^p+c^pp^{np} \equiv b^p\pmod {p^{np}}$$

I don't get where the teacher got $p^{n+1}$ here.

Answer 1

That answer is a mess.

I don't know why your source decided to treat the case $i=0$ as special. That seems wrong. The only binomial we need which is divisible by $p$ is $\binom p1$ for this proof.

I suppose their argument is that for $i=1,2,\dots,p-1,$ $\binom{p}i(p^n)^{p-i}$ is divisible by $\binom pip^n$ which is divisible by $p^{n+1}$ since $p\mid\binom pi.$

But that hides a crucial argument that occurs again and again in number theory, that $$(b+cp^n)^m\equiv b^m+mb^{m-1}cp^n\pmod{p^{n+1}}\tag1$$

This is true for any positive $m,n,$ even when $p$ is not prime.

---

Note, though, the original theorem is also true even if $p$ is not prime. So relying on $p\mid\binom pi$ is strange.

The key is to show $p^{n+1}$ divides all the terms of the binomial theorem sum other than the last one, when $i=p.$

I would have written the binomial in reverse order, so that the result $(1)$ is the first two terms of the binomial:

$$(b+cp^n)^p=\sum_{j=0}^p\binom{p}{j}b^{p-j}(cp^n)^{j}$$

You can think of $j=p-i$ in the source answer.

The point should be that for $j>1,$ $p^{n+1}\mid p^{nj},$ since $nj\geq 2n\geq n+1.$ But this means $(cp^n)^j =c^jp^{nj}$ is divisible by $p^{n+1}.$

So we only care about the terms $j=1$ and $j=0.$

The more interesting term is $j=1.$ When $j=1,$ $\binom p{j}=p,$ and the summand is, $$pb^{p-1}cp^n=b^{p-1}cp^{n+1},$$ so that term is also divisible by $p^{n+1}.$

So we are left with the term $j=0,$ and you get:

$$(b+cp^n)^p\equiv b^p\pmod {p^{n+1}}$$

---

Another proof might be:

$$b^p-a^p=(b-a)\sum_{i=0}^{p-1}b^{p-1-i}a^i.$$

Now $p^{n}\mid b-a,$ and $a\equiv b\pmod p$ means:

$$\sum_{i=0}^{p-1}b^{p-1-i}a^i\equiv \sum a^{p-1-i}a^i=\sum a^{p-1}=pa^{p-1}\equiv 0\pmod p$$

So this means $p^{n+1}\mid b^p-a^p.$

---

Another proof would start with:

Lemma: Given integers $b,d,m$ with $m\geq 0,$ $$(b+d)^m\equiv b^m+mdb^{m-1}\pmod{d^2}$$

This is absolutely trivial, since we are just excluding the terms of the binomial theorem that are divisible by $d^i$ with $i>1.$

Then, if $r^n\mid d,$ for some $r$ and $n>0,$ then $r^{n+1}\mid r^{2n}\mid d^2,$ and you get:

$$(b+d)^m\equiv b^m+mdb^{m-1}\pmod{r^{n+1}}$$

When $r\mid m,$ and $r^n\mid d,$ then $r^{n+1}\mid md,$ and thus:

$$(b+d)^m\equiv b^m\pmod {r^{n+1}}$$

In your case, $d=cp^n$ and $m=p,$ we have $r=p,$ $p^n\mid d$ and $p\mid m,$ so we get our result.

---

$(1)$ generalizes to any polynomial.

Given any integer polynomial, $f,$ and any $a\equiv 0\pmod{p^n},$ then $$f(b+a)\equiv f(b)+af'(b)\pmod {p^{n+1}},\tag2$$

where $f'$ is the algebraic derivative - the same thing you'd get in calculus, just defined algebraically only for polynomials.

This shows a way to solve equations $f(b)=0\pmod{p^{n}}.$ Specifically, if $f(b_1)\equiv 0\pmod p$ and $f'(b_1)\not\equiv0\pmod p,$ we can use $(2)$ to inductively find $b_n$ for a solution, modulo $p^n,$ such that $b_{n+1}\equiv b_n\pmod{p^n}.$

If you write out the solution, it will look a lot like Newton-Rapson method for finding zeros of functions in calculus. It will turn out later that this is a hint at the existence of the strange world of $p$-adic numbers.

Answer 2

I think the first equality is easier to understand with the binomial coefficients:

$$(b+cp^n)^p = (cp^n)^p + b^p + \sum_{i=1}^{p-1} {p\choose i}b^i(cp^n)^{p-i}$$

Notice now that in the sum the exponent $p-i$ is at least $1$ and $p\choose i$ is always divisible by $p$. Hence every term in the sum is divisible by $p^{n+1}$. This makes the sum vanish $(\text{mod}\ p^{n+1})$.

For the second equality simply note that $p^{n + 1}$ always divides $p^{np}$.

Answer 3

First note that $(m+q)^{p}$ has all coefficients except first and last divisible by $p$ now assume $p\mid m$ then since $m$ is raised to an exponent greater than 1 in the lead term you have it having all but last term divisible by $pm$ if $m=p^nx$ then $pm=p^{n+1}x$ so they are equivalent mod the higher power of p.