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

 

Problem A. 567. (September 2012)

A. 567. (a) Find all pairs (a,b) of relatively prime positive integers ab such that b divides a2-3 and a divides b2-3. (b) Find all pairs (a,b) of relatively prime positive integers ab 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.

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