linear algebra - Interpolating a Polynomial with a Subset of Interpolation Points

Consider we has a polynomial $P=(x-\beta)g(x)$, where $\beta \leftarrow \mathbb{Z}_p$, $p$ is a large prime, and $g(x)$ is a non-zero polynomial.

Here degree of $P$ is fixed $n$. We evaluate $P$ at $(x_1,..., x_{n+1})$. So we get $(y_1,...,y_{n+1})$ where $P(x_i)=y_i$.

---

Question: Given $n$ pairs $(x_1,y_1),...,(x_n,y_n)$ we interpolate a polynomial $P'$ of degree at most $n-1$.What is the probability that $P'$ has root $\beta$ too?

TBN: $x_i\neq\beta$

edit: $x_i\neq x_j$ and $x_i \in \mathbb{Z}_p$ but $x_i$'s are not necessarily picked uniformly at random

Answer

Since $P$ has degree $n$ and $P'$ has degree $n-1$ at most, $P-P'$ has degree $n$, so it has $n$ distincts roots at most. Since $P(x_i)=y_i=P'(x_i)$ for $i\in\{1,\dots,n\}$, $P'(\beta) \neq P(\beta)=0$, so $P'$ cannot have $\beta$ has a root.