A B. 4832. feladat (2016. december)

B. 4832. Bizonyítsuk be, hogy tetszőleges $\displaystyle a$, $\displaystyle b$, $\displaystyle c$ pozitív egész számokhoz találhatók olyan egymáshoz relatív prím $\displaystyle r$, $\displaystyle s$ pozitív számok, hogy $\displaystyle ar+bs$ osztható $\displaystyle c$-vel.

(5 pont)

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

Megoldás. Először tegyük fel, hogy $\displaystyle (a,b)=1$ és legyen $\displaystyle d_1=(a,c), d_2=(b,c)$. Mivel $\displaystyle (a,b)=1$, ezért $\displaystyle (d_1,d_2)=1$ is teljesül, és így $\displaystyle c=d_1d_2c'$, ahol $\displaystyle c'$ pozitív egész szám. Továbbá $\displaystyle a=d_1a'$ és $\displaystyle b=d_2b'$, ahol $\displaystyle a',b'$ pozitív egész számok, valamint az $\displaystyle a',b',c'$ számok páronként relatív prímek. Keressük az $\displaystyle r$ és $\displaystyle s$ számokat $\displaystyle r=d_2r',s=d_1s'$ alakban. A feltétel szerint $\displaystyle c=d_1d_2c'$-nek osztania kell $\displaystyle ar+bs=d_1a'd_2r'+d_2b'd_1s'=d_1d_2(a'r'+b's')$-t, ami pontosan akkor teljesül, ha $\displaystyle c'|a'r'+b's'$. Legyen $\displaystyle r'=b'$ és $\displaystyle s'=kbc'-a'$, ahol $\displaystyle k$ egy olyan pozitív egész szám, melyre $\displaystyle s'=kbc'-a'>0$. (Például $\displaystyle k=a'+1$ megfelelő választás.) Világos, hogy $\displaystyle a'r'+b's'=a'b'+kbb'c'-a'b'=kbb'c'$ osztható $\displaystyle c'$-vel. Ezenkívül $\displaystyle (r',s')=1$ is teljesül, hiszen $\displaystyle (b',kbc'-a')=(b',kb'd_2c'-a')=(b',-a')=1$. Ahhoz, hogy $\displaystyle (r,s)=1$, azt kell megmutatnunk, hogy $\displaystyle (d_2,s')=(d_1,r')=1$. Azonban $\displaystyle (d_1,r')|(a,b')=1$ és $\displaystyle (d_2,s')=(d_2,kbc'-a')=(d_2,kd_2b'c'-a')=(d_2,-a')=1$ is teljesül, hiszen $\displaystyle (a,b')|(a,b)=1$ és $\displaystyle (d_2,-a')|(b,a)=1$. Ezzel igazoltuk, hogy léteznek a feltételeknek megfelelő $\displaystyle r$ és $\displaystyle s$ számok, ha $\displaystyle a$ és $\displaystyle b$ relatív prímek.

Ha $\displaystyle a,b$ tetszőlegesek, akkor $\displaystyle a_0=a/(a,b)$ és $\displaystyle b_0=b/(a,b)$ már relatív prímek, így a fentiek szerint léteznek olyan $\displaystyle r,s$ relatív prím pozitív egész számok, hogy $\displaystyle c|a_0r+b_0s$. Ugyanerre az $\displaystyle r$-re és $\displaystyle s$-re az is teljesül, hogy $\displaystyle c|ar+bs=(a,b)(a_0r+b_0s)$.

Statisztika:

55 dolgozat érkezett.
5 pontot kapott:	Alexy Milán, Baran Zsuzsanna, Beke Csongor, Borbényi Márton, Bötkös Benedek, Busa 423 Máté, Csahók Tímea, Daróczi Sándor, Deák Bence, Döbröntei Dávid Bence, Fülöp Anna Tácia, Győrffy Ágoston, Hansel Soma, Imolay András, Janzer Orsolya Lili, Kerekes Anna, Kiss Gergely, Klász Viktória, Kocsis Júlia, Kovács 246 Benedek, Kőrösi Ákos, Lakatos Ádám, Matolcsi Dávid, Mikulás Zsófia, Nagy Dávid Paszkál, Németh 123 Balázs, Németh Ciprián, Nguyen Viet Hung, Schrettner Jakab, Sokvári Olivér, Szabó 417 Dávid, Szabó Kristóf, Tiderenczl Dániel, Tóth 827 Balázs, Tóth Viktor, Vári-Kakas Andor, Weisz Máté, Zólomy Kristóf.
4 pontot kapott:	Dömsödi Bálint, Gáspár Attila, Kővári Péter Viktor, Kupás Vendel Péter, Nguyen Thac Bach, Szakály Marcell.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	4 versenyző.
1 pontot kapott:	4 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2016. decemberi matematika feladatai