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. 4326. Let a and b be integers. Find integers c and d such that an+c and bn+d are relative primes for all integers n.

(5 points)

Deadline expired on 10 February 2011.


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

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.


Statistics on problem B. 4326.
17 students sent a solution.
5 points:Á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 points:Baráti László, Fonyó Viktória, Kiss 542 Robin, Strenner Péter.
2 points:2 students.
1 point:1 student.
0 point:1 student.


  • Problems in Mathematics of KöMaL, January 2011

  • 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