Kezdőlap


Feladat:	2000. évi Nemzetközi Matematika Diákolimpia 22. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Zábrádi Gergely
Füzet:	2000/október, 390 - 391. oldal		PDF \| MathML
Témakör(ök):	Euler-Fermat-tételek, Euklideszi algoritmus, Maradékos osztás, kongruenciák, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 2000/szeptember: 2000. évi Nemzetközi Matematika Diákolimpia 22. feladata

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.

Belátjuk, hogy minden pozitív egész $k$ -hoz található olyan pozitív egész $n$ úgy, hogy $(2^{n} + 1)$ osztható $n$ -nel, és $n$ -nek pontosan $k$ darab prímosztója van.
(Így $k = 2000$ -re is létezik ilyen $n$ .)
$k$ szerinti teljes indukcióval bizonyítjuk az állítást. $k = 1$ -re igaz: $9 ∣ 2^{9} + 1$ .
$k = 2$ -re: $9 \cdot 19 ∣ 2^{9 \cdot 19} + 1$ .
Tegyük fel, hogy $k$ -ra igaz ( $k \geq 2$ ):

\begin{matrix} p_{1}^{2} p_{2} p_{3} ... p_{k} ∣ 2^{p_{1}^{2} p_{2} p_{3} ... p_{k}} + 1, p_{1} = 3 < p_{2} = 19 < p_{3} < ... < p_{k} . \end{matrix}

Segédtétel. Ha

p > 3

prím, akkor

(2^{p} + 1)

-nek van

p

-nél nagyobb prímosztója.
Bizonyítás. Legyen a

q

(2^{p} + 1)

-nek egy

p

-nél nem nagyobb prímosztója. Ekkor

q > 2

és

\begin{matrix} \begin{matrix} 2^{p} \equiv - 1 (mod q) . Négyzetre emelve 2^{2 p} \equiv 1 (mod q) . \end{matrix} \end{matrix}

A kis Fermat-tétel szerint

2^{q - 1} \equiv 1 (mod q)

. Innen az euklideszi algoritmus alkalmazásával kapjuk, hogy

2^{(2 p, q - 1)} \equiv 1 (mod q)

p ∤ q - 1

, mert

q - 1 < p

, így

(2 p, q - 1) = 2

\begin{matrix} \begin{matrix} 2^{2} = 4 & \equiv 1 (mod q), tehát \\ q & = 3. \end{matrix} \end{matrix}

Másrészt

9 ∤ 2^{p} + 1

, mert egyébként

2^{2 p} \equiv 1 (mod 9)

és

2^{6} \equiv 1 (mod 9)

miatt

2^{(6, 2 p)} \equiv 1 (mod 9)

az euklideszi algoritmus miatt, ami

2^{2} \equiv 1 (mod 9)

, és ez ellentmondás.
Ha tehát

(2^{p} + 1)

-nek nincs

p

-nél nagyobb prímosztója, akkor

2^{p} + 1 \leq 3

, ami ellentmondás. Ezzel a segédtételt beláttuk.
Legyen ezután

p_{k + 1}

a segédtétel szerinti prím, tehát

p_{k + 1} > p_{k}

, és

p_{k + 1} ∣ 2^{p_{k}} + 1

\begin{matrix} \begin{matrix} 2^{p_{k}} & \equiv - 1 (mod p_{k + 1}), és így \\ 2^{p_{1}^{2} p_{2} p_{3} ... p_{k} p_{k + 1}} & \equiv {(- 1)}^{p_{1}^{2} p_{2} p_{3} ... p_{k - 1} p_{k + 1}} = - 1 (mod p_{k + 1}), azaz \\ p_{k + 1} & ∣ 2^{p_{1}^{2} p_{2} p_{3} ... p_{k} p_{k + 1}} + 1. \end{matrix} \end{matrix}

Másrészt az indukciós feltevés miatt

p_{1}^{2} p_{2} ... p_{k} ∣ 2^{p_{1}^{2} p_{2} ... p_{k}} + 1

, tehát

\begin{matrix} \begin{matrix} 2^{p_{1}^{2} p_{2} ... p_{k}} & \equiv - 1 (mod p_{1}^{2} p_{2} ... p_{k}) . \\ 2^{p_{1}^{2} p_{2} ... p_{k} p_{k + 1}} & \equiv {(- 1)}^{p_{k + 1}} = - 1 (mod p_{1}^{2} p_{2} ... p_{k}) . \\ p_{1}^{2} p_{2} ... p_{k} p_{k + 1} & ∣ 2^{p_{1}^{2} p_{2} ... p_{k} p_{k + 1}} + 1, \end{matrix} \end{matrix}

mert

p_{1}^{2} \cdot p_{2} \cdot ... \cdot p_{k}

és

p_{k + 1}

relatív prímek. Így

k + 1

-re

n = p_{1}^{2} \cdot p_{2} \cdot ... \cdot p_{k} \cdot p_{k + 1}

megfelelő, amivel az indukciós bizonyítást befejeztük.

Zábrádi Gergely (Győr, Révai M. Gimn., 12. o.t.)