Az A. 703. feladat (2017. szeptember)

A. 703. Adott egy $\displaystyle n\ge 2$ egész szám. Egy egész számokból álló rendezett szám-$\displaystyle n$-est primitívnek nevezünk, hogyha a benne szereplő számok legnagyobb közös osztója $\displaystyle 1$. Bizonyítsuk be, hogy minden primitív szám-$\displaystyle n$-esekből álló véges $\displaystyle H$ halmazhoz létezik olyan nem konstans homogén egész együtthatós $\displaystyle f(x_1,x_2,\dots,x_n)$ polinom, amelynek értéke minden $\displaystyle H$-beli szám-$\displaystyle n$-esben $\displaystyle 1$.

Az 58. Nemzetközi Matematika Diákolimpia 6. feladata nyomán

(5 pont)

A beküldési határidő 2017. október 10-én LEJÁRT.

Megoldás. Elegendő az állítást $\displaystyle H$ helyett a $\displaystyle H^*=\{(a_1^2,\dots,a_n^2)|(a_1,\dots,a_n)\in H\}$ halmazra bizonyítani, ugyanis ha $\displaystyle H^*$-hoz $\displaystyle f^*(x_1,\dots,x_n)$ polinom megfelel, akkor $\displaystyle H$-hoz az $\displaystyle f(x_1,\dots,x_n)=f^*(x_1^2,\dots,x_n^2)$ polinom alkalmas lesz.

Magyarul elegendő arra az esetre bizonyítani, mikor a $\displaystyle H$-beli szám-$\displaystyle n$-esek koordinátai nemnegatív egészek.

Legyen $\displaystyle f$ valamilyen adott (nagy) fokszámú homogén egész együtthatós polinom. Minden ilyen $\displaystyle f$ polinomhoz rendelhető egy szám-$\displaystyle |H|$-as, ami a $\displaystyle H$ elemeinél felvett értékeit tartalmazza. Célunk előállítani egy olyan $\displaystyle f$-et, melyre ez a szám-$\displaystyle |H|$-as éppen $\displaystyle (1,1,\dots,1)$: ehhez kétféle segédpolinomot állítunk elő. Készítünk előbb minden $\displaystyle v\in H$-hoz olyan $\displaystyle Q_v(x_1,\dots,x_n)$ segédpolinomot, amely egyik $\displaystyle v\in H$-nál $\displaystyle M_v>0$ értéket vesz fel, míg a többinél $\displaystyle 0$-t. Ezután pedig olyan $\displaystyle T(x_1,\dots,x_n)$ polinomot készítünk, melynek értéke $\displaystyle H$ minden eleménél $\displaystyle 1$ modulo az $\displaystyle M_v$ számok szorzata. Ekkor $\displaystyle T$-hez hozzáadva az egyes $\displaystyle Q_v$-k egész számszorosait, olyan polinom áll elő, ami minden $\displaystyle v\in H$-nál éppen $\displaystyle 1$-et vesz fel.

$\displaystyle Q_v(x_1,\dots,x_n)$ konstrukciója.

Legyen $\displaystyle v\in H$ tetszőleges. Tekintsük előbb az alábbi polinomot:

$\displaystyle P_v(x_1,\dots,x_n):=\prod_{(a_1,a_2,\dots,a_n)\in H\setminus \{v\}} \left( \sum_{i,j=1}^n (a_ix_j-a_jx_i)^2 \right).$

Mivel $\displaystyle \sum_{i,j=1}^n (a_ix_j-a_jx_i)^2=0$ pontosan akkor, ha $\displaystyle (x_1,x_2,\dots,x_n)=(\lambda a_1,\lambda a_2,\dots,\lambda a_n)$ valamilyen $\displaystyle \lambda$ valósra (hisz valamely $\displaystyle a_i$ nem nulla), és $\displaystyle v$ nem lehet egy $\displaystyle H\setminus\{v\}$-beli szám-$\displaystyle n$-es $\displaystyle \lambda$-szorosa az $\displaystyle \text{lnko}=1$ feltétel és a nemnegatív koordináták okán, ezért $\displaystyle P_v$ értéke $\displaystyle v$-ben valamilyen $\displaystyle M_v>0$, míg $\displaystyle H$ többi elemében $\displaystyle 0$.

Emellett ha $\displaystyle v=(v_1,v_2,\dots,v_n)$, akkor $\displaystyle v$ koordinátáinak legnagyobb közös osztója $\displaystyle 1$ lévén, a Bézout-lemma szerint $\displaystyle \alpha_1v_1+\dots+\alpha_nx_n=1$ alkalmas $\displaystyle \alpha_i$ egész számokra. Legyen így

$\displaystyle L_v(x_1,\dots,x_n)=\alpha_1x_1+\dots+\alpha_n x_n.$

Ekkor minden $\displaystyle P_v$ fokánál nagyobb $\displaystyle d$ fokszámhoz megadható a

$\displaystyle Q_v=P_v\cdot L_v^{d-\deg P_v}$

homogén egész együtthatós polinom, melynek értéke ugyancsak $\displaystyle v$-ben $\displaystyle M_v$ és $\displaystyle H$ többi elemében $\displaystyle 0$.

$\displaystyle T(x_1,\dots,x_n)$ konstrukciója.

Legyen $\displaystyle M=2\prod_{v\in H}M_v$. Ekkor $\displaystyle M$ kanonikus alakja $\displaystyle M=p_1^{k_1}p_2^{k_2}\dots p_s^{k_s}$, ahol a $\displaystyle p_i$-k különböző prímek, a $\displaystyle k_i$-k pozitív egészek. Tegyük fel, hogy $\displaystyle d$ többszöröse a $\displaystyle d_0=n!\cdot \prod_{i=1}^s k_i\varphi\left(p_i^{k_i}\right)$ számnak (ennek mindjárt meglátjuk az értelmét).

Tekintsünk egy $\displaystyle i$-t, és legyen $\displaystyle q=p_i^{k_i}=p^k$. Készítünk egy olyan polinomot, aminek értéke $\displaystyle 1$ mod $\displaystyle q$, ha $\displaystyle x_1,x_2,\dots,x_n$ nem mind $\displaystyle p$-vel osztható egész számok. Ehhez lényegében a szita-formulát használjuk. Legyen $\displaystyle j=1,2,\dots,n$ esetén

$\displaystyle T_j(x_1,\dots,x_n)=\sum_{1\le i_1< i_2< \dots< i_j\le n} x_{i_1}^{d/j}x_{i_2}^{d/j}\dots x_{i_j}^{d/j}.$

Hogyha $\displaystyle d$ többszöröse $\displaystyle n!\cdot k\varphi(q)$-nak, akkor az Euler-Fermat-tétel miatt

$\displaystyle x^{d/j}\equiv \begin{cases} 1\pmod{q}\quad\text{ha }p\not|x \\ 0\pmod{q}\quad \text{ha }p|x \end{cases},$

így amennyiben $\displaystyle x_1,x_2,\dots,x_n$ közül éppen $\displaystyle \nu$ darab nem osztható $\displaystyle p$-vel,

$\displaystyle T_j(x_1,x_2,\dots,x_n)\equiv \binom{\nu}{j}\pmod{q}.$

(Itt $\displaystyle \binom\nu j=0$ jelölést alkalmazunk $\displaystyle j>\nu$ esetén.) Mivel $\displaystyle \nu=1,2,\dots,n$-re a binomiális tétel szerint

$\displaystyle (1-1)^\nu=1-\binom \nu1+\binom \nu2\mp\dots\pm \binom \nu n,$

ezért mindebből következik, hogy

$\displaystyle T[q]=T_1-T_2\pm\dots\pm T_n$

polinom értéke $\displaystyle 1$ mod $\displaystyle q$, hogyha $\displaystyle x_1,x_2,\dots,x_n$ nem mind $\displaystyle p$-vel osztható.

Miután megkonstruáltuk $\displaystyle M$-nek minden $\displaystyle p_i^{k_i}$ prímhatványára a $\displaystyle d$ fokszámú $\displaystyle T[p_i^{k_i}]$ polinomot, a $\displaystyle d$ fokú $\displaystyle T$ polinomot csupán úgy adjuk meg, hogy minden egyes együtthatója kongruens legyen $\displaystyle T[p_i^{k_i}]$ megfelelő együtthatójával modulo $\displaystyle p_i^{k_i}$ az összes $\displaystyle i$-re: ez a Kínai maradéktétel sokszori alkalmazásával tehető meg.

Ekkor pedig a Kínai maradéktétel szerint $\displaystyle T(x_1,\dots,x_n)$ értéke biztosan $\displaystyle 1$ mod $\displaystyle M$, ha $\displaystyle (x_1,\dots,x_n)\in H$. Ugyanis akkor $\displaystyle T$ minden $\displaystyle i$-re $\displaystyle 1$ lesz mod $\displaystyle p_i^{k_i}$ ($\displaystyle p_i$ nem oszthatván $\displaystyle x_1,\dots,x_n$ mindegyikét az $\displaystyle \text{lnko}=1$ feltétel miatt).

Befejezés.

Minden $\displaystyle v\in H$-ra tudjuk, hogy $\displaystyle T(v)=1+M_v\ell_v$ alakú, ahol $\displaystyle \ell_v$ egész szám. Ezért ha $\displaystyle d$ fokszámot $\displaystyle d_0$ olyan nagy többszörösére választjuk, ami minden $\displaystyle P_v$ fokánál nagyobb, az esetben az

$\displaystyle f(x_1,\dots,x_n)=T(x_1,\dots,x_n)-\sum_{v\in H}\ell_v Q_v(x_1,\dots,x_n)$

polinom megfelel a célunknak.

Statisztika:

9 dolgozat érkezett.
5 pontot kapott:	Beke Csongor, Bukva Balázs, Gáspár Attila, Imolay András, Janzer Orsolya Lili, Matolcsi Dávid, Schrettner Jakab, Simon Dániel Gábor, Szabó Kristóf.

A KöMaL 2017. szeptemberi matematika feladatai