Kezdőlap


Feladat:	N.137	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Frenkel Péter , Gerbicz Róbert , Lukács László , Pap Gyula
Füzet:	1998/január, 33 - 34. oldal		PDF \| MathML
Témakör(ök):	Konstruktív megoldási módszer, Legkisebb közös többszörös, Oszthatósági feladatok, Ellenpélda, mint megoldási módszer a matematikában, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1997/április: N.137

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.

a) Legyen $A$ az 1, 2, $...$ , $k$ számok legkisebb közös többszöröse, és legyen $a_{i} = i \cdot A$ minden $i$ -re. Ekkor $i \neq j$ esetén $a_{i} - a_{j} = (i - j) A ∣ A^{2} ∣ a_{i}^{1997}$ , tehát ez a konstrukció megfelelő.

b) Az állítás $k = 1$ esetén az $a_{1} = 1$ ellenpélda miatt nem igaz, de $k \geq 2$ esetén igaz, ezt bizonyítjuk be. Legyen először $k \geq 4$ , és tekintsünk egy tetszőleges, $\frac{k}{2}$ -nél nem nagyobb $p$ prímet. Két különböző $a_{i}$ és $a_{j}$ nem adhatja ugyanazt a $0$ -tól különböző maradékot $p$ -vel osztva, mert $a_{i} \equiv a_{j} (mod p)$ esetén $p ∣ a_{i} - a_{j} ∣ a_{i}^{1997}$ . Ebből következik, hogy a $p$ -vel nem osztható $a_{i}$ -k száma legfeljebb $p - 1$ , és a $p$ -vel osztható $a_{i}$ -k száma legalább $k - p + 1 \geq [\frac{k + 1}{2}]$ .

Tekintsük a $B = a_{1} a_{2} ... a_{k}$ szorzatot. Az előbbiek szerint ha $p < \frac{k}{2}$ prím, akkor $B$ osztható $p^{[\frac{(k + 1)}{2}]}$ -vel, ezért

\begin{matrix} a_{k} > B^{\frac{1}{k}} \geq {(\prod_{p < \frac{k}{2}}^{} p^{[\frac{(k + 1)}{2}]})}^{\frac{1}{k}} \geq {(\prod_{p < \frac{k}{2}}^{} p)}^{\frac{1}{2}} . \end{matrix}

De ismeretes (lásd megjegyzésünket), hogy létezik olyan pozitív

c_{0}

konstans, amelyre tetszőleges

x \geq 2

esetén

\prod_{p \leq x}^{} p > 2^{c_{0} x}

, ezért

a_{k} > 2^{\frac{1}{4} c_{0} k}

.
Ha

k = 2

vagy

k = 3

, akkor

a_{k} \geq 2 > 2^{\frac{1}{4} k}

. A

c

számnak ezért választhatjuk

\frac{1}{4} c_{0}

és

\frac{1}{4}

közül a kisebbet.

Megjegyzés. A prímszámtétel egyik formája azt mondja ki, hogy

\begin{matrix} {lim}_{x \to \infty}^{} \frac{{\sum_{}^{}}_{p \leq x}^{} log p}{x} = 1, \end{matrix}

vagy másképpen, tetszőleges

ε > 0

-ra, ha

x

elég nagy,

\begin{matrix} e^{(1 - ε) x} < \prod_{p \leq x}^{} p < e^{(1 + ε) x} . \end{matrix}

Ennél valamivel gyengébb alsó és felső becslést be lehet bizonyítani viszonylag egyszerű, elemi úton. Szalay Mihály: Számelmélet (Tankönyvkiadó, 1991.) c. könyvének 143‐146. oldalain megtalálható többek között annak bizonyítása, hogy

n \geq 5

esetén

\begin{matrix} \prod_{n < p \leq 2 n}^{} p > \frac{2^{2 n}}{{(2 n)}^{\sqrt[]{n}}} \cdot 4^{- \frac{2 n}{3}} = \frac{2^{\frac{2}{3} 2 n}}{{(2 n)}^{\sqrt[]{2 n}}} . \end{matrix}

Ebből következik, hogy

\prod_{p \leq x}^{} p > 2^{(\frac{2}{3} - ε) x}

, ha

x

elég nagy.
Az idézett könyv 140. oldalán megtalálható 3.2. tétel szerint

\prod_{p \leq x}^{} p < 4^{x}

. Ebből nem nehéz bebizonyítani, hogy az első megoldásban szereplő

A

szám nem nagyobb, mint

4^{(1 + ε) k}

, és így a b) állítás a konstanstól eltekintve éles.