Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 4326. (January 2011)

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

Deadline expired on February 10, 2011.


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

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:

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