Kezdőlap


Feladat:	B.3651	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Backhausz Ágnes , Bartha Emőke , Bartha Ferenc , Bérczi Kristóf , Bereczki Péter , Birkus Róbert , Bitai Tamás , Boros Balázs , Csajbók Bence , Czank Tamás , Eckert Bernadett , Farkas Balázs , Fehér Borbála , Fehér Gábor , Füredi Mihály , Gehér György , Hubai Tamás , Jankó Zsuzsanna , Juhász Máté Lehel , Király Csaba , Komáromy Dani , Koreck Péter , Korotij Ágnes , Kórus Péter , Kovács Péter , Molnár András , Pálinkás Csaba , Pongrácz András , Ruppert László Gábor , Salát Máté , Simon Balázs , Szabó Botond , Szabó Tamás , Szalai Attila , Tábor Áron , Torma Róbert , Tóthmérész Lilla , Vaskó Richárd
Füzet:	2004/szeptember, 334 - 335. oldal		PDF \| MathML
Témakör(ök):	Legnagyobb közös osztó, Prímszámok, Oszthatósági feladatok, Feladat
Hivatkozás(ok):	Feladatok: 2003/május: B.3651

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.

Megoldás. Ha létezik olyan $p$ prímszám, hogy $p ∤ n$ és $p < \sqrt[]{n}$ , akkor $p^{2} < n$ és $(p^{2}; n) = 1$ , de $p^{2}$ nem prímszám. Ezért ha $n$ osztatlan szám, akkor az összes $\sqrt[]{n}$ -nél kisebb prímmel oszthatónak kell lennie.
Ez a feltétel elegendő is: ha $k < n$ és $k$ összetett, akkor $k$ -nak van $\sqrt[]{k}$ -nál nem nagyobb prímosztója; ez a prímosztó kisebb, mint $\sqrt[]{n}$ , így összetett $k$ -ra $(k; n) > 1$ .
$n = 3$ és $n = 4$ nyilván osztatlan.
Ha $n \geq 5$ , akkor ‐ a prímszámok növekvő sorozatát $p_{1}, p_{2}, ...$ -vel jelölve ‐ a $\sqrt[]{n}$ -nél kisebb prímek legyenek $p_{1}, p_{2}, ..., p_{i}$ . Ha $n$ osztatlan szám, akkor az előbbiek szerint $n = a \cdot p_{1} \cdot p_{2} \cdot ... \cdot p_{i}$ ( $a \in N^{+}$ ) és nyilván $n \leq p_{i + 1}^{2}$ , tehát

\begin{matrix} p_{1} \cdot p_{2} \cdot ... \cdot p_{i} \leq p_{i + 1}^{2} . \end{matrix}

Csebisev tétele szerint

p_{i + 1} < 2 p_{i}

és

p_{i} < 2 p_{i - 1}

, ezért ha

i \geq 3

, akkor

\begin{matrix} p_{1} \cdot p_{2} \cdot ... \cdot p_{i - 2} \leq \frac{p_{i + 1}^{2}}{p_{i} \cdot p_{i - 1}} < \frac{4 p_{i}^{2}}{p_{i} \cdot p_{i - 1}} = \frac{4 p_{i}}{p_{i - 1}} < 8, \end{matrix}

így

2 \cdot 3 \cdot 5 > 8

miatt

i \leq 4

. Mivel

i \geq 1

, négy eset van:

$a)$	$i = 1$ , ekkor $5 \leq n \leq 9$ ( $\sqrt[]{n} \leq 3$ miatt; és mindig csak az új lehetséges $n$ -eket vizsgáljuk) és $2 ∣ n$ szükséges. A megfelelő számok a 6 és a 8.

$b)$	$i = 2$ , ekkor $10 \leq n \leq 25$ és $2 \cdot 3 = 6 ∣ n$ szükséges. A lehetséges számok: 12, 18 és 24.

$c)$	$i = 3$ , ekkor $26 \leq n \leq 49$ és $2 \cdot 3 \cdot 5 = 30 ∣ n$ szükséges, így csak az $n = 30$ felel meg.

$d)$	$i = 4$ , ekkor $50 \leq n \leq 121$ és $2 \cdot 3 \cdot 5 \cdot 7 = 210 ∣ n$ szükséges, ami nyilván lehetetlen.

Az előbbiek szerint a fent felsorolt számok mind osztatlanok, ezért összesen 8 darab 2-nél nagyobb osztatlan szám van: 3, 4, 6, 8, 12, 18, 24, 30.