Lagrange's Theorem (Number Theory): Proof Using $ \textbf{Z}_p $

Question

...where $ \textbf{Z}_p $ is the ring of residue classes $ (\text{mod } p) $ and $ p\in\textbf{P} $.

As an exercise, we're supposed to prove in detail the following lemma used in the proof of the theorem:

Suppose $ f $ is a polynomial of degree $ n\geq2 $ with coefficients in $ \textbf{Z}_p $ and $ [a]\in\textbf{Z}_p $. Now if $ f([a])=[0] $, there exists a polynomial $ g $ of degree $ n-1 $ (with coefficients in $ \textbf{Z}_p $) such that $$ f([x])=([x]-[a])g([x]). $$

I'm certain the identity $$ [x]^n-[a]^n=([x]-[a])\left([x]^{n-1}+[x]^{n-2} [a]+\ldots+[a]^{n-1}\right) $$ will be of great use here, but I've hard time getting started.

Any help would be appreciated.

Answer 1

If $f(x)\bmod p$ is a polynomial of degree $n\ge 2$ and $f(a)\equiv 0\pmod{p}$, then ($b_i\not\equiv 0$ are reduced mod $p$):

$$f(x)\equiv f(x)-f(a)$$

$$\equiv b_nx^n+b_{n-1}x^{n-1}+\cdots + b_1x+b_0-b_na^n-b_{n-1}a^{n-1}-\cdots -b_1a-b_0$$

$$\equiv b_n\left(x^n-a^n\right)+b_{n-1}\left(x^{n-1}-a^{n-1}\right)+\cdots +b_1(x-a)$$

$$\equiv (x-a)\left(b_n\left(x^{n-1}+x^{n-2}a+\cdots + a^{n-1}\right)+b_{n-1}\left(x^{n-2}+\cdots +a^{n-2}\right)+\cdots+b_1\right)\pmod{p}$$

Answer 2

Theorem. Let $R$ be a commutative ring and let $f(x)$ be a polynomial with coefficients in $R$, of degree $n\ge 0$. If $h(x)$ is a monic polynomial with coefficients in $R$, then there exist polynomials $g(x)$ and $r(x)$, with the degree of $r$ less than the degree of $f$, such that $f(x)=g(x)h(x)+r(x)$.

Proof. If the degree of $f(x)$ is $0$ there is nothing to prove: either $h(x)$ has degree $0$, so $h(x)=1$, or it has higher degree and we can take $g(x)=0$ and $r(x)=f(x)$.

So assume the thesis holds for all polynomials having degree less than $n$, where $n>0$. Again, if the degree $m$ of $h(x)$ is larger than $n$, we can take $g(x)=0$ and $r(x)=f(x)$, so let's assume $n\ge m$. If $f(x)=a_0+a_1x+\dots+a_nx^n$, then $$ f_1(x)=f(x)-a_nx^{n-m}h(x) $$ has degree less than $n$ and so, by the induction hypothesis, $f_1(x)=g_1(x)h(x)+r(x)$, so that $$ f(x)=f_1(x)+a_nx^{n-m}h(x)=(g_1(x)+a_nx^{n-m})h(x)+r(x) $$ and we're done. QED

Your result is the special case when $h(x)=x-a$ (on an arbitrary ring). Then the remainder $r(x)$ is constant and it's obvious that $r(x)=f(a)$. So, if $f(a)=0$, we also have $$ f(x)=(x-a)g(x) $$ Take the ring $R=\mathbb{Z}_p$ and you're finished.

I don't think that proving the particular result using the factorization of $x^k-a^k$ (maybe using special notation for the $p$ element field) is particularly illuminating.

But here it is: if $f(x)=c_0+c_1x+\dots+c_nx^n$, then $$ f(x)=f(x)-f(a)=c_1(x-a)+c_2(x^2-a^2)+\dots+c_n(x^n-a^n) $$ and you can collect $x-a$ from all terms.