opnieuw een col buiten categorie

We zullen per inductie op $\left | S \right |$ aantonen dat er een polynoom $P(x,y)$ van de vorm $a_0x^n + a_1x^{n-1} y + a_2x^{n-2}y^2 + \cdots + a_{n-1}xy^{n-1} + a_ny^n $ bestaat zodat $P(x_i,y_i)=1$ voor elke $(x_i,y_i) \in S$.

Inductiebegin: Voor $\left | S \right |=1$ is de stelling waar, want volgens de stelling van Bachet-Bézout bestaan er dan gehele getallen $a, b$ zodat $ax+by=1$ aangezien $ggd(x,y)=1$.

Inductiehypothese: Veronderstel dat de polynoom $P(x,y)$, waarbij $\deg{P}=n$, voldoet aan de stelling voor $\left | S \right |=k$.

In de inductiestap zullen we een polynoom construeren die voldoet voor $\left | S \right |=k+1$, uit deze inductiestap en de inductiebasis, volgt dan dat de vraag waar is voor elke $k \in \mathbb N_{\ge 1}$.

Inductiestap: Zij het $i^{de}$ element van $S$ $(x_i,y_i)$. Dan geldt volgens de inductiehypothese: $\forall 1 \leq i \leq k \colon P(x_i,y_i)=1$. Zij nu $Q(x,y)={P(x,y)}^r-C(x,y) \prod_{i=1}^{k} {(y_k x-x_k y)}$. We gebruiken volgende lemma's om aan te tonen dat er een gehele waarde $r$ en een $C(x,y) \in \mathbb Z[x]$ bestaat zodat $Q(x,y)$ voldoet.

Lemma 1: $\forall 1 \leq i \leq k \colon Q(x_i,y_i)=1$.
Aangezien $\forall 1 \leq s \leq k \colon C(x,y) \prod_{i=1}^{k} {(y_i x_s-x_i y_s)}=0$, omdat er een element $y_s x_s -x_s y_s=0$ in het product zit, zal $\forall 1 \leq s \leq k$: $Q(x_s,y_s)={P(x_s,y_s)}^r=1^r=1$.

Lemma 2: $k^n P(x,y)=P(kx,ky)$.
Dit volgt uit de formule voor $P(x,y)$: $k^n P(x,y)=k^n \sum^{n}_{i=1} {a_0 x^{n-i} y^{i}}=\sum^{n}_{i=1} {a_0 (kx)^{n-i} (yk)^{i}}=P(kx,ky)$

Lemma 3: $ggd\left(P(x_{k+1},y_{k+1}), \prod_{i=1}^{k} {(y_i x_{k+1}-x_i y_{k+1})}\right)=1$.
We gebruiken een bewijs door contradictie. Stel dat dit niet het geval is; dan zal er een priemgetal $p$ bestaan zodat $p \mid P(x_{k+1},y_{k+1})$ en $p \mid \prod_{i=1}^{k} {(y_i x_{k+1}-x_i y_{k+1})}$. Uit dat laatste volgt dan dat $p$ één van de factoren van de vermenigvuldiging deelt, zeg W.L.O.G. $y_1 x_{k+1}-y_{k+1} x_1$.
Als we nu alles modulo $p$ bekijken, dan geldt dat
$0 \equiv P(x_{k+1},y_{k+1}) \equiv {y_{1}}^n P(x_{k+1},y_{k+1})$
$\equiv P(x_{k+1} y_1, y_{k+1} y_1) \equiv P(y_{k+1} x_{1}, y_1 y_{k+1})$
$ \equiv {y_{k+1}}^n P(x_1,y_1) \equiv {y_{k+1}}^n \pmod p$. Analoog geldt dan: $x_{k+1}^n \equiv 0 \pmod p$, maar dit kan niet, want $ggd(x_{k+1},y_{k+1})=1$. Dus moet het bovenstaande wel gelden. (Hierbij hebben we lemma 2 gebruikt)

Lemma 4: Er bestaan gehele $m,j$ zodat $mx_{k+1}+jy_{k+1}=1$.
Dit is niks anders dan de stelling van Bachet-Bézout toegepast op $(x_{k+1},y_{k+1})$.

M.b.v. vorige 4 lemma's kunnen we de inductiestap nu afwerken.

We nemen $r$ gelijk aan een veelvoud van $\phi\left( \left| \prod_{i=1}^{k} {(y_i x_{k+1}-x_i y_{k+1})}\right| \right)$ dat minstens gelijk is aan $\frac kn$.
Merk op dat $\prod_{i=1}^{k} {(y_i x_{k+1}-x_i y_{k+1})}\not=0$ en dat $\phi 1=1$.
Vanwege lemma 3 kunnen we nu de stelling van Euler (met de Euler totiënt function) toepassen op $P(x_{k+1},y_{k+1})$ en $\prod_{i=1}^{k} {(y_i x_{k+1}-x_i y_{k+1})}$, bijgevolg bestaat er een $c \in \mathbb{N}$ zodat $P(x_{k+1},y_{k+1})^r - c \prod_{i=1}^{k} {(y_i x_{k+1}-x_i y_{k+1})}=1$.
We kiezen nu $C(x,y)=c (mx+jy)^{nr-k}$ voor deze $c$ en de $m$ en $j$ uit Lemma 4.

We tonen tot slot aan dat $Q(x,y)$ wel degelijk voldoet:
Wegens lemma 1 geldt dat $\forall 1 \leq i \leq k \colon Q(x_i,y_i)=1$.
Verder geldt dat $Q(x_{k+1},y_{k+1})=P(x_{k+1},y_{k+1})^r-c(mx_{k+1}+jy_{k+1})^{nr-k} \prod_{i=1}^{k} {(y_i x_{k+1}-x_i y_{k+1})}=1$ per constructie van $c,m,j$.
Er geldt dus opnieuw dat $Q(x_i,y_i)=1$ voor elke $i \in \{1,2 ,\ldots, k,k+1\}$.
Verder is $Q$ ook van de gewenste vorm, omdat het opgebouwd werd vanuit homogene polynomen van dezelfde graad.

Q.E.D.