Feladat: N.44 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Braun Gábor ,  Burcsi Péter ,  Dombi Gergely ,  Gyarmati Katalin ,  Izsák Ferenc ,  Makai Márton ,  Pap Gyula ,  Puskás Zsolt ,  Szádeczky-Kardoss Szabolcs ,  Tóth Gábor Zsolt ,  Újváry-Menyhárt Mónika ,  Valkó Benedek 
Füzet: 1995/március, 167. oldal  PDF file
Témakör(ök): Konstruktív megoldási módszer, Euler-féle számelméleti függvény, Ellenpélda, mint megoldási módszer a matematikában, Nehéz feladat
Hivatkozás(ok):Feladatok: 1994/október: N.44

Igaz-e, hogy az Euler-féle φ függvény a páratlan helyeken minden értékét felveszi?

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.

Megmutatjuk, hogy φ(n) a páratlan helyeken φ(233)=232-t nem veszi fel. Legyen ugyanis

n=p1α1p2α2...pkαk,
ahol p1, ..., pk páratlan prímek. Ekkor
φ(n)=p1α1-1...pkαk-1(p1-1)...(pk-1).
Ha valamely i-re αi>1, akkor φ(n) osztható pi-vel, így φ(n) nem lehet 2-hatvány. Tehát ha φ(n)  2-hatvány, akkor minden i-re αi=1, azaz
φ(n)=(p1-1)...(pk-1).
Ez viszont csak akkor lehet 2-hatvány, ha p1-1, ..., pk-1 mind 2-hatvány. Felhasználjuk azt az ismert tételt (ld. pl. Szalay Mihály: Számelmélet 65. old.), hogy
225+1=6416700417, nem prímszám. Ekkor nyilván φ(225+1)225. Másfelől, ha 2l+1 prím valamely l egész számra, akkor l=2m alakú, ugyanis ha l-nek lenne egy páratlan p prímosztója, akkor 2l+1 osztható lenne 2l/p+1-gyel, így nem lenne prím.
Tehát ha φ(n)=225=(p1-1)ots(pk-1) valamely p1, ..., pk számokra, akkor pi-1=22li224 alakú. Így φ(n)=232 azt jelentené, hogy 232=22l1...22lk. Azonban
220221222223224=231<232,
így a fentiek alapján φ(n) semmilyen páratlan n-re sem lehet 232.