[proofplan] Subtract the two polynomials and study the difference $r=p-q$. The hypotheses imply that each of the $d+1$ distinct elements $a_0,\dots,a_d$ is a root of $r$. A nonzero polynomial over a field of degree at most $d$ cannot have more than $d$ distinct roots, so $r$ must be the zero polynomial. Therefore $p=q$ in $k[x]$. [/proofplan] [step:Reduce the identity to showing that the difference polynomial is zero] Define $r \in k[x]$ by \begin{align*} r=p-q. \end{align*} For each $i \in \{0,\dots,d\}$, evaluation at $a_i$ gives \begin{align*} r(a_i)=p(a_i)-q(a_i)=0. \end{align*} Thus each $a_i$ is a root of $r$. Since the elements $a_0,\dots,a_d$ are pairwise distinct, the polynomial $r$ has at least $d+1$ distinct roots in $k$. [/step] [step:Use the root bound for nonzero polynomials over a field] We use the following standard fact: if $f \in k[x]$ is nonzero and $\deg f=n$, then $f$ has at most $n$ distinct roots in $k$. [claim:A nonzero polynomial of degree $n$ over a field has at most $n$ roots] Let $f \in k[x]$ be nonzero with $\deg f=n$. Then $f$ has at most $n$ distinct roots in $k$. [/claim] [proof] We prove the claim by induction on $n \in \mathbb{N} \cup \{0\}$. If $n=0$, then $f$ is a nonzero constant polynomial, so $f(a)\neq 0$ for every $a \in k$, and hence $f$ has no roots. Assume the claim holds for degree $n-1$, where $n\geq 1$, and let $f \in k[x]$ be nonzero with $\deg f=n$. If $f$ has no root in $k$, the result follows. Otherwise choose a root $a \in k$ of $f$. By the [factor theorem](/theorems/3235) for polynomials over a field, there exists $g \in k[x]$ such that \begin{align*} f=(x-a)g. \end{align*} Since $\deg(x-a)=1$ and $f$ is nonzero of degree $n$, the polynomial $g$ is nonzero and $\deg g=n-1$. Let $b \in k$ be any root of $f$ with $b\neq a$. Evaluating the factorisation at $b$ gives \begin{align*} 0=f(b)=(b-a)g(b). \end{align*} Because $k$ is a field and $b-a\neq 0$, the element $b-a$ is invertible, so $g(b)=0$. Hence every root of $f$ other than $a$ is a root of $g$. By the inductive hypothesis, $g$ has at most $n-1$ roots. Therefore $f$ has at most one root equal to $a$ and at most $n-1$ further roots, so $f$ has at most $n$ roots. This completes the induction. [/proof] If $r$ were nonzero, then since $\deg p\leq d$ and $\deg q\leq d$, the degree of the difference satisfies \begin{align*} \deg r \leq d. \end{align*} The claim would then imply that $r$ has at most $d$ distinct roots in $k$, contradicting the $d+1$ distinct roots $a_0,\dots,a_d$ found above. Therefore $r=0$ in $k[x]$. [guided] The key point is that equality of values at enough distinct points forces the difference polynomial to have too many roots unless it is the zero polynomial. We first recall the needed algebraic fact: a nonzero polynomial $f \in k[x]$ of degree $n$ has at most $n$ distinct roots in $k$. Here is the proof of that fact. We argue by induction on $n \in \mathbb{N} \cup \{0\}$. When $n=0$, the polynomial $f$ is a nonzero constant, so no element of $k$ is a root. For the inductive step, assume $n\geq 1$ and suppose the result is known for degree $n-1$. If $f$ has no root, there is nothing to prove. If $a \in k$ is a root, the factor theorem gives a polynomial $g \in k[x]$ such that \begin{align*} f=(x-a)g. \end{align*} Since $f$ has degree $n$ and $x-a$ has degree $1$, the polynomial $g$ is nonzero and has degree $n-1$. Now take any other root $b \in k$ of $f$, with $b\neq a$. Substituting $b$ into the factorisation gives \begin{align*} 0=f(b)=(b-a)g(b). \end{align*} Because $k$ is a field and $b-a\neq 0$, multiplication by $b-a$ can be cancelled. Thus $g(b)=0$. So all roots of $f$ except possibly $a$ are roots of $g$. By the inductive hypothesis, $g$ has at most $n-1$ roots, and hence $f$ has at most $n$ roots. We apply this fact to the polynomial $r=p-q$. If $r$ were nonzero, then the degree bound on $p$ and $q$ gives \begin{align*} \deg r \leq d. \end{align*} Therefore $r$ could have at most $d$ distinct roots. But the previous step showed that $a_0,\dots,a_d$ are $d+1$ pairwise distinct roots of $r$. This contradiction shows that $r$ cannot be nonzero. Hence $r=0$ in $k[x]$. [/guided] [/step] [step:Translate the zero difference back into equality of polynomials] Since $r=0$ and $r=p-q$, we have \begin{align*} p-q=0 \end{align*} in $k[x]$. Adding $q$ to both sides in the additive group of the [polynomial ring](/page/Polynomial%20Ring) $k[x]$ gives \begin{align*} p=q. \end{align*} This is the desired equality in $k[x]$. [/step]