Proof of the Fundamental Theorem of Algebra for Congruence Equations 📂Number Theory

Proof of the Fundamental Theorem of Algebra for Congruence Equations

Theorem¹

For some prime $p$, suppose $p\nmid a_{ 0 }$. Then for a polynomial with all integer coefficients $$ f(x)=a_{ 0 }x^{ d }+a_{ 1 }x^{ d-1 }+ \cdots +a_{ d-1 }x+a_{ d } $$ the equation $f(x)\equiv 0 \pmod{p}$ has at most $d$ incongruent solutions.

Explanation

Speaking of polynomials with real coefficients, as commonly known, this is the theorem that an equation of degree $n$ has $n$ solutions, counting multiplicities. Thinking about this in number theory, we can say that an equation of degree $d$ with only integer coefficients in $\pmod{p}$ has at most $d$ solutions. This statement can be made even more concise by introducing complex numbers to the integers.

Proof

Strategy: Unlike the fundamental theorem of algebra, which is deduced through complex analysis, elementary number theory knowledge suffices for congruence equations. We assume that there exist more than $d$ incongruent solutions and derive a contradiction.

Assume that there exists a polynomial function $P$ of degree $n$ with integer coefficients such that the equation $P(x)\equiv 0 \pmod{p}$ has more than $n$ distinct solutions. Among such polynomials, choose the polynomial function $f$ of smallest degree, which can be expressed as follows. $$ f(x)=A_{ 0 }x^{ d }+A_{ 1 }x^{ d-1 }+ \cdots +A_{ d-1 }x+A_{ d } (p\nmid A_{ 0 }) $$ Then the equation $f(x)\equiv 0 \pmod{p}$ has distinct solutions $r_{ 1 },r_{ 2 }, \cdots ,r_{ d },r_{ d+1 }$. For a solution $r$ of $f(x)\equiv 0 \pmod{p}$, $f(x)$ can be expressed as $$ f(x)=(x-r)g(x)+f(r) $$ The quotient $g(x)$ obtained by dividing $f(x)$ by $(x-r)$ is a polynomial function of degree $(d-1)$ with integer coefficients, as follows. $$ g(x)=B_{ 0 }x^{ d-1 }+B_{ 1 }x^{ d-2 }+ \cdots +B_{ d-2 }x+B_{ d-1 } (p\nmid B_{ 0 }) $$ Substituting $r_{ 1 }$ for $r$, since $f(r_{ 1 })\equiv 0 \pmod{p}$, $$ f(x)\equiv (x-r_{ 1 })g(x) \pmod{p} $$ Since $r_{ k }$ is a root of $f(x)=0$, for $(2\le k\le d+1)$, $$ f(r_{ k })\equiv (r_{ k }-r_{ 1 })g(r_{ k })\equiv 0 \pmod{p} $$ Since $r_{ k }-r_{ 1 } \not\equiv 0 \pmod{p}$, it must be that $g(r_{ k })\equiv 0 \pmod{p}$. Therefore, $g(x)\equiv 0 \pmod{p}$ has $d$ distinct solutions $r_{ 2 },r_{ 3 }, \cdots ,r_{ d+1 }$. But $f(x)$ is the polynomial function of lowest degree, namely $d$, among those having more distinct solutions than their degree, whereas $g(x)$, despite having degree $(d-1)$, has $d$ distinct solutions, which is a contradiction.

■