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

Problem A. 567. (September 2012)

A. 567. (a) Find all pairs (a,b) of relatively prime positive integers a, b such that b divides a2-3 and a divides b2-3. (b) Find all pairs (a,b) of relatively prime positive integers a, b such that b divides a2-5 and a divides b2-5.

Proposed by: J. Pelikán, Budapest

(5 pont)

Deadline expired on October 10, 2012.

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

Megoldásvázlat. (a) b|a2-3 és a|b2-3 ekvivalens azzal, hogy a és b is osztója (a2+b2-3)-nak. Ha a és b relatív prímek, akkor ez ekivalens azzal, hogy ab|a2+b2-3, avagy, a2+b2-3=kab valamilyen k egész számra. Megfordítva, ha a2+b2-3=kab, akkor a és b relatív prímek, mert d=(a,b) esetén d2|a2+b2-kab=3, ami csak d=1 esetén igaz. A feladat tehát az

a2-kab+b2-3=0(1)

egyenlet olyan (a,b,k) egész megoldásainak megadása, ahol a,b>0.

1. lemma. Ha (a,b,k) egész megoldása az (1) egyenletnek, akkor (a,c,k) is egész megoldás, ahol c=ka-b=\frac{a^2-3}{b}.

Bizonyítás. Rögzített k és a mellett az X2-(ka)X+(a2-3)=0 másodfokú egyenlet egyik gyöke b. A másik gyök a Viéta-formulák szerint c=ka-b=\frac{a^2-3}{b}. A ka-b értéke biztosan egész.

Most rögzítsük k-t, és tekintsük (1)-nek egy olyan (a,b,k) megoldását, ahol a\geb>0. (Az olyan megoldásokat, amelyekben a\leb, az a és b felcserélésévével fogjuk kapni.) Ebből készítsük a következő sorozatot: x0=a, x1=b, xi+1=kxi-xi-1. A lemmából teljes indukcióval kapjuk, hogy (xi,xi+1,k) egész megoldása (1)-nek minden i\ge0 indexre.

Ha valamilyen i\ge1 indexre xi-1\gexi>0, akkor

x_{i+1}=kx_i-x_{i-1}=\frac{x_i^2-3}{x_{i-1}} < \frac{x_i^2}{x_{i-1}} \le x_i.

a sorozat tehát mindaddig monoton csökken, amíg az elemek pozitívak.

Legyen xn+1 az első nempozitív elem: xn+1\le0<xn\lexn-1. A rekurzió és a lemma szerint xn+1xn-1=xn2-3; a baloldal nempozitív, ami csak xn=1 esetén lehetséges; ekkor xn+1xn-1=-2. Az xn-1 szám osztója a (-2)-nek, tehát xn-1=1 vagy xn-1=2.

1. eset: xn-1=1. Ekkor k=\frac{x_n^2+x_{n-1}^2-3}{x_nx_{n-1}}=\frac{1^2+1^2-3}{1\cdot 1}=-1. Mivel xn-2=kxn-1-xn<0, ez csak úgy lehet, ha n=1, és rögtön az a=b=1 számokból indultunk ki.

2. eset: xn-1=2. Ekkor k=\frac{x_n^2+x_{n-1}^2-3}{x_nx_{n-1}}=\frac{1^2+2^2-3}{1\cdot 2}=1. Mivel xn-2=kxn-1-xn=1<xn-1, ez is csak úgy lehet, ha n=1, és rögtön az a=2, b=1 számokból indultunk ki.

A pozitív egész megoldások tehát: (1,1), (1,2), (2,1).

(b) Hasonlóan az első részhez, az

a2-kab+b2-5=0(2)

egyenlet megoldásait keressük.

Az 1. lemma a következőképpen módosul:

2. lemma. Ha (a,b,k) egész megoldása az (2) egyenletnek, akkor (a,c,k) is egész megoldás, ahol c=ka-b=\frac{a^2-5}{b}.

Ismét rögzítsük k-t, és tekintsük (2)-nek egy olyan (a,b,k) megoldását, ahol a\geb>0, és legyen x0=a, x1=b, xi+1=kxi-xi-1. Ha valamilyen i\ge0 indexre xi-1\gexi>0, akkor

x_{i+1}=kx_i-x_{i-1}=\frac{x_i^2-5}{x_{i-1}} < \frac{x_i^2}{x_{i-1}} \le x_i.

Ismét legyen xn+1 az első nempozitív elem: xn+1\le0<xn\lexn-1. Ekkor xn+1xn-1=xn2-5; a baloldal nempozitív, tehát xn=1 vagy xn=2.

Ha xn=2, akkor xn+1xn-1=-1. Viszont a monotonitás miatt xn-1\gexn\ge2, ellentmondás. Tehát xn=1 és xn+1xn-1=xn2-5=-4. Ebből következik, hogy xn-1=1, xn-1=2 vagy xn-1=4.

1. eset: xn-1=1. Ekkor k=\frac{x_n^2+x_{n-1}^2-5}{x_nx_{n-1}}=\frac{1^2+1^2-5}{1\cdot 1}=-3. Mivel xn-2=kxn-1-xn<0, ez csak úgy lehet, ha n=1, és rögtön az a=b=1 számokból indultunk ki.

2. eset: xn-1=2. Ekkor k=\frac{x_n^2+x_{n-1}^2-5}{x_nx_{n-1}}=\frac{1^2+2^2-5}{1\cdot 2}=0. Ezúttal is xn-2=kxn-1-xn<0; ez csak úgy lehet, ha n=1, és rögtön az a=2, b=1 számokból indultunk ki.

3. eset: xn-1=4. Ekkor k=\frac{x_n^2+x_{n-1}^2-5}{x_nx_{n-1}}=\frac{1^2+4^2-5}{1\cdot 4}=3.

Most fordítsuk meg a sorozatot: legyen yi=xn-i, Ekkor tehát y0=1, y1=4 és yi+1=3yi=yi-1. A (b,a) pár ennek a sorzatnak két szomszédos eleme.

Az y_0,y_1,\dlots sorozatot a végtelenségig folyathatjuk: a 2. lemma miatt a sorozatotnak bármelyik két szomszédos eleme megoldást ad k=3-mal.

A megoldások tehát: (1,1), (1,2), (2,1), továbbá (yi,yi+1) és (yi+1,yi) (i=0,1,2,\ldots).

Statistics:

12 students sent a solution.
5 points:Janzer Olivér, Maga Balázs, Nagy Róbert, Omer Cerrahoglu.
4 points:Ágoston Péter, Herczeg József, Kúsz Ágnes.
2 points:2 students.
0 point:3 students.

Problems in Mathematics of KöMaL, September 2012