A B. 4326. feladat (2011. január)

B. 4326. Legyenek a és b egész számok. Adjunk meg olyan c és d egészeket, amelyekre tetszőleges n egész szám esetén az an+c relatív prím bn+d-hez.

(5 pont)

A beküldési határidő 2011. február 10-én LEJÁRT.

Megoldás. Ha \(\displaystyle a\) és \(\displaystyle b\) közül valamelyik 0, akkor a \(\displaystyle c=d=1\) választás nyilván megfelelő. Ha az \(\displaystyle (a;b)\) párhoz a \(\displaystyle (c;d)\) pár megfelelő, akkor a \(\displaystyle (b;a)\), illetve \(\displaystyle (-a;b)\) párhoz rendre \(\displaystyle (d;c)\) és \(\displaystyle (-c;d)\) megfelelő lesz. Ezért a továbbiakban feltesszük, hogy \(\displaystyle b\ge a>0\). Ha \(\displaystyle b\) osztható \(\displaystyle a\)-val, vagyis \(\displaystyle b=qa\), akkor \(\displaystyle c=0\), \(\displaystyle d=1\) alkalmas választást eredményez, hiszen ha egy \(\displaystyle t\) egész szám osztója az \(\displaystyle an\) és \(\displaystyle bn+1=qan+1\) számoknak is, akkor osztója a \(\displaystyle bn+1-q(an)=1\) számnak is, tehát ekkor \(\displaystyle an+c\) és \(\displaystyle bn+d\) bármely \(\displaystyle n\) egész szám esetén relatív prímek.

Ha \(\displaystyle b\) nem osztható \(\displaystyle a\)-val, akkor végezzük el \(\displaystyle a\)-ra és \(\displaystyle b\)-re az euklideszi algoritmust, vagyis legyen \(\displaystyle r_{-1}=b\), \(\displaystyle r_0=a\), és a definiáljuk a \(\displaystyle q_0,q_1,\ldots\), \(\displaystyle r_1,r_2,\ldots\) pozitív egész számokat maradékos osztások \(\displaystyle r_{i-2}=q_{i-1}r_{i-1}+r_i\) sorozatával, ahol (élve azzal a feltevéssel, hogy \(\displaystyle r_{i-1}\) nem osztója \(\displaystyle r_{i-2}\)-nek) a \(\displaystyle q_{i-1}\), \(\displaystyle r_i\) pozitív egészek az \(\displaystyle r_i<r_{i-1}\) feltétel által egyértelműen meghatározottak. Mivel az \(\displaystyle r_i\) számok sorozata szigorúan csökkenő, léteznie kell egy \(\displaystyle k\) pozitív egésznek, amelyre teljesül, hogy \(\displaystyle r_{k-1}\) osztható \(\displaystyle r_k\)-val, amikor is több lépést már nem tudunk elvégezni. Ekkor a \(\displaystyle c_k=0\), \(\displaystyle d_k=1\) választással igaz lesz, hogy az \(\displaystyle r_{k}n+c_k\) és \(\displaystyle r_{k-1}n+d_k\) számok bármely \(\displaystyle n\) egész szám esetén relatív prímek.

Írjuk most fel visszafelé a \(\displaystyle c_{k-1},d_{k-1}\ldots,c_0,d_0\) számokat \(\displaystyle k-1\ge i\ge 0\) esetén a \(\displaystyle c_i=d_{i+1}\), \(\displaystyle d_i=q_id_{i+1}+c_{i+1}\) szabállyal. Azt állítjuk, hogy minden \(\displaystyle 0\le i\le k\) esetén az \(\displaystyle r_{i}n+c_i\) és \(\displaystyle r_{i-1}n+d_i\) számok relatív prímek lesznek bármely \(\displaystyle n\) egész számra. Ez \(\displaystyle i=k\) esetén teljesül. Tegyük fel tehát, hogy valamely \(\displaystyle 1\le i\le k\) egész szám esetén ezt már beláttuk, és legyen a \(\displaystyle t\) egész szám osztója az \(\displaystyle r_{i-1}n+c_{i-1}=r_{i-1}n+d_{i}\) és \(\displaystyle r_{i-2}n+d_{i-1}=r_{i-2}n+q_{i-1}d_i+c_i\) számoknak. Ekkor \(\displaystyle t\) osztója az

\(\displaystyle (r_{i-2}n+d_{i-1})-q_{i-1}(r_{i-1}n+c_{i-1})= (r_{i-2}-q_{i-1}r_{i-1})n+(q_{i-1}d_i+c_i-q_{i-1}d_i)= r_in+c_i\)

számnak is, vagyis az indukciós feltevés miatt csak \(\displaystyle \pm 1\) lehet, ami állításunkat \(\displaystyle i-1\) esetében is igazolja.

Ezek alapján a \(\displaystyle c=c_0\), \(\displaystyle d=d_0\) választással az \(\displaystyle an+c=r_0n+c_0\) és \(\displaystyle bn+d=r_{-1}n+d_0\) számok tetszőleges \(\displaystyle n\) egész szám esetén relatív prímek lesznek.

Statisztika:

17 dolgozat érkezett.
5 pontot kapott:	Ágoston Péter, Damásdi Gábor, Dolgos Tamás, Énekes Péter, Lenger Dániel, Perjési Gábor, Szabó 928 Attila, Viharos Andor, Weisz Gellért.
4 pontot kapott:	Baráti László, Fonyó Viktória, Kiss 542 Robin, Strenner Péter.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2011. januári matematika feladatai