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

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$$
1. $$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.

• Better not to use $=$ when you mean $\equiv$. You can get the latter symbol with \equiv Mar 24 at 14:23
• Already edited the question @ThomasAndrews Mar 24 at 14:30
• You need the binomials in the sum from expanding the binomial theorem. And the first two steps $a^p=(b+cp^n)^p=...$ are the only two that should be $=.$ The rest should be $\equiv.$ And you left off the exponent $^p$ in $(b+cp^n)^p.$ Mar 24 at 14:48
• Also, if they say that $p\mid\binom pi$ for $1\leq i\leq p,$ they are wrong. It is true for $1\leq i\leq p-1.$ Mar 24 at 14:58
• Put $\, k,n = p,p^{n-1}$ in the linked dupe, where the answer by Paul explains the points you ask about. Note also another answer there shows how to view it as a special case of the double root test. Mar 24 at 20:28

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.$$

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.

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}$$.

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.