Feladat:	2017. évi Nemzetközi Matematika Diákolimpia 23. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Williams Kada
Füzet:	2017/november, 452 - 453. oldal		PDF  |  MathML
Témakör(ök):	Nemzetközi Matematikai Diákolimpia, Ponthalmazok, Egész együtthatós polinomok
Hivatkozás(ok):	Feladatok: 2017/szeptember: 2017. évi Nemzetközi Matematika Diákolimpia 23. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   Williams Kada megoldása. Szeretnénk tehát egy olyan egész együtthatós nemkonstans homogén $f\left(x\mathrm{,}y\right)$ polinomot találni, amire $f\left(x\mathrm{,}y\right)=1$, ha $\left(x\mathrm{,}y\right)\in S$. (Homogénnek nevezünk egy többváltozós polinomot, ha benne minden tag fokszáma egyenlő.) Az $f\left(x\mathrm{,}y\right)$ polinom létezését $|S|$ szerinti indukcióval igazoljuk. Ehhez felhasználjuk az ún. Bézout-lemmát, ami szerint bármely $x$ és $y$ egész számok legnagyobb közös osztója előállítható $ax+by$ alakban, ahol $a\mathrm{,}b\in \text{Z}$. Az $|S|=1$ esetből indulunk ki: ha $S=\left\{\left(x\mathrm{,}y\right)\right\}$, akkor a Bézout-lemma szerint alkalmas $a\mathrm{,}b\in \text{Z}$-re $f\left(x\mathrm{,}y\right)=ax+by$ megfelel. Tegyük fel ezután, hogy az $S=\left\{\left(a_1\mathrm{,}{b}_1\right)\mathrm{,}\text{...}\mathrm{,}\left(a_m\mathrm{,}{b}_m\right)\right\}$ halmaz minden pontján $g\left(x\mathrm{,}y\right)=1$, és szeretnénk az $\left(a_{m+1}\mathrm{,}{b}_{m+1}\right)$ elemet hozzácsatolni. A Bézout-lemma szerint $A{a}_{m+1}+B{b}_{m+1}=1$ alkalmas $A\mathrm{,}B\in \text{Z}$-re. Mivel a $\begin{array}{c}{\displaystyle h\left(x\mathrm{,}y\right)=\prod _{i=1}^m\left(a_{i}y-b_{i}x\right)}\end{array}$ polinom értéke minden $S$-beli pontban $0$, azért $C\mathrm{,}K\in \text{Z}$-re az $\begin{array}{c}{\displaystyle f\left(x\mathrm{,}y\right)=g{\left(x\mathrm{,}y\right)}^K-C\cdot {\left(Ax+By\right)}^{K\cdot \text{deg}g-m}h\left(x\mathrm{,}y\right)}\end{array}$ homogén polinom értéke minden $S$-beli pontban $1$ (feltesszük, hogy $K\ge m$), míg $\begin{array}{c}{\displaystyle f\left(a_{m+1}\mathrm{,}{b}_{m+1}\right)=g{\left(a_{m+1}\mathrm{,}{b}_{m+1}\right)}^K-C\cdot \underset{=:M}{\overset{}{\underbrace{h\left(a_{m+1}\mathrm{,}{b}_{m+1}\right)}}}\mathrm{.}}\end{array}$ Azt állítjuk, hogy $g\left(a_{m+1}\mathrm{,}{b}_{m+1}\right)$ és $M=h\left(a_{m+1}\mathrm{,}{b}_{m+1}\right)$ egymáshoz relatív prím. Valóban, ha lenne közös $p$ prímosztójuk, akkor $p\mid m$ miatt $p$ osztója lenne az $M$ valamelyik $a_i{b}_{m+1}-b_i{a}_{m+1}$ tényezőjének ($1\le i\le m$). Vegyük észre, hogy ekkor a homogenitás miatt ${\displaystyle \begin{array}{cc}\hfill {\displaystyle b_i^{\text{deg}g}g\left(a_{m+1}\mathrm{,}{b}_{m+1}\right)}& {\displaystyle =g\left(b_i{a}_{m+1}\mathrm{,}{b}_i{b}_{m+1}\right)\equiv g\left(a_i{b}_{m+1}\mathrm{,}{b}_i{b}_{m+1}\right)=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =b_{m+1}^{\text{deg}g}g\left(a_i\mathrm{,}{b}_i\right)=b_{m+1}^{\text{deg}g}\left(\text{mod}p\right)\mathrm{,}}\hfill \end{array}}$ s így $p\mid g\left(a_{m+1}\mathrm{,}{b}_{m+1}\right)$-ből $p\mid b_{m+1}$ következik. Hasonlóan kapjuk, hogy $p\mid a_{m+1}$. Ez viszont ellentmond annak, hogy $a_{m+1}$ és $b_{m+1}$ relatív prím. Ha $M\ne 0$, akkor a relatív prímség miatt $g{\left(a_{m+1}\mathrm{,}{b}_{m+1}\right)}^{\phi \left(|M|\right)}\equiv 1\left(\text{mod}M\right)$ az Euler‐Fermat-tétel szerint, így pl. $K=m\phi \left(|M|\right)$ választással alkalmas $C\in \text{Z}$-re $f\left(a_{m+1}\mathrm{,}{b}_{m+1}\right)=1$ biztosítható. Ha pedig $M=0$, akkor a $0$-hoz való relatív prímség miatt $g\left(a_{m+1}\mathrm{,}{b}_{m+1}\right)=\pm 1$, s így $K=2$ és $C=0$ megfelel. Tehát minden esetben biztosítottuk, hogy $f\left(a_{m+1}\mathrm{,}{b}_{m+1}\right)=1$ is teljesüljön. Tehát az indukciós lépést befejeztük, az indukció teljes.   Megjegyzés. A feladat általánosítása volt a 2017. szeptemberi számban megjelent A. 703. feladat. Egy további megoldási módszer olvasható a https://www.komal.hu/verseny/feladat.cgi?a=feladat&f=A703&l=hu címen.