Kezdőlap


Cím:	Bizonyítsuk be Csebisev tételét 1.
Szerző(k):	Kalmár László
Füzet:	1950/február, 7 - 13. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

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.

Az első évfolyamban feladatsorozatot indítottunk Csebysev tételének bebizonyítására, mely azonban a Lappal együtt abbamaradt. Tekintettel a tétel érdekességére és a bizonyítás egyszerű voltára, most újra elindítjuk. Megoldással közöljük azt a néhány feladatot, melynek megoldása már az első évfolyamban megjelent, a többieket pedig újra ki fogjak tűzni.

Hallottatok-e a világhírű Pafnutij Lvovicsc Csebysev orosz matematikus tételéről? Arról, amelyik azt mondja ki, hogy bármely

n

egész szám és kétszerese;

2 n

között van legalább egy prímszám. (Pl. 2 és 4 között a 3, 3 és 6 között az 5, 4 és 8 között az 5 is, a 7 is, 5 és 10 között a 7, 6 és 12 között a 7 is, a 11 is. Még akkor is igaz a tétel, ha

n = 1

, feltéve, hogy ,,közöttet'' úgy értjük, hogy

2 n

is beleszámítson; ez ugyanis

n = 1

esetén 2, tehát prímszám, de csak akkor.) Aki hallott róla az is azt gondolja bizonyosan, hogy borzasztó nehéz lehet ezt a tételt bebizonyítani. Talán csak akkor lehet reménye az embernek, hogy valaha is megértheti a bizonyítását, ha érettségi után matematikus-hallgatónak iratkozik be az egyetemre, vagy még akkor sem lehet. Pedig illő, hogy legalábbis hazánkban minden, a matematika iránt érdeklődő diák közkincse legyen a Csebysev-tétel, mert Erdős Pál, magyar matematikus, másodéves egyetemi hallgató korában olyan egyszerű bizonyítást adott rá, hogy valamennyien megérthetitek. Nemcsak, hogy megérthetitek, hanem egy kis irányítással magatok is rájöhettek az ő bizonyítására. Kitűzök most és még néhány számban egy-két feladatot; aki ezeket megoldja, végezetül majd be tudja bizonyítani Csebysev tételét. Olyan élménye lesz a bizonyítás, amit egyhamar nem felejt el.

A prímszámokra vonatkozó tételek bizonyításának kulcsa mindig egy egyenlet, esetleg egyenlőtlenség, amelynek egyik oldalán az ismeretlen, egyelőre még titokzatos prímszámok szerepelnek, a másik oldatán pedig a jólismert egész számok. Csebysev ilyen kulcs gyanánt Legendre egy azonosságát használja, amely azt mondja meg, hogyan lehet az első

n

(pozitív) egész szám szorzatát prímtényezőire bontani. Ezt a szorzatot

n!

-sal (mondd:

n

faktoriális) szokás jelölni; tehát

1! = 1

2! = 1 \cdot 2 = 2

3! = 1 \cdot 2 \cdot 3 = 6

4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24

, stb. Arról nevezetes az

n!

, hogy ennyiféleképpen lehet

n

diákot egy sorba állítani. De Csebysev nem emiatt a tulajdonsága miatt gondolt arra, hegy

n!

-sal dolgozzék, hanem azért, mert definíciójában az egész számok egyformán szerepelnek, tehát várható, hogy

n

-nel szabályosan növekszik; de ugyanakkor szorzat, tehát várható, hogy könnyű lesz prímtényezőire felbontani, mégpedig mindenféle, kevés és sok törzstényezőből álló számoknak szorzata, tehát várható, hogy törzstényezős felbontásában is lesz valami szabályosság. Ismerkedjünk meg közelebbről

n!

-sal!
1. Bontsuk fel prímtényezőkre

10!

-t és

20!

-t, a nélkül, hogy előbb elvégeznők a szorzást.
Megoldás:

\begin{matrix} 10! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 = \\ = 2 \cdot 3 \cdot 2^{2} \cdot 5 \cdot (2 \cdot 3) \cdot 7 \cdot 2^{3} \cdot 3^{2} \cdot (2 \cdot 5) = 2^{8} \cdot 3^{4} \cdot 5^{2} \cdot 7, \end{matrix}

\begin{matrix} 20! = 10! \cdot 11 \cdot 12 \cdot 13 \cdot 14 \cdot 15 \cdot 16 \cdot 17 \cdot 18 \cdot 19 \cdot 20 = \\ = (2^{8} \cdot \cdot 3^{4} \cdot 5^{2} \cdot 7) \cdot 11 \cdot (2^{2} \cdot 3) \cdot 13 \cdot (2 \cdot 7) \cdot (3 \cdot 5) \cdot 2^{4} \cdot 17 \cdot (2 \cdot 3^{2}) \cdot 19 \cdot (2^{2} \cdot 5) = \\ = 2^{18} \cdot 3^{8} \cdot 5^{4} \cdot 7^{2} \cdot 11 \cdot 13 \cdot 17 \cdot 19. \end{matrix}

2. Határozzuk meg

100!

prímtényezős felbontásában

2

3

5

és

7

kitevőjét.

Megoldás: 100!-t már nemhogy kiszámítani, de még felírni sem volna türelmünk. Mégis el tudjuk képzelni, hogy ha felírnók az első 100 pozitív egész szám szorzataként: akkor úgy kaphatnók meg prímtényezős felbontását, hogy minden egyes (összetett) tényezője helyébe beírnók annak prímtényezős felbontását és a 2, 3, 5, 7 s a többi prímszámok hatványait összegyűjtve, kitevőiket összeadnók. Így például 2 kitevője azon számok száma 1-tő1 100-ig, amelyekben a 2 az első hatványon szerepel, hozzáadva azon számok számának kétszeresét, amelyekben a 2 a második hatványon szerepel, meg azon számok háromszorosát, melyekben a harmadik hatványon szerepel, stb. A 2 csak azon számoknak a prímtényezős felbontásában szerepel, amelyek párosak; ilyen van 100-ig 50. De ezek közül 25 osztható 4-gyel, tehát csak a többi 25-ben szerepel az első hatványon a 2. A 25 4-gyel osztható szám közül 12 osztható 8-cal is, tehát csak a többi 13-ban szerepel a második hatványon, a 2. A 12 8-cal osztható szám közül 6 osztható 16-tal is, ezek közül 3 32-vel is, ezek közül 1 64-gyel is, úgyhogy 6 olyan szám van, amelyik a harmadik, 3 olyan, amelyik a negyedik, 2 olyan, amelyik az ötödik és 1 olyan (t. i. a 64), amelyik a hatodik hatványon tartalmazza prímtényezős felbontásában a 2-t. E szerint 2 kitevője a 100! prímtényezős felbontásában:

\begin{matrix} 25 + 2 \cdot 13 + 3 \cdot 6 + 4 \cdot 3 + 5 \cdot 2 + 6 \cdot 1 = 97. \end{matrix}

Hasonlóan, minthogy 100-ig 33 3-mal osztható szám van, ezek közül 11 osztható 9-cel (tehát a többi 22 tartalmazza a 3-at az első hatványon), 3 osztható 27-tel (tehát a többi 8 tartalmazza a második hatványon), 1 osztható 81-gyel (tehát a többi 2 tartalmazza a 3-at a harmadik, ez az 1 pedig a negyedik hatványon), ezért 3 kitevője 100! felbontásában

\begin{matrix} 22 + 2 \cdot 8 + 3 \cdot 2 + 4 \cdot 1 = 48. \end{matrix}

Minthogy 100-ig 20 5-tel osztható és ezek között 4 25-tel osztható szám van, tehát 16 tartalmazza az 5-öt az első, 4 pedig a második hatványon, továbbá, minthogy 100-ig 14 7-tel és ezek között 2 49-cel osztható szám van, tehát 12 tartalmazza a 7-et az első, 2 pedig a második hatványon, ezért 5 kitevője

16 + 2 \cdot 4 = 24

, 7-é pedig

12 + 2 \cdot 2 = 16

a 100! prímtényezős felbontásában. E szerint ez a felbontás így kezdődik:

\begin{matrix} 100! = 2^{97} \cdot 3^{48} \cdot 5^{24} \cdot 7^{16} ... \end{matrix}

3. Hány

0

-ra végződik

100!

? Hát

1000!

Megoldás: Minden szám annyi

0

-ra végződik, ahányadik hatványával még osztható a

10

-nek.

10^{k}

prímtényezős felbontása

2^{k} \cdot 5^{k}

, tehát egy szám akkor és csakis akkor osztható vele, ha prímtényezős felbontásában

2

is,

5

is legalább a

k

-adik halványon szerepel. A legnagyobb ilyen

k

a kérdéses szám prímtényezős felbontásában a

2

és az

5

kitevője közül a kisebbik (ha véletlenül egyenlők, akkor közös értékük). Mivel

100!

felbontásában

2

kitevője

97

5

-é pedig

24

, ezért

100!

24

0

-ra végződik.

1000!

prímtényezős felbontásában az

5

kitevője

249

, mert

1000

-ig

200

5

-tel,

40

25

-tel,

8

125

-tel és

1

625

-tel osztható szám van, tehát

160

tartalmazza az 5-öt az első,

32

a második,

7

a harmadik és

1

a negyedik hatványon és

160 + 2 \cdot 32 + 3 \cdot 7 + 4 \cdot 1 = 249

. A

2

kitevője nagyobb ennél, hiszen

1000

-ig

500

páros szám van s ezek mindegyike legalább első hatványon tartalmazza a

2

-t. Ezért

1000!

249

0

-ra végződik.

4. Határozzuk meg

(2^{n})!

és

(2^{n} - 1)!

prímtényezős felbontásában a

2

kitevőjét.

Megoldás: Az

1,2,3, ..., 2^{n}

számok között

2^{n - 1}

páros van, ezek közül

2^{n - 2}

4-gyel osztható,

2^{n - 3}

8-cal,

2^{n - 4}

16-tal,

...

végül egyetlen egy

2^{n}

-nel osztható. Így közülük

2^{n - 1} - 2^{n - 2}

tartalmazza a 2-t az első,

2^{n - 2} - 2^{n - 3}

a második,

2^{n - 3} - 2^{n - 4}

a harmadik,

...

, végül 1 az

n

-edik hatványon. E szerint a 2 kitevője a

(2^{n}

)! prímtényezős felbontásában

\begin{matrix} 2^{n - 1} - & 2^{n - 2} + 2 (2^{n - 2} - 2^{n - 3}) + 3 (2^{n - 3} - 2^{n - 4}) + ... + n \cdot 1 = \\ = & 2^{n - 1} - 2^{n - 2} + 2 \cdot 2^{n - 2} - 2 \cdot 2^{n - 3} + 3 \cdot 2^{n - 3} - ... - (n - 1) + n = \\ = 2^{n - 1} + 2^{n - 2} + 2^{n - 3} + ... + 1 = 2^{n} - 1. \end{matrix}

Minthogy

(2^{n} - 1)! = (2^{n})! : 2^{n}

, azért prímtényezős felbontásában a 2 kitevője

n

-nel kevesebb, mint

(2^{n})!

-éban, vagyis

2^{n} - n - 1

5. Fejezzük ki az algebra nyelvén, hogyan határozhatjuk meg

n!

prímtényezős felbontásában a p prímszám kitevőjét.

Megoldás: Az

1,2,3, ..., n

számok között annyi

p

-vel osztható van, ahány egész-szer megvan a

p

n

-ben, azaz

[\frac{n}{p}]

¹, annyi

p^{2}

-tel osztható, ahány egész-szer a

p^{2}

megvan az

n

-ben, azaz

[\frac{n}{p^{2}}]

, hasonlóan

p^{3}

-nel

[\frac{n}{p^{3}}]

számú osztható, s. í. t.: végül, ha

p^{k} ≦ n < p^{k + 1}

, akkor

p^{k}

-nal

[\frac{n}{p^{k}}]

számú osztható,

p

magasabb hatványával azonban egy sem. E szerint az

1,2,3, ..., n

számok, között

[\frac{n}{p}] - [\frac{n}{p^{2}}]

számúnak a prímtényezős felbontása tartalmazza a

p

-t az első hatványon,

[\frac{n}{p^{2}}] - [\frac{n}{p^{3}}]

számúé a másodikon,

[\frac{n}{p^{3}}] - [\frac{n}{p^{4}}]

számúé a harmadikon, s. í. t.,

[\frac{n}{p^{k - 1}}] - [\frac{n}{p^{k}}]

számúé, a

(k - 1)

-ediken és

[\frac{n}{p^{k}}]

számúé a

k

-adikon. Így az

n!

prímtényezős felbontásában a

p

kitevője

\begin{matrix} [\frac{n}{p}] - [\frac{n}{p^{2}}] + 2 ([\binom{n}{p^{2}}] - [\frac{n}{p^{3}}]) + 3 ([\frac{n}{p^{3}}] - [\frac{n}{p^{4}}]) + ... + \\ + (k - 1) ([\frac{n}{p^{k - 1}}] - [\frac{n}{p^{k}}]) + k [\frac{n}{p^{k}}] = [\binom{n}{p}] - [\frac{n}{p^{2}}] + 2 [\frac{n}{p^{2}}] - 2 [\binom{n}{p^{3}}] + \\ + 3 [\frac{n}{p^{3}}] - ... - (k - 1) [\binom{n}{p^{k}}] + k [\frac{n}{p^{k}}] = [\binom{n}{p}] + [\frac{n}{p^{2}}] + [\frac{n}{p^{3}}] + ... + \\ + [\frac{n}{p^{k}}] = [\frac{n}{p}] + [\frac{n}{p^{2}}] + [\frac{n}{p^{3}}] + ..., \end{matrix}

ahol az összeg az

[\frac{n}{p^{k}}]

tagon túl is folytatható, hiszen a többi tagja úgyis 0. Az eredményt utólag még így is igazolhatjuk:

[\frac{n}{p}]

jelenti az

1,2,3, ...

n

számok közül a

p

-vel oszthatók.

[\frac{n}{p^{2}}]

p^{2}

-tel,

[\frac{n}{p^{3}}]

p^{3}

-nel oszthatók számát, s. í. t. Ha tehát egy szám

p

-vel osztható, de

p^{2}

-tel nem, akkor az

[\frac{n}{p}] + [\frac{n}{p^{2}}] + [\frac{n}{p^{3}}] + ...

összegben csak egyszer vettük számba, t.i. az első tagban; ha

p^{2}

-tel osztható, de,

p^{3}

-nel már nem, akkor kétszer vettük számba, t. i. az első és második tagban; ha

p^{3}

-nel is osztható, de

p^{4}

-tel nem, akkor háromszor vettük számba, t. i. az első, második és harmadik tagban, és így tovább; minden számot annyiszor vettünk számba, amennyi a prímtényezős felbontásában a

p

kitevője, így az összeg e kitevők összege, vagyis

n!

felbontásában

p

hatványkitevője.

Megjegyzések: A

p^{k} ≦ n < p^{k + 1}

egyenlőtlenség

k ≦ \frac{log n}{log p} =^{p} log n < k + 1

alakban írható; tehát az ennek eleget tevő egész szám

k = [\frac{log n}{log p}] = [^{p} log n]

.
Numerikusan adott

n

és

p

esetén célszerűbb a számítást így berendezni legyen

[\frac{n}{p}] = n_{1}

[\binom{n_{1}}{p}] = n_{2}

[\frac{n_{2}}{p}] = n_{3}, ...

; akkor

n!

prímtényezős felbontásában a

p

prímszám kitevője:

n_{1} + n_{2} + n_{3} + ... + n_{k}

.
Ugyanis

[\binom{n}{p^{2}}] = [\frac{\frac{n}{p}}{p}] = [\frac{[\frac{n}{p}]}{p}] = [\frac{n_{1}}{p}] = n_{2}

[\frac{n}{p^{3}}] = [\frac{\frac{n}{p^{2}}}{p}] = [\frac{[\frac{n}{p^{2}}]}{p}] = [\frac{n_{2}}{p}] = n_{3} ...

, mert általában

[\frac{x}{p}] = [\frac{[x]}{p}]

Az 5. feladat megoldásával a Legendre-féle

\begin{matrix} n! = 2 \binom{[\frac{n}{2}] + [\frac{n}{4}] + [\frac{n}{8}] + ...}{} \cdot 3 \binom{[\frac{n}{3}] + [\frac{n}{9}] + [\frac{n}{27}] + ...}{} \cdot 5 \binom{[\frac{n}{5}] + [\frac{n}{25}] + [\frac{n}{125}] + ...}{} \end{matrix}

azonosságban (ahol prímszámok persze

n

-ig mennek) olyan kulcshoz jutottunk, amely alkalmas egyes, a prímszámokra vonatkozó kérdések megoldására. De vajon hogyan forgassuk ezt a kulcsot, hogy a Csebysev- tétel nyitját megtaláljuk? Mit kezdjünk

n!

-sal, hogy éppen az

n

és

2 n

közötti prímszámokról tudósítson bennünket?
Csebysev eredeti bizonyítása egy nagyon bonyolult, az

n!

segítségével képezett kifejezés vizsgálatán alapul. Erdős (és már előtte az indus Ramanujan is) a Csebysev-féle kifejezés helyett a sokkal egyszerűbb

\begin{matrix} \frac{(2 n)!}{{(n!)}^{2}} = \frac{1 \cdot 2 ... n (n + 1) (n + 2) ... 2 n}{1 \cdot 2 \cdot 3 ... n \cdot 1 \cdot 2 \cdot 3 ... n} = \frac{(n + 1) (n + 2) ... 2 n}{1 \cdot 2 \cdot 3 ... n} \end{matrix}

kifejezést használja. Ezt a kifejezést

(\binom{2 n}{n})

-nel (mondd:

2 n

alatt

n)

szokás jelölni: általában

(\binom{m}{n})

-nel az

\frac{m!}{n! (m - n)!}

kifejezést jelöljük. Ez arról nevezetes, hogy egy

m

tagú osztályból ennyiféleképpen lehet kijelölni egy

n

tagú küldöttséget, így

(\binom{m}{n})

csak látszólag tört, valójában mindig egész szám az értéke. De Erdős sem azért gondolt arra, bogy

(\binom{2 n}{n})

segítségével fogjon hozzá a Csebysev-tétel bizonyításához, mert ha egy

2 n

tagú osztálynak pontosan a felét visszük kirándulni, akkor éppen

(\binom{2 n}{n})

féleképpen lehet kijelölni, hogy kik jussanak a kirándulók közé. Hanem azért, mert

(\binom{2 n}{n}) = \frac{(n + 1) (n + 2) ... 2 n}{1 \cdot 2 \cdot 3 ... n}

meg kell, hogy érezze, hogy

n

és

2 n

között vannak prímszámok Hiszen ezekkel a prímszámokkal minddel osztható, mert a számlálója osztható velük, de a nevezője nem; az

n

-ig terjedő prímszámok azonban a nevezőjében is előfordulnak, így ezek közül sok kiesik egyszerűsítés közben. Várható hát, hogy ha feltételezzük, hogy

n

és

2 n

között nincs prímszám, akkor

(\binom{2 n}{n})

prímtényezős felbontásából sokkal kisebb értéket kapunk.

(\binom{2 n}{n})

számára, mint amekkora valójaban. Ismerkedjünk meg hát közelebbről a

(\binom{2 n}{n})

-nel!

6. Mutassuk meg, hogy ha

a

pozitív szám, akkor

[2 a] - 2 [a]

értéke vagy

0

, vagy

1

.
7. Mutassuk meg, hogy

(\binom{2 n}{n})

mindig egész azám.
8. Mutassuk meg, hogy

(\binom{2 n}{n})

tözzstényezős felbontásában egyik prímszám hatványa sem lehet nagyobb

2 n

-nél. (A hatványról van szó, nem a hatványkitevőről!)
9. Mutassuk meg, hogy

(\binom{2 n}{n})

prímtényezős felbontásában a

\sqrt[]{2 n}

-nél nagyobb prímszámok legfeljebb első hatványon szerepelnek (azaz vagy nem szerepelnek, vagy csak első hatványon).
10. Mutassuk meg, hogy

(\binom{2 n}{n})

nem osztható a

\frac{2}{3} n

és

n

közötti prímszámokkal (

n

-et beleértve, ha prímszám;

\frac{2}{3} n

-et akkor sem értve bele, ha

n

osztható 3-mal és

\frac{2}{3} n

prímszám).

¹Olv. ,

, \frac{n}{p}

egész része.'' Ez a legnagyobb olyan egész számot jelenti, mely még nem nagyobb

\frac{n}{p}

-nél. Lásd erre vonatkozólag a 85‐89. feladatokat, I. évf. 49‐51. és 71‐72. lap,

¹Lásd 85. feladat, I. évi, 49. 1.