Cím: Számhármasok II.
Szerző(k):  Csikvári Péter 
Füzet: 2005/november, 451 - 458. oldal  PDF  |  MathML 
Témakör(ök): Egyéb írások

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Az első részben1 azt a kérdést vetettük föl, hogy milyen számhármasokat lehet előállítani egy adott (a;b;c) számhármasból kiindulva, ha egy-egy lépésben felcserélhetjük egy számhármasban az elemek sorrendjét, illetve egy már meglévő (x;y;z) számhármasból elkészíthetjük az (x;y;2x+2y-z) számhármast. Az (a;b;c)↝(x;y;z) jelölést használtuk arra, hogy az (a;b;c) számhármasból el lehet jutni az (x;y;z) számhármasba. Láttuk, hogy ez ekvivalencia reláció. Bevezettük az n(a;b;c)=a2+b2+c2-2ab-2bc-2ca mennyiséget, amelyről láttuk, hogy invariáns, nem változik a lépések során: az egyes ekvivalencia osztályokon belül tehát állandó. Ha a+b+c páros, akkor az N(a;b;c)=14n(a;b;c) egész számot a számhármas normájának hívtuk. Ez az invariáns közvetlenül nem bizonyult elég érzékenynek az A. 376. feladat megoldására: N(5;13;42)=N(1;21;42)=79 és mivel nem bizonyítottuk be ‐ nem is igaz ‐, hogy egyenlő normájú számhármasok ekvivalensek, a fenti egyenlőség ténye nem válaszolja meg a feladat kérdését. Most mutatunk egy az eddigieknél sokkal ravaszabb invariánst. A számolások során hivatkozás nélkül használjuk majd a norma tulajdonságait, amelyeket a cikk első részében igazoltunk.

 
Lánctörtek
 

Egy z valós számhoz hozzárendelhetünk egy lánctört alakot:
z=a0+1a1+1a2+1⋱.
Az a0,a1,a2,... egész számokat a lánctört jegyeinek hívjuk és a következőképpen számolhatók: legyen z0=z, a0=[z0], z1=1z0-[z0], ha z0 nem egész, a1=[z1], általában pedig zi=1zi-1-[zi-1], ha zi-1 nem egész és ai=[zi]. Ha zi egész, akkor megállunk.
 
Példa.
-5,6=-6+0,4=-6+12,5=-6+12+0,5=-6+12+12.
Ha z nem racionális, akkor nem kaphatunk véges lánctörtet, mert ezek racionálisak. Ilyenkor egészek végtelen sorozatát kapjuk.
 
Példa.
2=1+(2-1)=1+12+1=1+12+(2-1)==1+12+12+1=1+12+12+1⋱.
A következőkben ezt úgy jelöljük, hogy
-5,6=L(-6;2;2),  illetve  2=L(1;2;2;...)=L(1;2¯).
Könnyen látható, hogy a0∈Z tetszőleges lehet, de a1-től kezdve a jegyek pozitívak, ugyanis 1>zj-[zj]≥0. (Részletesebb) bevezetést ad a lánctörtekbe Freud Róbert ‐ Gyarmati Edit: Számelmélet című könyvének 8.3. fejezete.
A továbbiakban olyan speciális számokra lesz szükségünk, amelyek lánctört alakja periodikus. A fenti példák közül ilyen a 2: a lánctört alak periódusa az egytagú ,,2'' sorozat, amit így jelölünk: L˜(2)=(2). A periodicitást itt is úgy értelmezzük, mint a tizedestörteknél: elegendő, ha az an sorozat valahonnan kezdve periodikus, azaz ha z1=L(3;1;2¯), z2=L(5;1;4;2¯), akkor L˜(z1)=L˜(z2)=L˜(2)=(2).
 
Feladat. Milyen szám lánctört alakjai az alábbi sorozatok:
L(2;2;...)=L(2¯);L(3;1;2¯);L(5;1;4;2¯)?

Most bizonyítás nélkül kimondunk két tételt.
 
III. tétel2. A z szám lánctört alakja akkor és csak akkor periodikus, ha z=a+bc alakú, ahol a, b, c egészek, b>0 nem négyzetszám és c≠0.
 

Hívjuk a z1 és a z2 valós számokat hasonlónak, ha a két szám lánctört alakjában véges sok, nem feltétlenül ugyanannyi kezdeti jegyet elhagyva a megmaradó jegyek sorozata azonos. Két véges lánctört nyilván hasonló és hasonlók például azok a számok is, amelyeknek L(3;1;2¯), illetve L(5;1;4;2¯) a lánctört alakja.
 
IV. tétel. A z1 és z2 valós számok pontosan akkor hasonlók, ha léteznek olyan m, n, k, ℓ egészek, amelyekre |kn-mℓ|=1 és z2=kz1+ℓmz1+n.
 

A IV. tételnek valójában csak arra a következményére van szükségünk, hogy ha z1 lánctörtalakja periodikus, és z2 a tétel szerinti kifejezése z1-nek, akkor z1 és z2 hasonlók. A hasonlóság ebben az esetben azt jelenti, hogy z2 lánctört alakja is periodikus, a két periódus azonos, L˜(z1)=L˜(z2), bár az egyenlő periódusok a két lánctört alakban általában nem ugyanott kezdődnek.
 
Feladatok. a) Legyen z1=56, z2=47. Írjuk fel z2-t z2=kz1+ℓmz1+n alakban, ahol |kn-mℓ|=1. Oldjuk meg a feladatot akkor is, ha z1=L(3;1;2¯) és z2=L(2¯).
b) Adott valós számokra legyen z1∼z2, ha z2 felírható z1 segítségével a IV. tétel szerinti alakban. Igazoljuk, hogy ∼ a valós számok halmazán ekvivalencia reláció.
c) Igazoljuk, hogy ha z1 és z2 racionális számok, akkor z2 felírható z1 segítségével a IV. tétel szerinti alakban.
 
Megoldás az A. 376. feladatra. Tekintsük a következő kifejezést:
[a;b;c]=a+b-c2+N(a;b;c)a.
Ekkor
a+b-c2+N(a;b;c)a⋅-(a+b-c)2+N(a;b;c)b=N(a;b;c)-(a+b-c2)2ab=-1.
Azt kaptuk, hogy [a;b;c]⋅([b;c;a]-1)=-1, vagyis [b;c;a]=1-[a;b;c]-1. A III. tétel szerint [a;b;c] lánctört alakja periodikus, ha a≠0 és N(a;b;c) nem négyzetszám. A IV. tétel feltételei tehát teljesülnek a k=m=1, ℓ=-1, n=0 szereposztással, ezért a két szám, [a;b;c] és [b;c;a] lánctört alakjának azonos a periódusa: L˜([a;b;c])=L˜([b;c;a]).
Az L˜([a;b;c]) sorozat tehát nem változik, ha a számhármas elemeit ciklikusan permutáljuk. Az a, b, c elemek hatféle permutációja így ‐ legfeljebb ‐ két lánctörtperiódust határoz meg: L˜([a;b;c])-t és L˜([b;a;c])-t. Nézzük most meg, mi történik L˜([a;b;c])-vel a másik, (a;b;c)→(a;b;2a+2b+c) lépés során.
A definíciók alapján könnyen ellenőrizhető, hogy
=a+b-(2a+2b-c)2+N(a,b,2a+2b-c)a==-a+b-c2+N(a;b;c)a=-[b;a;c]-1.
Mivel a IV. tétel szerint L˜(-[b;a;c]-1)=L˜([b;a;c]), azért innen
L˜([a;b;2a+2b-c])=L˜([b;a;c])
következik: az (L˜([a;b;c]);L˜([b;a;c])) pár tehát invariáns! Hogy tényleg olyan erős, mint ahogy ígértük, az nyomban kiderül, amint ráeresztjük az A. 376. feladatra:
=-12+795=L(-1;2;1;1;1;5;3¯),[13;5;42]=-12+7913=L(-1;1;3;5;1;1;1;2¯),[1;21;42]=-10+791=L(-2;1;7;1;16¯),[21;1;42]=-10+7921=l(-1;1;17;1;7;1;16¯).
Azt kaptuk, hogy L˜([5;13;42])=(2;1;1;1;5;3) és L˜([13;5;42])=(3;5;1;1;1;2), míg
L˜([1;21;42])=L˜([21;1;42])=(1;7;1;16).
Mivel ez a két perióduspár nem azonos, nem juthatunk el az (5;13;42) számhármasból az (1;21;42) számhármasba a megadott lépésekkel.
 
Megjegyzés. Meg lehet mutatni, hogy az L˜([a;b;c]) és L˜([b;a;c]) periódusok általában is vagy egyenlők, vagy pedig egymás palindromái. Ami fontosabb, hogy egy ilyen perióduspár már majdnem egyértelműen határozza meg a számhármas ekvivalencia osztályokat: ha két számhármasra ez a pár azonos, akkor bármelyikükből el lehet jutni a másiknak egy racionális többszörösébe a megadott lépésekkel. Meg lehet ugyanis mutatni, hogy egy periodikus lánctörttel rendelkező z számból el lehet jutni egy tisztán periodikus lánctörthöz az f(z)=-1z és g(z)=1-1z függvények néhány egymásutáni alkalmazásával. Egy tisztán periodikus lánctörtből pedig kiszámolhatjuk [a;b;c]-t. Az egyetlen probléma, hogy [a;b;c]=[ka;kb;kc] miatt a tisztán periodikus lánctört csak konstans szorzó erejéig határozza meg a számhármast, de az könnyen meggondolható, hogy ha [a;b;c]=[x;y;z], akkor létezik olyan r racionális szám, hogy r(a;b;c)=(x;y;z).
 
Egy osztály gráfja
 

Egy ekvivalencia osztály természetes módon meghatároz egy gráfot. Mivel a ↝ relációban érdektelen az elemek sorrendje, a gráf csúcsai legyenek az ekvivalens számhármasok elemeiből álló háromelemű halmazok és egy (a;b;c) számhármast kössünk össze éllel a belőle közvetlenül elérhető (a;b;2a+2b-c), (a;2a+2c-b;c), (2b+2c-a;b;c) számhármasokkal. Lehetséges, hogy e három számhármasból kettő azonos, sőt, az is megtörténhet, hogy egyikük megegyezik az eredetivel: a hurokélt ilyenkor hagyjuk el. Az így adódó gráf nyilván összefüggő, a csúcsai pedig legfeljebb harmadfokúak.
Tekintsük az olyan számhármasokat, amelyekben van pozitív és negatív szám is. Hívjuk az ilyen számhármasokat maghármasoknak. Ezek a fenti gráf egy részgráfját feszítik ki, amelyet magnak fogunk hívni. A magban a pontok foka legfeljebb kettő, ugyanis egy maghármas eltérő előjelű számát lecserélve nem magbeli számhármast kapunk.
Célunk a mag és az eredeti gráf leírása.
Az első kérdés, hogy van-e egyáltalán maghármas, illetve ha igen, akkor hány van. Láttuk, hogy egy osztályon belül n(a;b;c) invariáns. Azt állítjuk, hogy ha ez a mennyiség az adott osztályra nem pozitív, akkor az osztály nem tartalmaz maghármast, ha pedig pozitív, akkor legfeljebb csak véges sokat. Tegyük fel ugyanis, hogy a<0<b. Ekkor
(a+b-c)2=n(a;b;c)+4ab≤n(a;b;c)-4.
Ha n(a;b;c)≤0, akkor ez nyilván nem lehetséges. Ha n(a;b;c)>0, akkor csak véges sok négyzetszám kisebb n(a;b;c)-nél és mindegyikük legfeljebb véges sok (a;b) és így legfeljebb véges sok (a;b;c) számhármast határoz meg. □
 
Feladatok. a) Bizonyítsuk be, hogy n(0;k;ℓ) négyzetszám.
b*) Bizonyítsuk be, hogy ha n(a;b;c) négyzetszám, akkor léteznek olyan k,ℓ egészek, hogy (a;b;c)↝(0;k;ℓ).
 

Legyen n(a;b;c) adott. Az A. 376. feladat megoldásakor láttuk, hogy az n(a;b;c) invariáns nem választja szét az ekvivalencia osztályokat, több olyan ekvivalencia osztály is lehetséges, amelynek elemeire n(a;b;c) ugyanaz az érték. Megmutatjuk, hogy ha n(a;b;c)>0 és nem négyzetszám, akkor ha nem is egyetlen, de mindenképpen csak véges sok olyan osztály van, amelynek elemeire n(a;b;c) az adott értékkel egyenlő. Ehhez elég megmutatni, hogy minden osztályban van maghármas, ezek száma ugyanis, mint láttuk, véges. Mivel n(a;b;c) nem négyzetszám, így a fenti feladat szerint egyetlen számhármas sem tartalmazhatja a 0-t. Másrészt három pozitív számot tartalmazó számhármas nem lehet összekötve három negatív számot tartalmazó számhármassal, hiszen szomszédos számhármasokban két szám azonos. Ha tehát n(a;b;c) nem négyzetszám és az (a;b;c) számhármas osztálya nem tartalmaz maghármast, akkor az ekvivalencia osztály minden számhármasa azonos előjelű számokból áll: mindegyikük pozitív vagy mindegyikük negatív. A (-1)-gyel való szorzás miatt feltehetjük, hogy minden számhármas csupa pozitív számot tartalmaz. Ennek mond ellent az alábbi
 
V. tétel. Ekvivalensek az (a;b;c) egész számhármasokra:
(1) minden x, y, z számhármasra (melyre (a;b;c)↝(x,y,z)) teljesül, hogy x,y,z>0;
(2) n(a;b;c)<0 és a>0.
 

Bizonyítás. (1)⇒(2).  a>0 triviálisan teljesül. Tegyük fel, hogy n=n(a;b;c)≥0, ekkor persze N=14n>0 (még ha nem is feltétlenül egész). Legyen 0<x≤y≤z olyan, hogy (a;b;c)↝(x;y;z) és x+y+z minimális. Ekkor 2x+2y-z≥z, így x+y≥z. Tehát z=x+y-2xy+N≥y, így x≥2xy+N≥2x2+0=2x, ami ellentmondás.
(2)⇒(1).  xy=(x+y-z2)2-N>0 így x, y, z előjele megegyezik, ez minden lépésben teljesül. Mivel a>0, így a végén x,y,z>0.
 

Tehát azonnal kapjuk, hogy véges sok osztály van, ha n(a;b;c)>0.
 
Feladatok. a) Bizonyítsuk be, hogy akkor is véges sok osztály van, ha n(a;b;c)<0, vagy ha pozitív négyzetszám.
b) Igazoljuk, hogy ha n(a;b;c)=0, akkor végtelen sok osztály van. Mik ezek?
 

Folytassuk a névadást: azon számhármasokat, amelyekben mind a három szám előjele megegyezik, héjhármasoknak fogjuk hívni. Tekintsük a 0<a≤b≤c számokat. Ezekre 2b+2c-a>c, illetve 2a+2c-b>c, tehát, ha a-t vagy b-t lecseréljük, akkor olyan héjhármast kapunk, amelyben a legnagyobb szám értéke nőtt. Hasonló állítás igaz a negatív elemű számhármasokra is. Ennek az egyszerű észrevételnek messzemenő következményei vannak:
 
VI. tétel. a) Héjhármasok nem alkothatnak kört.
b) Két maghármast nem köthet össze héjhármasokból álló út.
 

Bizonyítás. Mindkét esetben feltehetjük, hogy a héjhármasok pozitív számhármasokból állnak (ha nem, akkor szorozzuk az egészet (-1)-gyel).
a) Tegyük fel, hogy van héjhármasokból álló kör és tekintsük a körben előforduló legnagyobb számot. Legyen ez cm, az ezt tartalmazó számhármas pedig legyen (am;bm;cm), ahol 0<am≤bm≤cm. Az észrevétel szerint am-et vagy bm-et lecserélve cm-nél nagyobb számot kapunk, tehát a számhármas mindkét szomszédjánál cm-et kellett lecserélnünk. A két szomszéd tehát megegyezik, ez pedig körben nem lehetséges.
b) Tegyük fel, hogy van két maghármast összekötő héjhármasokból álló út. Legyen t1→t2→...→tn-1→tn egy út a gráfban, ahol tk=(ak;bk;ck). Feltehetjük, hogy a1<0<b1≤c1 és an<0<bn≤cn és 0<ak≤bk≤ck, ha 2≤k≤n-1. Most is vegyük a 3n szám közül a legnagyobbat. Az előbbi gondolatmenet szerint ez nem lehet c2,...,cn-1 egyike sem. Nem lehet viszont c1 és cn sem, mert az első lépésben biztosan a negatív a1-et cseréljük le 2c1+2b1-a1>c1-re, míg az utolsóban a negatív an-et 2cn+2bn-an>cn-re. Ez az ellentmondás bizonyítja az állításunkat. □
 

Ez az egyszerű tétel magában is elintézi az A. 376. feladatot. Tekintsük ugyanis az (5;13;42) számhármas osztályának a gráfját. Lépjünk egyet: (5;13;42)→(5;13;-6), majd a talált maghármasból indulva járjuk be a magot: egy kört kapunk (ábra).
 
 

Mivel két maghármast nem köthet össze héjhármasokból álló út, azért a mag általában is összefüggő részgráf és egy-egy maghármasból ,,leágazó gráf'' csupa héjhármasból áll. Az így adódó ,,héjak'' ráadásul diszjunktak, megint csak amiatt, hogy két maghármast nem köthet össze héjhármasokból álló út. Mivel láttuk, hogy a héjak körmentesek, mindegyikük egy-egy végtelen bináris fa.
Általában pedig a gráf magja összefüggő gráf, amelyben minden csúcs foka legfeljebb kettő; a mag tehát vagy egy kör, mint az ábrán, vagy pedig egy út. Remélem, a gráf szerkezete indokolja a furcsa elnevezések eredetét.
Mivel (1;21;42)→(1;21;2)→(1;-15;2) és ez a maghármas nincs benne az (5;13;42) osztályának magjában (ábra), azért (1;21;42)/↝(5;13;42).
Ezzel ismét megoldottuk az A. 376. feladatot.
 
Feladat. Írjuk le az (1;21;42) osztályának a gráfját. Mi lesz a mag?
 

Érdemes még elidőzni egy kicsit a mag szerkezeténél. Minden maghármasban van egy szám, amelynek előjele különbözik a másik kettőétől: az ábrán ezek (vastagon szedve) a következők: 5, -3, 10, -7, 9, -6. Ezek a számok rendre 3, 5, 1, 1, 1, 2-ször fordulnak elő a magban ebben a sorrendben. Ez a számsorozat nem más, mint L˜(13;5;42), a már látott (3;5;1;1;1;2) lánctörtperiódus! Szemléletesen szólva a lánctörtek jegyei valamilyen ,,útleírást'' adnak meg: hogyan menjünk le a héjról a magig, majd ott körbe-körbe; ennek részletesebb vizsgálatát az Olvasóra hagyjuk.
Említettük, hogy a mag lehet út is. Erre akkor kerül sor, ha találunk benne egy elsőfokú csúcsot. Ekkor persze van a magban egy másik elsőfokú csúcs is, az út másik végpontja. Ennek az egyszerű észrevételnek nagyon hasznos következményei lehetnek:
 
Feladat. a) Legyen p  4k-1 alakú prím. Mutassuk meg, hogy az x2-py2=2 vagy az x2-py2=-2 egyenletek valamelyikének van egész x, y megoldása. (Segítség: az (1;-(p-1);-p) az út egyik végpontja, mi a másik? Használjuk a 2. tételt a cikk első részéből.)
b) Mit mondhatunk, ha p  4k+1 alakú prím?
 
Visszatekintés
 

Azt hiszem, tanulságos, hogy egy egyszerű ,,játék'' vizsgálata hogyan vezetett el a másodfokú diofantikus egyenletek elméletéhez. A B. 3822. és az A. 376. feladatok megoldására tett kísérleteink során több megközelítés is kínálkozott: mozgósítottuk a periodikus lánctörtek elméletét, valamint a gráfelmélet eszközeit is. Noha egyszerű észrevételeken múlt, a kapott gráfok szerkezetének a leírása igen hatásos eszköznek bizonyult. A rengeteg feladat talán mutatja, hogy közel sem mondtam el mindent, amit erről a témakörről tudni lehet; aki kedvet kap a további kutatáshoz, maga is biztosan találhat érdekes új eredményeket, vagy újszerű bizonyítást egy-egy már ismert tételre.
 
Köszönöm Pataki Jánosnak értékes észrevételeit.
1KöMaL, 2005/10, 398‐405. oldal.

2A III. tétel bizonyítása megtalálható Niven ‐ Zuckerman, Bevezetés a Számelméletbe, Műszaki Kiadó (Budapest, 1978) c. könyvének 146‐148. oldalán.