Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

2. Prímszámok

2. Prímszámok

Meg lehet mutatni, hogy az F n polinomok irreducibilisek. Ezt azonban nem bizonyítjuk, és a bemutatandó alkalmazáshoz nem is lesz rá szükségünk. Az alkalmazás speciális alakú prímszámok létezésével kapcsolatos.

Könnyű belátni, hogy végtelen sok 3 k - 1 alakú prímszám van. Valóban, ha egy tetszőleges N ? 3 számnál nagyobb 3 k - 1 alakú prímet keresünk, akkor tekintsük N ! - 1 prímosztóit. Ezek mind nagyobbak N -nél (miért?), és nem oszthatók 3-mal, tehát mindegyikük vagy 3 k - 1 vagy 3 k + 1 alakú. Nem lehet mindegyik 3 k + 1 alakú, mert akkor N ! - 1 maga is 3 k + 1 alakú lenne, holott N ! - 1 3-mal osztva - 1 -et ad maradékul. Így N ! - 1 prímosztói között van 3 k - 1 alakú, ami tehát egy N -nél nagyobb 3 k - 1 alakú prím.

Szó szerint ugyanígy láthatjuk be, hogy végtelen sok 4 k - 1 alakú prímszám van. Az azonban már nehezebb kérdés, hogy van-e végtelen sok 3 k + 1 alakú vagy végtelen sok 4 k + 1 alakú prímszám. Az utóbbi állítás így látható be. Először azt fogjuk bizonyítani, hogy ha n egész, akkor n 2 + 1 -nek nincs 4 k - 1 alakú pozitív osztója. Tegyük fel, hogy ez nemigaz, és legyen b a legkisebb 4 k - 1 alakú pozitív egész szám, amely osztója n 2 + 1 -nek valamely n egészre. Legyen n = q b + r , ahol 0 ? r //<// b . Ekkor r 2 + 1 és ( r - b ) 2 + 1 mindketten oszthatók b -vel. Jelöljük s -sel az r és r - b számok közül azt, amelyik páros. Ekkor tehát s 2 + 1 osztható b -vel, és | s | ? b . Itt | s | = b nyilván lehetetlen, ezért s 2 + 1 ? ( b - 1 ) 2 + 1 //<// b 2 . Legyen t = ( s 2 + 1 ) / b ; ekkor t //<// b és t is osztója s 2 + 1 -nek, tehát b választása folytán t nem lehet 4 k - 1 alakú. De t páratlan (mert s páros), ezért t csak 4 k + 1 alakú lehet. Ebből következik, hogy a t · b szám 4-gyel osztva - 1 maradékot ad. Ez azonban lehetetlen, mert t · b = s 2 + 1 és s páros. Ezzel az állítást beláttuk.

A fentiekből következik, hogy ha n páros, akkor n 2 + 1 minden prímosztója 4 k + 1 alakú. Speciálisan, ha N ? 2 , akkor ( N ! ) 2 + 1 minden prímosztója 4 k + 1 alakú és nagyobb N -nél, amivel beláttuk, hogy végtelen sok 4 k + 1 alakú prímszám van.

A következőkben a célunk a fenti gondolatmenet általánosítása lesz. Vegyük észre, hogy x 2 + 1 = F 4 ( x ) , tehát, ha a egész szám, akkor F 4 ( a ) minden prímosztója vagy 2 (és ekkor osztója 4-nek), vagy 4 k + 1 alakú. Ezt az állítást fogjuk általánosítani. Ehhez szükségünk lesz az ún. „kis Fermat-tételre”, ami azt állítja, hogy ha p prím és n nem osztható p -vel, akkor n p - 1 - 1 osztható p -vel. Ezt így láthatjuk be.

Az n , 2 n , , ( p - 1 ) n számok csupa különböző maradékot adnak p -vel osztva, hiszen p | i n - j n = ( i - j ) n esetén vagy p | n vagy p | i - j . Mivel a feltételezésünk szerint n nem osztható p -vel és 1 ? i , j ? p - 1 , így szükségképpen i = j .

Mivel az n , 2 n , , ( p - 1 ) n számok egyike sem osztható p -vel, ebből következik, hogy a p -vel vett osztási maradékaik az 1 , 2 , , p - 1 számok (esetleg más sorrendben). Így n · 2 n ? ( p - 1 ) n és 1 · 2 ? ( p - 1 ) azonos maradékot adnak p -vel osztva, azaz

p | n p - 1 ( p - 1 ) ! - ( p - 1 ) ! = n p - 1 - 1 ( p - 1 ) !

tehát p | n p - 1 - 1 , hiszen p nem osztója ( p - 1 ) ! -nak.

Most rátérünk az ígért általánosításra, melyet Bauer Mihály bizonyított: ha a egész szám, akkor F n ( a ) minden prímosztója vagy osztója n -nek, vagy n k + 1 alakú.

Bizonyítás. Legyen p egy prímosztója F n ( a ) -nek. Mivel (1) alapján F n ( a ) | a n - 1 , ezért p | a n - 1 , és így p nem osztója a -nak. Legyen d a legkisebb pozitív egész, amelyre a d - 1 osztható p -vel. Ekkor a hatványainak p -vel való osztási maradékai d szerint periodikus sorozatot alkotnak. Valóban, p | a d - 1 alapján p | a d + 1 - a , p | a d + 2 - a 2 , és általában p | a d + i - a i minden i -re. Ebből egyszerűen következik, hogy a m - 1 akkor és csak osztható p -vel, ha m osztható d -vel.

Amint láttuk, p | a n - 1 , és a kis Fermat-tétel szerint p | a p - 1 - 1 is igaz, tehát d | n és d | p - 1 . Ha d = n , akkor n | p - 1 , amiből p = n k + 1 , tehát a tétel állítása igaz. Tegyük fel, hogy d //<// n . Belátjuk, hogy ekkor p | n .

Mivel d | n és d //<// n , ezért (1)-et n -re és d -re alkalmazva azt kapjuk, hogy az ( x n - 1 ) / ( x d - 1 ) polinom mindazon F m körosztási polinomok szorzata, melyekre m osztója n -nek, de nem osztója d -nek. Ezek között F n is ott van, így p | F n ( a ) alapján p osztója ( a n - 1 ) / ( a d - 1 ) -nak. Azonban

a n - 1 a d - 1 = 1 + a d + + a n - d = ( a d - 1 ) + ( a 2 d - 1 ) + + ( a n - d - 1 ) + n d ,

és itt mindegyik a i d - 1 alakú tag is osztható p -vel. Így n / d is osztható p -vel, amivel a tételt bebizonyítottuk.

A fenti tételt illusztrálandó térjünk vissza a bevezetésben említett faktorizációs kérdéshez. Mint láttuk , 10 15 + 1 faktorizációja visszavezethető az 109889011 = f ( 10 ) szám faktorizációjára ahol f ( x ) = x 8 + x 7 - x 5 - x 4 - x 3 + x + 1 = F 15 ( - x ) . Mármost a fenti tétel szerint F 15 ( - 10 ) mindegyik prímosztója 15 k + 1 alakú, és így, mivel páratlan is, valójában 30 k + 1 alakú. Ez az információ jelentősen leszűkíti a lehetőségeket, hiszen a prímeknek csak kb. nyolcadát kell kipróbálnunk. Láthatjuk, hogy a konkrét esetben talált prímosztók (211, 241 és 2161) valóban 30 k + 1 alakúak.

A tételből könnyen levezethetjük, hogy bármely n pozitív egészre végtelen sok n k + 1 alakú prímszám van. Ugyanis, ha N ? n , akkor F n ( N ! ) minden prímosztója n k + 1 alakú és nagyobb N -nél.