Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az A. 567. feladat (2012. szeptember)

A. 567. (a) Határozzuk meg az összes olyan, relatív prím pozitív egész a, b számokból álló (a,b) számpárt, amelyre a2-3 osztható b-vel, és b2-3 osztható a-val.

(b) Határozzuk meg az összes olyan, relatív prím pozitív egész a,b számokból álló (a,b) számpárt, amelyre a2-5 osztható b-vel, és b2-5 osztható a-val.

Javasolta: Pelikán József (Budapest)

(5 pont)

A beküldési határidő 2012. október 10-én LEJÁRT.

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

Statisztika:

12 dolgozat érkezett.
5 pontot kapott:Janzer Olivér, Maga Balázs, Nagy Róbert, Omer Cerrahoglu.
4 pontot kapott:Ágoston Péter, Herczeg József, Kúsz Ágnes.
2 pontot kapott:2 versenyző.
0 pontot kapott:3 versenyző.

A KöMaL 2012. szeptemberi matematika feladatai