Let $Z=\{ p_1, ...,p_n\}$ be $n$ distinct points in $\mathbb{A^2}$. Show that $Z$ is the common zero locus of two polynomials $f,g\in K[x,y]$ s.t. deg $f \le n-1$ and deg $g\le n$.
I can only prove it without the restriction of the number of polynomials and the degree of polynomials by using the product of lines, which is a much weaker version of this statement. We did not learn protective space or other high-level theorem. How to prove it by using elementary tools?
Here is a partial solution. You will see soon why this is only partial.
Let us first consider the case that the $x$-coordinates of the $n$ points are distinct. In this circumstance you have a easy solution: Suppose the coordinates are $(x_1, y_1), \cdots, (x_n, y_n)$, then pick $g := \prod_{i=1}^n(x-x_i)$, and $f := y- p$, where $p$ is a polynomial in $x$ such that $p(x_i) = y_i$. By Lagrange interpolation, $p$ can be always chosen to have degree $n-1$ or less.
Now suppose that there are points sharing the same $x$-coordinates. Consider the transformations of the form $x_{a, b} := ax + by$. Since there are infinitely many of them and the $n$ points share at most $\binom n2$ slopes, there exists a pair $(a, b) \in \mathbb R^2$ such that $ax_i + by_i$ are pairwise distinct.
Fix a pair $(a', b')$ which is not proportional to $(a,b)$. Write $x_i' := ax_i + by_i$ and $y_i' := a'x_i + b'y_i$. Now you can pick $g := \prod_{i=1}^n(ax+by - x_i')$. $f$ can be taken similarly as the previous case, that is, a "twisted Lagrange interpolated polynomial".
Unfortunately this will not work if the field $K$ is a very small finite field.