Proof. $$

1.

First, we will show that there exists an $n$-degree (or lesser degree) polynomial $f(X)$ that passes through the $n+1$ distinct coordinates: $(x_0,y_0),(x_1,y_1),\dots ,(x_n,y_n)$. Such a polynomial $f(X)$ is designed as follows:

$f(X)=\underset{j=0}{\overset{n}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\displaystyle \frac{(X-x_0)\cdot (X-x_1)\cdots (X-x_{j-1})\cdot (X-x_{j+1})\cdots (X-x_n)}{(x_j-x_0)\cdot (x_j-x_1)\cdots (x_j-x_{j-1})\cdot (x_j-x_{j+1})\cdots (x_j-x_n)}}\cdot y_j$

$f(X)=\underset{j=0}{\overset{n}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}\left(\prod _{\begin{array}{c}0\le k\le n\\ k\ne j\end{array}}{\displaystyle \frac{X-x_k}{x_j-x_k}}\cdot y_j\right)$

$f(X)=\underset{j=0}{\overset{n}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\ell }_j(X)\cdot y_j$ $▹$ where ${\ell }_j(X)=\underset{\begin{array}{c}0\le k\le n\\ k\ne j\end{array}}{\prod <!--\; FUNCTION\; APPLICATION\; -->}{\displaystyle \frac{X-x_k}{x_j-x_k}}$

$$

We call $\{{\ell }_0(X),{\ell }_1(X),\dots ,{\ell }_n(X)\}$ the Lagrange basis for polynomials of degree $\le n$. Given this design of $f(X)$, notice that for each of $(x_i,y_i)\in \{(x_0,y_0),(x_1,y_1),\dots ,(x_n,y_n)\}$, ${\ell }_i(x_{i^{\prime }})=1$ for $i^{\prime }=i$, and ${\ell }_i(x_{i^{\prime }})=0$ for $i^{\prime }\ne i$. Therefore, $f(x_i)=\underset{j=0}{\overset{n}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\ell }_j(x_i)\cdot y_j=1\cdot y_i=y_i$ for $0\le i\le n$. In other words, $f(X)$ passes through the $n+1$ distinct coordinates: $\{(x_0,y_0),(x_1,y_1),\dots ,(x_n,y_n)\}$. Such a satisfactory $f(X)$ can be computed in the case where the domain of $(X,Y$) is either: $(x_i,y_i)\in {ℂ}^2$ (i.e., real and complex numbers), or $(x_i,y_i)\in {\mathbb{Z}}_p^2$ (where $p$ is a prime). Especially, a valid $f(X)$ can be computed also in the $modp$ domain, because as we learned from Fermat’s Little Theorem in Theorem A-4.2.4 (§A-4.2), $a^{p-1}\equiv 1modp$ if and only if $a$ and $p$ are co-prime, and this means that if $p$ is a prime, then $a^{p-1}\equiv 1modp$ for all $a\in {\mathbb{Z}}_p^{\times }$ (i.e., ${\mathbb{Z}}_p$ without $\{0\}$). Since every value in ${\mathbb{Z}}_p^{\times }$ has an inverse, we can perform each division in the formula for $f(X)=\underset{j=0}{\overset{n}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\displaystyle \frac{(X-x_0)\cdot (X-x_1)\cdots (X-x_{j-1})\cdot (X-x_{j+1})\cdots (X-x_n)}{(x_j-x_0)\cdot (x_j-x_1)\cdots (x_j-x_{j-1})\cdot (x_j-x_{j+1})\cdots (x_j-x_n)}}\cdot y_j$ by multiplying with the corresponding inverses of those denominators.

2.

Next, we will prove that no two distinct $n$-degree (or lesser degree) polynomials $f_1(X)$ and $f_2(X)$ can pass through the same $n+1$ distinct $(X,Y)$ coordinates. Suppose there exist such two polynomials $f_1(X)$ and $f_2(X)$. Then $f_{1-2}(X)=f_1(X)-f_2(X)$ will be a new $n$-degree (or lesser degree) polynomial that passes through $(x_0,0),(x_1,0),\cdots ,(x_n,0)$. This means that $f_{1-2}(X)$ has $n+1$ distinct roots. In other words, $f_{1-2}(X)$ is an $n+1$-degree (or higher-degree) polynomial. However, this contradicts the assumption that $f_{1-2}(X)$ is an $n$-degree (or lesser degree) polynomial. Therefore, there exist no two polynomials $f_1(X)$ and $f_2(X)$ that pass through the same $n+1$ distinct $(X,Y)$ coordinates.

3.

We have shown that there exists some $n$-degree (or lesser degree) polynomial $f(X)$ that passes through $n+1$ distinct $(X,Y)$ coordinates, and no such two or more distinct polynomials exists. Therefore, there exists only a unique polynomial that satisfies this requirement.

□