Feladat: 18.22.
*
Legyen
p egy tetszőleges prímszám és bizonyítsuk be, hogy van olyan
x és
y egész szám, amelyre
x2
+
y2
+1 osztható
p-vel.
Megjegyzés. Ebből a tételből bebizonyítható az a másik nevezetes tétel, hogy bármely egész szám felírható négy négyzetszám összegeként. A bizonyítás szintén használja a skatulyaelvet, egy meglehetősen ,,cseles" formában. Erről olvashatunk Erdős Pál és Surányi János
Válogatott fejezetek a számelméletből c. könyvében ([
173] 246-251. oldal).
Megoldás: 18.22
1. megoldás.
Az előző (=
18.21.) feladatban Annánál is, Bélánál is lehetett végtelen sok szám, csak az volt a fontos, hogy hány különböző maradékot adnak
n-nel osztva. Legyen most
n=p az adott prímszám és osszuk ki Annának a négyzetszámokat, Bélának a négyzetszámnál eggyel nagyobb számokat. Ismeretes, hogy a négyzetszámok
p-vel osztva
(p+1)/2 különböző maradékot adnak (ezek a ,,kvadratikus maradékok"
modp), így mind Annának, mind Bélának ennyi maradéka lesz. (Ha a négyzetszámoknak
(p+1)/2 különböző maradéka van, akkor az ennél eggyel nagyobb számoknak is ugyanennyi van.) Ez összesen
p+1 szám, tehát több, mint
p. Így teljesül az előző feladat feltétele, s ezért van egy négyzetszám és egy (másik) négyzetszámnál eggyel nagyobb szám, amelyek összege osztható
p-vel. Ezt kellett bizonyítanunk.
2. megoldás.
A megoldást elmondhatjuk egy kicsit másképp is, s akkor (látszólag) nincs szükségünk arra, hogy hány ,,kvadratikus maradék" van mod
p.
Tekintsük a
0,1,2,…,(p-1)/2 számok négyzetét, ez
(p+1)/2 szám. Másrészt tekintsük azokat a számokat, amelyeket úgy kapunk, hogy 1-ből levonjuk ezeket a számokat, tehát tekintsük az
-1-
02
,-1-
12
,-1-
22
,… számokat. Ezek összesen
p+1 számot jelentenek. Van tehát közöttük kettő, amelyek ugyanazt a maradékot adják
p-vel osztva. Nem lehet mindkét szám például az elsőben, mert ez azt jelentené, hogy
i2
-
j2
=(i-j)(i+j) osztható volna
p-vel valamely
i<j nem-negatív számpárra, ahol mindkettő legfeljebb
(p-1)/2. De két ilyen számnak mind az összege, mind a különbsége kisebb
p-nél, tehát
(i-j)(i+j) nem lehet osztható
p-vel. Ugyanez az ellentmondás adódna akkor is, ha mindkét szám a második csoportban lenne. Tehát a két szám közül az egyik az első csoportban van, a másik a második csoportban van. Találtunk tehát két számot,
x-et és
y-t, amelyekre igaz, hogy
x2
és
-1-
y2
ugyanazt a maradékot adja
p-vel osztva. Ekkor a különbségük, azaz
x2
+
y2
+1 osztható
p-vel, és éppen ezt akartuk bizonyítani.