Kezdőlap


Feladat:	Pontversenyen kívüli P.305	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Alberti G. , Angyal T. , Bene Gy. , Bölcsföldi L. , Cseri I. , Erdélyi Szabó M. , Erdélyi T. , Fordán T. , Gaál I. , Hajnal P. , Hidas P. , Hollós P. , Kis-Kós L. , Kiss 352 György , Mészáros a. , Nagy 647 G. , Pátkai Andrea , Pintér 395 F. , Sz. Nagy Cs. , Varga L.
Füzet:	1979/április, 169. oldal		PDF \| MathML
Témakör(ök):	Nevezetes azonosságok, Rekurzív eljárások, Maradékos osztás, Prímszámok, Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1978/szeptember: Pontversenyen kívüli P.305

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.

Könnyen látható, hogy $a_{n} = 5^{2^{n - 1}}$ , vagyis azt kell belátnunk, hogy az $a_{n} - 1 = 5^{2^{n - 1}} - 1$ számnak legalább $n$ különböző prímosztója van. Ezt teljes indukcióval bizonyítjuk be.
$n = 1$ -re állításunk nyilvánvaló. Tegyük fel, hogy igaz $n = k$ -ra, be kell látnunk, hogy akkor $n = k + 1$ -re is igaz.

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

Indukciós feltevésünk miatt az

a_{k} - 1

számnak legalább

k

különböző prímosztója van. Azt kell már csak bebizonyítani, hogy

(a_{k} + 1)

-nek van olyan prímosztója, amely nem osztója

(a_{k} - 1)

-nek. Vegyük észre, hogy

\begin{matrix} (a_{k} - 1, a_{k} + 1) = 2. \end{matrix}

(1)

Ugyanis ha

(a_{k} - 1

a_{k} + 1) = d

, akkor

d | a^{k} - 1

és

d | a^{k} + 1

, s így

d | (a^{k} + 1) - (a^{k} - 1) = 2

. Mivel

a^{k} + 1

és

a^{k} - 1

is páros,

2

közös osztójuk, azaz

2 | d

. Tehát

d = 2

.
Az

(a - b) | a^{n} - b^{n})

oszthatósági relációból következik, hogy

4 | a^{k} - 1

, s így

(1)

miatt

4 ∤ (a^{k} + 1)

. Mivel azonban

a_{k} + 1 > 2

(a_{k} + 1)

-nek kettőn kívül kell, hogy legyen más prímosztója is, ami viszont

(1)

miatt

(a_{k} - 1)

-nek nem prímosztója. Ezzel állításunkat beláttuk.

Kiss 352 György (Miskolc, Földes F. Gimn., III. o. t.)