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