Let $\mathbb{F}$ be some finite field.
Let $Q(x, y)\in\mathbb{F}[X,Y]$ and $P(x)\in\mathbb{F}[X]$ such that $Q(x, P(x)) = 0$ for every $x\in\mathbb{F}$.
Prove that $Q(x, y) = (y - P(x))A(x, y)$ for some polynomial $A(x, y)$, i.e. $y-P|Q$.
I must say I am stuck and I don't know how to prove this fact.
(This was too long to post as a comment). The comments in the related link conclude that this is not true in general, but the counterexample is over $\mathbb{C}$, not over a finite field. I don't actually know if it's true, but if you consider elements of $\mathbb{F}[X,Y]$ as elements of $\mathbb{F}[X][Y]$ (that is, as polynomials in the indeterminate $Y$ with coefficients in $\mathbb{F}[X]$ then the statement is an immediate consequence of the remainder theorem, which can be proven if the set of polynomials is an euclidean domain. Since $\mathbb{F}[X]$ is not a field, it is not necessarily true that $\mathbb{F}[X][Y]$ is euclidean, but maybe the fact that $\mathbb{F}$ is a finite field, gives you that property. Not sure, I will have to think more.