Kezdőlap


Feladat:	2008. évi Nemzetközi Matematika Diákolimpia 13. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Lovász László Miklós
Füzet:	2008/október, 390. oldal		PDF \| MathML
Témakör(ök):	Osztók száma, Prímszámok száma, Magasabb fokú kongruenciák, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 2008/szeptember: 2008. évi Nemzetközi Matematika Diákolimpia 13. 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.

Lovász László Miklós megoldása. A bizonyítandó állítás következik az alábbi állításból:
Végtelen sok $p$ prím van, amihez létezik olyan $n$ , hogy

\begin{matrix} 2 n + \sqrt[]{2 n} < p, és p ∣ n^{2} + 1. \end{matrix}

Ha ugyanis csak véges sok megfelelő

n

lenne, akkor, mivel

(n^{2} + 1)

-nek véges sok különböző prímosztója van, csak véges sok megfelelő

p

lenne.
Ismert, hogy végtelen sok

p = 4 k + 1

alakú prím van, és hogy ezekre létezik olyan

n

, amire

p ∣ n^{2} + 1

. Legyen

p > 20

egy

4 k + 1

alakú prím. Nyilván létezik ekkor ilyen

n

(0, p)

intervallumban¹. Ha

n > \frac{p}{2}

, akkor

p - n < \frac{p}{2}

, így

\begin{matrix} {(p - n)}^{2} + 1 \equiv n^{2} + 1 \equiv 0 (p) . \end{matrix}

Tehát van megfelelő pozitív egész

n

, amire

n < \frac{p}{2}

, vagyis

2 n < p

.
Legyen

n = \frac{p - k}{2}

. Mivel

p

páratlan,

k > 0

\begin{matrix} {(\frac{p - k}{2})}^{2} + 1 & \equiv 0 (p), \\ {(p - k)}^{2} + 4 & \equiv 0 (p), \\ k^{2} + 4 & \equiv 0 (p) . \end{matrix}

k^{2} > 0, 4 > 0 \Rightarrow k^{2} + 4 > 0

, tehát

k^{2} + 4 \geq p

, amiből

k \geq \sqrt[]{p - 4}

. Ekkor tehát

\begin{matrix} n = \frac{p - k}{2} \leq \frac{p - \sqrt[]{p - 4}}{2}, \end{matrix}

vagyis

\begin{matrix} 2 n \leq p - \sqrt[]{p - 4}, 2 n + \sqrt[]{p - 4} \leq p, p - 4 \geq 2 n + \sqrt[]{p - 4} - 4. \end{matrix}

Mivel

p > 20

\sqrt[]{p - 4} > 4

, amiből

p - 4 > 2 n \Rightarrow \sqrt[]{p - 4} > \sqrt[]{2 n}

. Azt kaptuk tehát, hogy

\begin{matrix} p \geq \sqrt[]{p - 4} + 2 n > \sqrt[]{2 n} + 2 n . \end{matrix}

Tehát ha

p

elég nagy, létezik hozzá megfelelő

n

, így mivel végtelen sok

4 k + 1

alakú prím van, végtelen sok megfelelő

p

van, és ezért végtelen sok megfelelő

n

van.

n

p

szerinti osztási maradéka megfelelő lesz.