Feladat: Pontversenyen kívüli P.97 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Cseresnyés Mária ,  Ferró József ,  Füredi Zoltán ,  Hermann Péter ,  Katona Endre ,  Komornik Vilmos ,  Móri Tamás ,  Pásztor Miklós ,  Reviczky János ,  Szendrei Ágnes ,  Szendrei Mária 
Füzet: 1971/szeptember, 25. oldal  PDF file
Témakör(ök): Oszthatóság, Teljes indukció módszere, Pontversenyen kívüli probléma
Hivatkozás(ok):Feladatok: 1971/március: Pontversenyen kívüli P.97

Egy természetes számot négyzetesnek nevezünk, ha van négyzetszámosztója (természetesen 1-nél nagyobb). Igaz-e, hogy tetszőleges k természetes számhoz található k szomszédos négyzetes szám?

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.

Teljes indukcióval bebizonyítjuk, hogy a feladat kérdésére igenlő válasz adható. Ha k=2, két szomszédos négyzetes szám például a 8 és a 9. Tegyük fel, hogy valamilyen k természetes számhoz már találtunk k szomszédos négyzetes számot, legyen ezek között a legkisebb a, és legyen ezeknek a legkisebb közös többszöröse d. Megmutatjuk, hogy ezek alapján megadható (k+1) szomszédos négyzetes szám is.
Tetszőleges n természetes szám mellett az

nd+a,(nd+a)+1,...(nd+a)+(k-1)(1)
számok is négyzetesek. Valóban, feltevésünk szerint d osztható (a+j)-vel (ahol 0jk-1), így (nd+a)+j is osztható (a+j)-vel, és ugyancsak a feltevésünk szerint (a+j)-nek van négyzetszám osztója.
Megmutatjuk, hogy található olyan n, melyre (nd+a)-1 is négyzetes, ekkor ez az (1) alatti számokkal együtt már (k+1) szomszédos szám, és mindegyikük négyzetes. Legyen p tetszőleges prímszám, mellyel d nem osztható (p lehet például (d+1) bármelyik törzstényezője), és jelöljük p2-et röviden q-val, (a-1)-et b-vel. Azt állítjuk, hogy a
d+b,2d+b,3d+b,...,qd+b(2)
számok között van q-val osztható. Ha ugyanis ez nem volna így, akkor e számokat q-val osztva mindig az 1, 2, ..., q-1 maradékok valamelyikét kapnánk. Összesen q maradékot kapunk, amennyi a (2) számok száma, a lehetőségek száma pedig csak (q-1), így volna olyan maradék, amelyiket kétszer is megkaptunk. Legyen mondjuk az id+b és a jd+b számokra ugyanaz a maradék, ahol 1i<jq. Ekkor a
(jd+b)-(id+b)=(j-i)d
különbség osztható volna q-val, viszont d még p-vel sem osztható, és 0<j-i<q miatt (j-i) sem osztható q-val. Ellentmondásra jutottunk, tehát a (2) alatti számok között valóban van q-val osztható. Legyen, mondjuk, ez az (id+b) szám, ekkor n=i mellett (nd+a)-1 négyzetes, hiszen osztható q=p2-tel. Ezzel a feladat állítását bebizonyítottuk.
 

Megjegyzések. 1. Biztosan négyzetes az (nd+a)-1 szám n=(a-1)(d+2) mellett, hiszen ekkor
nd+a-1=(a-1)(d+2)d+(a-1)=(a-1)(d+1)2.

2. Hasonlóan bizonyítható, hogy tetszőleges k és n természetes számokhoz található k szomszédos természetes szám, melyek mindegyike osztható egy (1-nél nagyobb) természetes szám n-ik hatványával.