Kezdőlap


Feladat:	F.3262	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Máthé András , Pataki Péter , Szép László , Torda Péter , Vitéz Ildikó
Füzet:	1999/október, 422. oldal		PDF \| MathML
Témakör(ök):	Nevezetes azonosságok, Prímszámok, Oszthatóság, Feladat
Hivatkozás(ok):	Feladatok: 1999/január: F.3262

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.

Alkalmazzuk 1999-szer a $2^{2^{n}} - 1 = (2^{2^{n - 1}} - 1) (2^{2^{n - 1}} + 1)$ azonosságot:

\begin{matrix} \begin{matrix} 2^{2^{1999}} - 1 & = (2^{2^{1998}} - 1) (2^{2^{1998}} + 1) = (2^{2^{1997}} - 1) (2^{2^{1997}} + 1) (2^{2^{1998}} + 1) = \\ = ... = (2^{2^{0}} + 1) (2^{2^{1}} + 1) \cdot ... \cdot (2^{2^{1998}} + 1) . \end{matrix} \end{matrix}

Belátjuk, hogy a

2^{2^{0}} + 1

2^{2^{1}} + 1

...

2^{2^{1998}} + 1

szorzótényezők páronként relatív prímek.

2^{2^{k}} + 1

és

2^{2^{k}} - 1

relatív prímek, mert egymást követő páratlan számok.

(2^{2^{k}} - 1)

-nek viszont osztója

2^{2^{ℓ}} + 1

, ha

ℓ < k

, mivel az előzőek szerint

\begin{matrix} 2^{2^{k}} - 1 = (2^{2^{0}} + 1) (2^{2^{1}} + 1) ... (2^{2^{k - 1}} + 1) . \end{matrix}

Így

ℓ < k

esetén

2^{2^{k}} + 1

és

2^{2^{ℓ}} + 1

relatív prímek.

(2^{2^{1999}} - 1)

-et tehát felbontottuk 1999 darab olyan 1-nél nagyobb szorzótényezőre, amelyek közül bármely kettő relatív prím. Ezért ennek a számnak valóban legalább 1999 különböző prímosztója van.

Vitéz Ildikó (Miskolc, Földes F. Gimn., 11. o.t.)