Kezdőlap


Feladat:	Pontversenyen kívüli P.89	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Bacsó G. , Bara T. , Ferró J. , Katona E. , Reviczky János , Szendrei Ágnes
Füzet:	1971/november, 152 - 153. oldal		PDF \| MathML
Témakör(ök):	Algoritmikus eljárások, Prímszámok, Természetes számok, Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1971/január: Pontversenyen kívüli P.89

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.

Jelöljük $D_{n}$ -nel az $n$ -nél nem nagyobb természetes számok közül azoknak a halmazát, amelyeknek van $1$ -nél nagyobb közös osztójuk $n$ -nel, és jelöljük $d (n)$ -nel a $D_{n}$ halmaz elemeinek a számát. Feladatunk állítása azt jelenti, hogy nincs olyan $n$ természetes szám, melyre $d (n)$ értéke $10$ volna. Ezt fogjuk bizonyítani, és rögtön feltesszük, hogy $n > 1$ , hiszen $d (1) = 0$ .
Ha $n$ prímszám, vagy egy prímszám hatványa, azaz $n = p^{k}$ , ahol $p$ prímszám, és $k \geq 1$ , akkor

\begin{matrix} D_{n} = {p, 2 p, 3 p, ..., p^{k - 1} \cdot p}, \end{matrix}

tehát

d (n) = p^{k - 1}

, ami ugyancsak prímszámhatvány ‐ vagy

1

. Ilyen

n

-ekre tehát

d (n)

értéke nem lehet

10

.
Minden más természetes szám felbontható két egymáshoz prím,

1

-nél nagyobb természetes szám szorzatára. Legyen

n = a \cdot b

n

-nek ilyen ‐ de különben tetszőleges ‐ felbontása. Ekkor a

\begin{matrix} D_{n} (a) = a, 2 a, ..., b a, D_{n} (b) = b, 2 b, ..., a b \end{matrix}

halmazoknak egyetlen közös elemük az

n = a b

szám, hiszen ha

j a = l b

, ahol

1 \leq j \leq b

1 \leq l \leq a

, akkor

a

minden osztója

l

-nek is osztója, és

b

minden osztója

j

-nek is osztója, vagyis csak

j = b

és

l = a

lehet. A

D_{n} (a)

D_{n} (b)

halmazok egyesítésében tehát

(a + b - 1)

szám van, és ezek mind elemei

D_{n}

-nek is. Emiatt

\begin{matrix} d (n) \geq a + b - 1. \end{matrix}

Itt akkor és csakis akkor lehet az egyenlőség jele érvényes, ha

a

is és

b

is, prímszám, hiszen

a

-nak és

b

-nek

1

-nél nagyobb, de

a

-nál, illetve

b

-nél kisebb osztói elemei

D_{n}

-nek, de nincsenek benne a

D_{n} (a)

D_{n} (b)

halmazokban. Ha viszont

a

is,

b

is prímszámok, akkor

D_{n}

minden eleme vagy

a

-val, vagy

b

-vel osztható, tehát vagy

D_{n} (a)

-nak, vagy

D_{n} (b)

-nek eleme.
Ha itt

a

és

b

prímszámok, akkor ezek szerint

d (n) = 10

csak akkor lehetne, ha

a + b = 11

volna, viszont a

11

-et nem lehet két prímszám összegeként előállítani.
Ezek szerint már csak azokat az

n

számokat kell vizsgálni, amelyek

n = a \cdot b

alakúak, ahol

a

és

b

relatív prímek,

1

-nél nagyobbak, nem mind a kettő prímszám, és

a + b < 11

. Csak két ilyen szám van: a

3 \cdot 4

és a

4 \cdot 5

, ezekre

\begin{matrix} D_{12} = {2, 3, 4, 6, 8, 9, 10, 12}, \\ D_{20} = {2, 4, 5, 6, 8, 10, 12, 14, 15, 16, 18, 20}, \end{matrix}

tehát

d (12) = 8

d (20) = 12

, így

d (n)

értéke ezekre sem

10

. Feladatunk állítását ezzel bebizonyítottuk.

Reviczky János (Budapest, I. István Gimn.)