Feladat: F.2556 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Hajdú Gábor ,  Majoros László 
Füzet: 1986/november, 362 - 364. oldal  PDF file
Témakör(ök): Algebrai átalakítások, Maradékos osztás, Oszthatósági feladatok, Prímszámok, Számtani sorozat, Természetes számok, Feladat
Hivatkozás(ok):Feladatok: 1985/december: F.2556

Igaz-e, hogy ha a természetes számok közül elhagyjuk a háromszögszámokat, a maradó számok között van végtelen számtani sorozat? (Háromszögszámnak nevezzük azokat a számokat, amelyek valamely n természetes számra n(n-1)2 alakúak.)

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.

I. megoldás Megmutatjuk, hogy a feladat kérdésére igenlő a válasz: a 3k+2 (k=0,1,2,...) alakú számok egyike sem háromszögszám, így ezek elhagyása után a 2, 5, 8, ..., 3k+2, ... végtelen számtani sorozat minden tagja megmarad.
Állításunk igazolásához elég azt belátni, hogy egy háromszögszám, azaz egy n(n-1)2 alakú szám hárommal osztva nem adhat 2 maradékot. Ha n vagy n-1 valamelyike osztható hárommal, akkor n(n-1) és így ennek fele, n(n-1)2 is osztható hárommal. (Felhasználtuk, hogy 2 és 3 relatív prímek.)
Ha sem n, sem pedig n-1 nem osztható hárommal, akkor n+1 osztható hárommal, tehát 3l alakú, és így n(n-1)=(3l-1)(3l-2)=9l2-9l+2==9l(l-1)+2 alakú. Itt l és l-1 szomszédos egészek, szorzatuk páros, ezért 9l(l-1) osztható 18-cal.

 

Azt kaptuk, hogy n(n-1) 2 maradékot ad 18-cal osztva, s ezért n(n-1)2 kilenccel és így hárommal osztva is 1-et. Tehát n(n-1)2 valóban nem ad 2 maradékot hárommal osztva, ahogyan állítottuk.
A fentiekből az is következik, hogy a háromszögszámok kilenccel osztva csak 0, 1, 3 vagy pedig 6 maradékot adnak, így elhagyásuk után a következő végtelen számtani sorozatok is megmaradnak:
2,11,20,...,9k+2,...4,13,22,...,9k+4,...5,14,23,...,9k+5,...7,16,25,...,9k+7,...8,17,26,...,9k+8,...



Megjegyzés. Hasonlóan igazolható, hogy a 2, 7, ..., 5k+2, és a 4, 9, 14, ..., 5k+4, ... sorozatok minden tagja megmarad, ugyanis egy háromszögszám öttel osztva csak 0, 1 vagy 3 maradékot adhat.
 

II. megoldás. Most egy általánosabb állítást bizonyítunk be. Láttuk, hogy mind hárommal, mind pedig öttel osztva van olyan maradék (pl. a 2, ill. a 4), ami nem fordul elő a háromszögszámok között, és így a 3k+2 (k=1,2,...), illetve az 5k+4 (k=1,2,...) végtelen számtani sorozatok megmaradnak a háromszögszámok elhagyása után. Most igazoljuk, hogy tetszőleges p páratlan prímszámhoz van olyan maradék, amelyet n(n-1)2 alakú szám nem adhat p-vel osztva.
Ehhez két dolgot fogunk belátni.
1. Ha n osztható p-vel, vagy p-vel osztva 1 maradékot ad, akkor n(n-1)2 osztható p-vel. Ez nyilvánvaló, hiszen n(n-1) osztható p-vel, s így a fele is (mert 2 és p relatív prímek).
2. Hogy n(n-1)2 a p-vel osztva mennyi maradékot ad, az csakis attól függ, hogy az n mennyi maradékot ad p-vel osztva. (p=3-ra ezt tulajdonképpen beláttuk az első megoldásban.) Ez következik abból, hogy ha n és m ugyanazt a maradékot adják p-vel osztva, akkor n(n-1)2 és m(m-1)2 is ilyenek. Valóban:
n(n-1)2-m(m-1)2=n2-m2+n-m2=(n-m)(n+m+1)2.
Feltevésünk szerint itt (n-m) osztható p-vel, tehát a számláló, és így a fele is osztható p-vel, mert (2,p)=1. ((n-m)(n+m+1)2 egész, hiszen két egész különbsége.) Ezzel a 2. állításunkat is beláttuk.
Nézzük most meg, hogy n(n-1)2 hányféle maradékot adhat p-vel osztva. Az n nyilván p különböző maradékot adhat, a 0-t, az 1-et, a 2-t, ... és a (p-1)-et. Az első két esetben az 1. állítás szerint n(n-1)2 osztható p-vel. Marad p-2 lehetőség, s miután a 2. állítás szerint n(n-1)2 maradéka csak az n maradékától függ, n(n-1)2 legfeljebb p-2 különböző maradékot adhat a maradó p-2 esetben. Az n(n-1)2 tehát legfeljebb (p-1) különböző maradékot adhat p-vel osztva, és mivel p különböző maradék van, így legalább egy maradék valóban "kimarad''. Ezzel az állításunkat igazoltuk.
A fentiek után már következik, hogy tetszőleges p páratlan prímszámra van p különbségű végtelen számtani sorozat a "nem-háromszögszámok'' között, és így persze az is igaz, hogy ha d pozitív egész és van páratlan prímosztója (d nem kettőhatvány), akkor d különbségű végtelen számtani sorozat is van a "nem‐háromszögszámok'' között.
 

(S. L.)
 

Megjegyzés. Bizonyítható, hogy ha d kettőhatvány, akkor nincs d különbségű végtelen számtani sorozat a "nem-háromszögszámok'' között.