Feladat: N.39 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Braun Gábor ,  Burcsi Péter ,  Dombi Gergely ,  Duzmath Zsolt ,  Farkas Péter ,  Gyarmati Katalin ,  Kiss Márton ,  Makai Márton ,  Pap Gyula ,  Póczos Barnabás ,  Szádeczky-Kardoss Szabolcs ,  Tóth Gábor Zsolt ,  Valkó Benedek 
Füzet: 1995/március, 164 - 165. oldal  PDF file
Témakör(ök): Euler-Fermat-tételek, Maradékos osztás, Euler-féle számelméleti függvény, Nehéz feladat
Hivatkozás(ok):Feladatok: 1994/szeptember: N.39

Mutassuk meg, hogy ha n>3 egész, akkor a 2φ(n)-1 számnak van n-hez relatív prím (valódi) osztója. (φ(n) az n-nél nem nagyobb, n-hez relatív prím pozitív egészek számát jelöli (az ún. Euler-féle φ függvény.)

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. Legyenek n páratlan prímosztói: q1<...<qs; ha az n 2-hatvány, akkor s=0. Jelölje t a legnagyobb olyan egész számot, amelyre
2t(q1-1)...(qs-1).
A φ függvény értékét szolgáltató képlet szerint ekkor
2t(q1-1)...(qs-1)φ(n),
a qi prímek páratlan volta miatt pedig ts. Így
22t-12φ(n)-1,
és itt a bal oldalon álló osztó az egymáshoz páronként relatív prím 220+1, 221+1, ..., 22t-1+1 (páratlan) számok szorzata.
Ha t>s, akkor az előbbi t darab szám között van olyan, amelyik relatív prím n-hez.
A továbbiakban tegyük fel, hogy t=s; ekkor mindegyik qi 4-gyel osztva 3-at ad maradékul. Tételezzük fel továbbá, hogy, a feladat állításával ellentétben, 2φ(n)-1 minden prímosztója a qi prímek közül kerül ki. Ekkor szükségképpen qi=22i-1+1  (1is), így viszont s1, hiszen i2 esetén 22i-1+11(mod4). Ez azt jelenti, hogy az n szám 2α3β alakú. Ha β=0, akkor α3 miatt 3=22-1 valódi (és n-hez relatív prím) osztója 22α-1-1=2φ(n)-1-nek, ellentmondás. Ha β=1, akkor α2 miatt 5222-12φ(n)-1, ellentmondás. Ha pedig β2, akkor 7=23-12φ(n)-1, ugyancsak ellentmondás.
 
Megjegyzés. Több megoldó is úgy fejezte be a bizonyítást, hogy felhasználta 225+1 összetettségét (ld. pl. Szalay Mihály: Számelemélet, 65. old.).
 
II. megoldás. Könnyen látható, hogy elegendő a feladatot páratlan n-re megoldani; azért a továbbiakban feltesszük, hogy n páratlan. Ha n=pk prímhatvány, akkor φ(n)=pk-pk-1 szerint
2φ(n)-1=(2(pk-pk-1)/2-1)(2(pk-pk-1)/2+1).
E két tényező nem lehet egyszerre p-vel osztható, hiszen a különbségük 2. Feltehető tehát, hogy n=ab, ahol a és b 1-nél nagyobb, egymáshoz relatív prím egészek. Ekkor φ(n)=φ(a)φ(b), és φ(a), valamint φ(b) páros. Így φ(n)2 osztható φ(a)-val és φ(b)-vel, következésképpen
2φ(a)-12φ(n)2-1,2φ(b)-12φ(n)2-1.
Az Euler‐Fermat tétel szerint
a2φ(a)-12φ(n)2-1,b2φ(b)-12φ(n)2-1,
így, mivel (a,b)=1, n2φ(n)2-1. Tehát, ha p tetszőleges prímosztója 2φ(n)2+1-nek, akkor p nem oszthatja a 2-vel kisebb 2φ(n)2-1 számot, így n-et sem.
 Dombi Gergely (Fazekas M. Főv. Gyak. Gimn., IV. o.t.) dolgozata alapján