Bivariate low-degree polynomial testing of Polishchuk-Spielman
If I understand it correctly, Gauss's lemma implies that that $P$ and $E$ have a non-trivial common factor over $\mathbb{F}[x,y]$.

But in the beginning of the proof of Lemma 8 they assume without loss of generality that $P$ and $E$ do not have a common factor. More specifically, they show that if $P$ and $E$ have a common factor then they can use induction to show that $E$ divides $P$.