Kezdőlap


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 \| MathML
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

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 $φ (2^{33}) = 2^{32}$ -t nem veszi fel. Legyen ugyanis

\begin{matrix} n = p_{1}^{α_{1}} \cdot p_{2}^{α_{2}} \cdot ... \cdot p_{k}^{α_{k}}, \end{matrix}

ahol

p_{1}

...

p_{k}

páratlan prímek. Ekkor

\begin{matrix} φ (n) = p_{1}^{α_{1} - 1} \cdot ... \cdot p_{k}^{α_{k} - 1} \cdot (p_{1} - 1) \cdot ... \cdot (p_{k} - 1) . \end{matrix}

Ha valamely

i

-re

α_{i} > 1

, akkor

φ (n)

osztható

p_{i}

-vel, így

φ (n)

nem lehet 2-hatvány. Tehát ha

φ (n)

2-hatvány, akkor minden

i

-re

α_{i} = 1

, azaz

\begin{matrix} φ (n) = (p_{1} - 1) \cdot ... \cdot (p_{k} - 1) . \end{matrix}

Ez viszont csak akkor lehet 2-hatvány, ha

p_{1} - 1

...

p_{k} - 1

mind 2-hatvány. Felhasználjuk azt az ismert tételt (ld. pl. Szalay Mihály: Számelmélet 65. old.), hogy

2^{2^{5}} + 1 = 641 \cdot 6 700 417

, nem prímszám. Ekkor nyilván

φ (2^{2^{5}} + 1) \neq 2^{2^{5}}

. Másfelől, ha

2^{l} + 1

prím valamely

l

egész számra, akkor

l = 2^{m}

alakú, ugyanis ha

l

-nek lenne egy páratlan

p

prímosztója, akkor

2^{l} + 1

osztható lenne

2^{l / p} + 1

-gyel, így nem lenne prím.
Tehát ha

φ (n) = 2^{2^{5}} = (p_{1} - 1) \cdot o t s \cdot (p_{k} - 1)

valamely

p_{1}

...

p_{k}

számokra, akkor

p_{i} - 1 = 2^{2^{l_{i}}} \leq 2^{2^{4}}

alakú. Így

φ (n) = 2^{32}

azt jelentené, hogy

2^{32} = 2^{2^{l_{1}}} \cdot ... \cdot 2^{2^{l_{k}}}

. Azonban

\begin{matrix} 2^{2^{0}} \cdot 2^{2^{1}} \cdot 2^{2^{2}} \cdot 2^{2^{3}} \cdot 2^{2^{4}} = 2^{31} < 2^{32}, \end{matrix}

így a fentiek alapján

φ (n)

semmilyen páratlan

n

-re sem lehet

2^{32}