Number of polynomials with bounded degree if we know its values at two points? Let $\mathbb{F}$ be a finite field of order $q$. Then we know that there are at most $q^{\ell}$ polynomials $p(x)\in \mathbb{F}[x]$ with degree at most $\ell$ satisfying $p(a)=b$ for $a, b\in\mathbb{F}$: because $p(x)-b=(x-a)p_1(x)$ with a polynomial $p_1(x)\in \mathbb{F}[x]$ of degree at most $\ell-1$.
While if we know $p(a_1)=b_1$ and $p(a_2)=b_2$ for two distinct $a_1,a_2\in\mathbb{F}$, there are at most how many such polynomials $p$ of degree at most $\ell$? Is it possible to bound it by $O(q^{\ell-1})$, assuming $q\to\infty$ and $\ell$ is fixed?
 A: The best possible result holds: Take $n$ points $(a_i,b_i)$ with distinct $a_i$. (This implies that $n \le q$.) Then, for $\ell \ge n-1$,  there will be exactly $q^{\ell - n + 1}$ polynomials $p(x)$ such that $p(a_i) = b_i$ and $p(x)$ has degree at most $n$. 
Start by observing that there exists a polynomial $q(x)$ of degree $< n$ which satisfies $q(a_i) = b_i$. The polynomial $q(x)$ will be unique, and it can be found by Lagrange interpolation. For $n = 1$ it is the constant polyomial $q(x) = b_1$, and for $n = 2$ it is the line
$$q(x) = b_1 + (x - a_1) \cdot \frac{(b_2 - b_1)}{(a_2 - a_1)}.$$
Now the argument you gave works: the difference $p(x) - q(x)$ has degree at most $\ell$ (since the degree of $q(x)$ is at most $n-1$, and $n-1 \le \ell$), and yet it also vanishes at the $n$ points $a_i$, and so
$$p(x) - q(x) = r(x) \cdot \prod (x - a_i),$$
where the degree of $r(x)$ is at most $\ell - n$. (Conversely, any $p(x)$ of this form works). Hence the number of $p(x)$ is just the number of polynomials of degree $\ell - n$, which is $q^{\ell - n + 1}$.
In your problem $n = 2$, so the result holds for all $q$ and all $\ell \ge 1$.
