KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem B. 4832. (December 2016)

B. 4832. Let \(\displaystyle a\), \(\displaystyle b\), and \(\displaystyle c\) denote some positive integers. Prove that there exist two relatively prime positive numbers \(\displaystyle r\) and \(\displaystyle s\) such that \(\displaystyle ar+bs\) is divisible by \(\displaystyle c\).

(5 pont)

Deadline expired on January 10, 2017.


Sorry, the solution is available only in Hungarian. Google translation

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)\).


Statistics:

55 students sent a solution.
5 points: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 points: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 points:2 students.
2 points:4 students.
1 point:4 students.
Unfair, not evaluated:1 solution.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley