Feladat: N.114 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bérczi Gergely ,  Braun Gábor ,  Frenkel Péter ,  Gyenes Zoltán ,  Lippner Gábor ,  Lukács László ,  Pap Gyula 
Füzet: 1997/április, 227 - 228. oldal  PDF  |  MathML 
Témakör(ök): Prímszámok, Magasabb fokú kongruenciák, Maradékos osztás, Maradékosztályok, Nehéz feladat
Hivatkozás(ok):Feladatok: 1996/október: N.114

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.

Mivel (a-b)(a2+ab+b2)=a3-b3, és a-b nem lehet osztható p-vel, a p∣a2+ab+b2 feltétel ekvivalens az a3≡b3(modp) feltétellel. Ezen kívül többször felhasználjuk, hogy p≥7.
Ismeretes, hogy minden p prímszámhoz létezik olyan g egész szám (úgynevezett primitív gyök modulo p), amelyre az 1, g, g2, ..., gp-2 számok p-vel való osztási maradékai között az 1, 2, ..., p-1 számok mindegyike pontosan egyszer fordul elő, továbbá
gp-1≡1(modp) (a Fermat-tételnek megfelelően). (A bizonyítást lásd pl. Niven‐Zuckermann: Bevezetés a számelméletbe, 49‐50. old.) Ennek következménye, hogy tetszőleges 3k+1 alakú p prímszámra létezik olyan h egész szám, amely nem kongruens 1-gyel modulo p, viszont h3≡1(modp); ilyen szám például a gp-13.
Azt állítjuk, hogy léteznek olyan x, y egész számok, amelyekre 0<x, |y|<p, valamint hx≡h(modp). Tekintsük a hu-v alakú számokat, ahol 0≤u,v≤[p] egészek. Ez összesen ([p]+1)2>p darab egész szám, van közöttük kettő, amelyek ugyanabba a p szerinti maradékosztályba esnek: hu1-v1≡hu2-v2(modp), vagyis p∣(u1-u2)h-(v1-v2). Legyen x=u1-u2 és y=v1-v2. Ekkor az |x|, |y|<p, hx≡y(modp) feltételek teljesülnek, és az általánosság megszorítása nélkül feltehetjük, hogy x>0, mert x-et és y-t kicserélhetjük (-x)-re és (-y)-ra. Még azt kell megmutatnunk, hogy x és y különbözőek, és egyikük sem 0. Tegyük fel, hogy y=0; ekkor p∣hx. Mivel h nem osztható p-vel, ebből p∣x következik, viszont |x|<p miatt ez csak x=0 esetén lehetséges. Ha viszont x=y=0, az ellentmond annak, hogy az (u1,v1) és (u2,v2) számpárok különbözők. Az x=0 esetben hasonlóképpen jutunk ellentmondásra. Ha x és y nem lennének különbözőek, akkor p∣(h-1)x lenne, viszont sem h-1, sem x nem osztható p-vel.
Mivel
(x-y)(x2+xy+y2)=x3-y3≡(hx)3-y3-(hx-y)(h2x2+hxy+y2)≡0(modp),
és 0<|x-y|<2p<p, így p∣x2+xy+y2. Ha megmutatjuk, hogy y>0 is teljesül, kész vagyunk: x, y közül a kisebbiket a-nak, a nagyobbikat b-nek választva megfelelő számpárt nyerünk.
Tegyük fel, hogy y<0. Ekkor x≤|y| esetén
x2+xy+y2≤x|y|+xy+y2=y2<p,
x>|y| esetén pedig
x2+xy+y2≤x2+xy+x|y|=x2<p.
Viszont
x2+xy+y2=12(x2+y2+(x+y)2)>0,
és így x2+xy+y2 nem lehet osztható p-vel.
 Frenkel Péter (Fazekas M. Főv. Gyak. Gimn., IV. o.t.)

 
Megjegyzések. 1. Többen észrevették, hogy 0<a,b<p teljesülése esetén
p∣a2+ab+b2 ekvivalens azzal, hogy a2+ab+b2=p. Ez azért igaz, mert 0<a2+ab+b2<3p, és a2+ab+b2=2p nem lehetséges. (Ebben az esetben ugyanis a és b is páros kellene legyen, viszont 2p nem osztható 4-gyel.)
2. Legyen ϱ=12+32i az első hatodik komplex egységgyök. Az x+yϱ (x, y egészek) alakú komplex számokat Euler-egészeknek nevezik. Egyszerű számolással ellenőrizhető, hogy |x+yϱ|2=x2+xy+y2. A feladat tehát, figyelembe véve az előbbi megjegyzést, olyan a+bϱ Euler-egész létezésének bizonyítása volt, amelyre |a+bϱ|2=p, valamint 0<a<b<p.
Ismeretes (lásd pl. Gyarmati‐Turán: Számelmélet, 431‐432. old.), hogy ha p
3k+1 alakú prím, akkor pontosan 12 olyan Euler-egész létezik, amelyek abszolút értékének négyzete éppen p. Ezek közül hat egymásból úgy kapható, hogy egy megfelelő hatodik egységgyökkel megszorozzuk őket, a többi hat pedig ezek konjugáltja. A 0<a<b feltétel azzal ekvivalens, hogy a keresett Euler-egész argumentuma (szöge) 0∘ és 30∘ közé esik. Az ilyen egész létezése az előbbiekből következik. Végül a b<p feltétel is teljesül, mert b2<a2+ab+b2=p.