KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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 points)

Deadline expired on 10 January 2017.


Google Translation (Sorry, the solution is published in Hungarian only.)

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 on problem B. 4832.
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.


  • Problems in Mathematics of KöMaL, December 2016

  • Támogatóink:   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