Szocialista Nevelés, 1971. szeptember-1972. június (17. évfolyam, 1-10. szám)

1972-05-01 / 9. szám - László Béla - László Béláné: Matematikai logika és számtanelmélet a szakkörökben (folyt)

Matematikai logika és számelmélet a szakkörökben

(Folytatás)

LÁSZLÓ BÉLA — LÁSZLÓ BÉLÁNÉ

Vegyük most szemügyre a prímszámokat. Tudjuk, hogy végtelen sok prímszám van, de nem ismerünk olyan képletet, amely minden esetben prímszámot adna. Nyilvánvaló, hogy a 3 = 23 + 1; 5 = 22 + 1; 17 = 24 + 1; 257 = 28 + 1; ___

számok törzsszámok és mind írhatók 2n + 1 (16) alakban, ahol n természetes szám. Ez azonban nem minden természetes szám esetén ad törzsszámot. Ha történetesen n egyenlő 3, akkor 23 + 1 = 9 már összetett szám.

A felsorolt példákból arra lehetne következtetni, hogy ha n egyenlő 2 nem negatív egész kitevőjű hatványával, akkor a (16) mindig prím- számot szolgáltat. Azonban ez a sejtésünk is téves, hiszen 225 + 1 = 4 294 967 297 = 641.6 700 417 szám már nem prímszám. Ha tehát az, hogy n egyenlő 2 nem negatív egész kitevőjű hatványával az előzőek alapján nem elégséges feltétel ahhoz, hogy (16) prímszám lehessen, kérdezhetjük, nem teljesíti-e ezen feltétel legalább a szükségesség iránt támasztott követelményt. E kérdésre a következő általánosabb tétel bebizonyításával adjuk meg az igenlő választ.

VI. tétel: Legyen n pozitív és a egynél nagyobb természetes szám. Ha an + 1 (17)

prímszám, akkor a páros szám és n egyenlő 2 nem negatív egész hatványával.

Bizonyítás: „A (17) alakú szám prímszám“ ítéletet jelöljük P-vel, az „a páros szám“ ítéletet Q-val és az „n egyenlő 2 valamely nem negatív egész kitevőjű hatványával“ ítéletet pedig R-el.

Ennélfogva tételünk

P-*(Q A R)

alakú, amelynek igazolásához a II. tétel alapján be kell bizonyítani a IQ^IP; 1R_»P

tételeket.

Ha tehát a nem páros szám, akkor a (17) mint két páratlan szám ösz- szege páros szám, a nagyobb 1 miatt az an + 1 ^ 4

páros szám nem lehet prímszám, vagyis nem R-ből következik nem P, amit bizonyítani kellett.

Második esetként tegyük fel, hogy nem Q igaz és bizonyítjuk újból, hogy nem P is igaz. A nem Q igazsága azt jelenti, hogy n-nek van egynél nagyobb páratlan osztója, vagyis n = m . v

ahol a nagyobb 1 és páratlan. Ilyen feltételek alapján an + l = am v + i = = (am + 1) . (am • (V-D — am • (v~2) +

+

........— am + 1).

Ennélfogva (17) osztható az am + 1

számmal, amely nagyobb 1-nél és kisebb mint (17), hiszen m kisebb n-nél. (17) tehát sem prímszám, ami nem P igazát jelenti.

Ezzel tételünket teljesen bebizonyítottuk.

Az a egyenlő 2 esetben (17) a tétel előtt közölt számokra utal.

Hasonlóan bizonyítható a következő tétel:

VII. tétel: Legyen a pozitív, n 1-nél nagyobb természetes szám. Ha an — 1 prímszám, akkor a egyenlő 2 és n prímszám.

Az F(r) = 22r + 1

alakú számokat, ahol az r egyenlő

0, 1, 2,

........, Fermat — féle számoknak nevezzük. Az ilyen alakú számok között eddig öt prímet, ún. Fermat- féle prímet ismerünk. Ezek a következők:

F(0) = 3; F(1) = 5; F(2) = 17;

F(3) = 257; F(4) = 65 537

277