Kezdőlap


Feladat:	1981. évi Kürschák matematikaverseny 3. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Bali János , Dósa György , Gellér János , Király Zoltán , Magyar Ákos , Nacsa János , Simonyi Gábor , Szabó Endre , Szenes András , Tardos Gábor
Füzet:	1982/február, 59 - 61. oldal		PDF \| MathML
Témakör(ök):	Maradékos osztás, Osztók összege, Tökéletes számok, Prímszámok, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):	Feladatok: 1982/február: 1981. évi Kürschák matematikaverseny 3. 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.

Megoldás. Azon, hogy egy $n$ egész számot egy pozitív egész számmal maradékosan osztunk, egy

\begin{matrix} n = c q + r \end{matrix}

alakú előállítását értjük, ahol

q

(a hányados) egész szám,

r

pedig (a maradék) kisebb, mint

c

és nem negatív. Ilyen hányados és maradék mindig van és mindig csak egy.
Vizsgáljuk

n

és

n - 1

maradékát ugyanazzal a

k

számmal történő osztásnál. Ha a fenti osztásnál az

r

maradék nem

0

, akkor

\begin{matrix} n - 1 = c q + (r - 1), \end{matrix}

és mivel a maradék egyértelműen meg van határozva, így minden ilyen esetben

1

adódik hozzá az

r (n) - r (n - 1)

különbséghez. Ha viszont

r = 0

, vagyis

c

osztója

n

-nek, akkor

\begin{matrix} n - 1 = c (q - 1) + c - 1, \end{matrix}

tehát az

n

osztói az osztónál

1

-gyel kevesebbel csökkentik a fenti különbséget. Jegyezzük meg, hogy magával

n

-nel

n

-et még el kell osztanunk a feladat szövege szerint,

n - 1

-et azonban már nem. Ezt az osztót azonban figyelmen kívül is hagyhatjuk, mert az elvégzendő osztás maradéka

0

. Jelöljük az

n

szám

n

-nél kisebb (pozitív) osztóinak összegét

s (n)

-nel, számukat

d (n)

-nel, akkor megállapításaink szerint

\begin{matrix} r (n) - r (n - 1) = n - d (n) - 1 - (s (n) - d (n)) = n - 1 - s (n) . \end{matrix}

A feladat eszerint annak a belátását kívánja, hogy végtelen sok olyan

k

szám van, amelyikre

\begin{matrix} s (k) = k - 1. \end{matrix}

Az első néhány szám kipróbálása azt mutatja, hogy a

2

hatványai ilyenek, és valóban könnyű belátni, hogy

k = 2^{l}

minden pozitív egész

l

kitevőre kielégíti az egyenletet. Valóban,

2^{l}

nála kisebb osztói

1, 2, 2^{2}, ..., 2^{l - 1}

. Ezek mértani sorozatot alkotnak, amelyben az elemek összege ‐ mivel az elemek száma

l

, a hányados pedig

2

‐

\begin{matrix} \frac{[2^{l} - 1]}{2 - 1} = 2^{l} - 1 = k - 1. \end{matrix}

Ezzel állításunkat igazoltuk.

Megjegyzések. 1. A feladat igen hasonló a tökéletes számok problémájához. A fenti jelöléseket használva akkor neveztek az ókori görögök tökéletesnek egy számot, ha

\begin{matrix} s (k) = k . \end{matrix}

Már Euklidész elemeiben szerepel, hogy a

2^{s - 1} (2^{s} - 1)

alakú számok tökéletesek, ha a második tényező törzsszám. Mintegy 2000 évvel később Euler bebizonyította, hogy a páros számok közül csak az Euklidész által említett számok tökéletesek.
Páratlan tökéletes szám nem ismeretes. Számos olyan tulajdonságot találtak, amivel minden páratlan tökéletes számnak ‐ ha van ilyen ‐ rendelkeznie kell. A legkisebb szám is, amelyiknek mindez a tulajdonsága megvan, elképzelhetetlenül nagy kell hogy legyen, azt azonban nem sikerült eddig bebizonyítani, hogy nincs páratlan tökéletes szám.
A

2^{s} - 1

alakú szám könnyen láthatóan csak akkor lehet prím, ha

s

is prímszám, de távolról sem igaz, hogy minden

s

prímszámra prímszámot adna a fenti formula. Pl.

\begin{matrix} 2^{11} - 1 = 2047 = 23 \cdot 89 . \end{matrix}

Eddig a nagyteljesítményű számítógépek segítségével is mindössze

27

ilyen alakú prímet találtak, így ugyanennyi az ismert tökéletes számok száma is. Nem tudjuk, hogy van-e több, még azt sem sikerült azonban eldönteni, hogy van-e végtelen sok, vagy pedig véges a páros tökéletes számok száma.
2. Az

\begin{matrix} s (k) = k - 1 \end{matrix}

egyenletről azt láttuk be, hogy

2

minden hatványa megoldása, tehát végtelen sok megoldása van. Nem tudjuk azonban, hogy van-e más megoldása is, mint a

2

hatványai. Annyit nem nehéz belátni, hogy egy

2^{l} m

alakú szám, ahol

m

páratlan (

l

lehet

0

is) csak akkor elégítheti ki az egyenletet, ha

m

egy egész szám négyzete.
3. A bizonyítás során nyert

\begin{matrix} r (n) - r (n - 1) = n - 1 - s (n) \end{matrix}

formulát

n = 2, 3, ..., k

-ra összeadva és felhasználva, hogy

r (1) = 0

, azt kapjuk, hogy

\begin{matrix} r (k) = (r (k) - r (k - 1)) + (r (k - 1) - r (k - 2)) + ... + (r (2) - r (1)) + r (1) = \\ = (k - 1) + (k - 2) + ... + 1 - s (k) - s (k - 1) - ... - s (2) = \frac{k (k - 1)}{2} - S (k), \end{matrix}

ahol

S (k)

-val a következő összeget jelöltük:

\begin{matrix} S (k) = s (k) + s (k - 1) + ... + s (2) . \end{matrix}

[Az összeghez

s (1)

-et is hozzáírhatjuk, ha tetszik, mert annak értéke

0

.]
Célszerűbb

s (k)

helyett az összes osztók

σ (k)

összegét használni. A kettő kapcsolata

\begin{matrix} σ (k) = s (k) + k . \end{matrix}

σ (k) + σ (k - 1) + ... + σ (1)

összeget

\sum (k)

-val jelölve

\begin{matrix} S (k) = σ (k) - k + σ (k - 1) - (k - 1) + ... + σ (1) - 1 = \sum (k) - \frac{k (k + 1)}{2} . \end{matrix}

Ezt

r (k)

képletébe beírva az egyszerűbb

\begin{matrix} r (k) = k^{2} - \sum (k) \end{matrix}

formulát kapjuk.
Néhány versenyző felhasználta, hogy

n

-et

c

-vel maradékosan osztva a hányados

[\frac{n}{c}]

, azaz

n = c \cdot [\frac{n}{c}] + r

, ahol

0 \leq r < c

,
továbbá az irodalomra hivatkozva¹ a

\begin{matrix} \sum (n) = [\frac{n}{1}] + 2 [\frac{n}{2}] + ... + n [\frac{n}{n}] \end{matrix}

formulát. Ezekből eljutott az

r (n)

-re éppen nyert képlethez és azt vette segítségül a feladat megoldásához (nem mindig sikerrel).

¹ D. O. Skljarszkij‐N. N. Csencov‐J. M. Jaglom: Válogatott feladatok és tételek az elemi matematika köréből 1. Aritmetika és algebra 172. o.