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

A szabályos sokszögek szerkeszthetőségéről

A szabályos sokszögek szerkeszthetőségéről

Frenkel, Péter

A szerző köszönetet mond dr. Surányi Lászlónak hasznos megjegyzéseiért. 

Már az ókori görögök is tudták, hogy a szabályos 2 k , 3 · 2 k , 5 · 2 k , 15 · 2 k oldalú sokszögek megszerkeszthetőek (körzővel és vonalzóval). Az a kérdés, hogy más oldalszámok esetén mi a helyzet, 1796-ig eldöntetlen maradt. Ebben az évben az akkor 19 éves C. F. Gauss bebizonyította, hogy a szabályos 2 k · p 1 · p 2 · · p s oldalú sokszögek is megszerkeszthetőek, ahol p 1 , …, p s különböző Fermat-prímek ( p Fermat-prím, ha p //>// 2 prím és p - 1 2-hatvány). Az alábbi feladatsor fő célja ennek a tételnek a bizonyítása, többé-kevésbé Gauss eredeti gondolatmenetét követve. Fel fogjuk használni a komplex számokkal kapcsolatos alapvető fogalmakat és tételeket, valamint néhány jól ismert számelméleti tételt. (Gauss a fenti tétel megfordítását is igazolta: ha a szabályos n -szög megszerkeszthető, akkor n a fenti alakú. Ennek bizonyításával nem foglalkozunk.)

1. Bizonyítsuk be, hogy ha szerkeszthető szabályos n -szög, akkor szerkeszthető szabályos 2 k · n -szög is.

2. Bizonyítsuk be, hogy ha szerkeszthető szabályos p -szög és q -szög, ahol p és q relatív prímek, akkor szerkeszthető szabályos p · q -szög is.

Nevezzük a C komplex számsík z pontját szerkeszthetőnek, ha körzővel és vonalzóval megszerkeszthető, amennyiben kiindulásként adott a 0, az 1 és az i pont.

3. Bizonyítsuk be, hogy minden racionális szám (mint C pontja) szerkeszthető.

4. Tegyük fel, hogy a , b ? C szerkeszthetőek. Bizonyítsuk be, hogy a + b , a - b , a · b , a / b (ha b ? 0 ) és a (pontosabban, minden olyan szám, amelynek négyzete a ) is szerkeszthető.

5. Bizonyítsuk be, hogy ha ? , ß ? C , és ? + ß , ? · ß szerkeszthetőek, akkor ? és ß is.

Az első két feladat alapján tételünk bizonyításához elegendő a szabályos p -szög szerkeszthetőségének igazolása, ahol p Fermat-prím. Ehhez elég belátni, hogy az összes p -ik egységgyök szerkeszthető.

A legkisebb Fermat-prím a 3. Szabályos háromszöget persze mindenki tud szerkeszteni. Ennek szerkeszthetősége a fentiekből is következik: ha ? = cos 2 ? 3 + i · sin 2 ? 3 az első harmadik egységgyök, akkor ? + ? = 2 cos 2 ? 3 = - 1 és ? · ? ¯ = ? 2 = 1 szerkeszthetőek, tehát ? és ? ¯ is.

6. Bizonyítsuk be, hogy a szabályos ötszög szerkeszthető. (Ez komplex számok nélkül is megy, de most próbáljuk az ötödik egységgyököket használni!)

A következő Fermat-prím a 17. A 17-szög szerkeszthetőségének bizonyítására igen nehéz rájönni (a fentiek segítségével is), ezért az alábbiakban segítséget adunk hozzá (persze ennek elolvasása nélkül is lehet próbálkozni!).

A 17-szög szerkeszthetőségét – az ötszög esetével analóg módon – úgy bizonyíthatjuk, hogy az ? = cos 2 ? 17 + i · sin 2 ? 17 , ? 2 , ? 3 , , ? 16 úgynevezett primitív 17-ik egységgyököket két nyolcelemű, majd négy négyelemű, majd nyolc kételemű, majd 16 egyelemű csoportba osztjuk, és az 5. feladat állításának ismételt alkalmazásával sorban mindegyik csoport elemeinek összegéről bebizonyítjuk, hogy szerkeszthető. A kérdés az, hogy mik legyenek ezek a csoportok.

Legyen p //>// 2 tetszőleges prím és g egy egész szám. Azt mondjuk, hogy g primitív gyök modulo p , ha az 1, g , g 2 , … g -hatványok p -vel vett osztási maradékai minden nemnulla maradékot kiadnak. Például 2 primitív gyök mod 5, mert 2 0 ? 1 , 2 1 ? 2 , 2 2 ? 4 , 2 3 ? 3 ( mod 5 ) (az a ? b ( mod m ) jelölés azt jelenti, hogy a - b osztható m -mel). Ha g primitív gyök mod p , és a egy p -vel nem osztható egész, akkor a legkisebb olyan k ? 0 egész kitevőt, amelyre g k ? a ( mod p ) , az a szám indexének (pontosabban, mod p vett g alapú indexének) nevezzük.

7. Bizonyítsuk be (közvetlen számolással, vagy ha lehet, ügyesebben), hogy

a) 2 nem primitív gyök mod 17 , de

b) 3 igen. Milyen értékek fordulnak elő a 17-tel nem osztható számok indexei között?

c) Hogyan lehetne egy (nem programozható) zsebszámológéppel viszonylag gyorsan eldönteni, hogy 3 primitív gyök-e mod 257 (ez a következő Fermat-prím)?

8. Mivel 3 primitív gyök mod 17 , ezért minden primitív 17-ik egységgyök ? 3 s alakba írható, ahol s 16-os maradék erejéig van meghatározva (miért?). Sejtsük meg, hogyan érdemes csoportokba osztani őket!

9. Bizonyítsuk be a szabályos 17-szög szerkeszthetőségét!

10. Mit kell még bebizonyítanunk ahhoz, hogy a 9. feladat megoldását minden Fermat-prímre általánosíthassuk?

11. Bizonyítsuk be a hiányzó állításokat!

Ezzel tételünk bizonyítása teljes. Sajnos, azt senki sem tudja, hogy mik a Fermat-prímek, sőt még azt sem, hogy van-e belőlük végtelen sok, vagy hogy van-e belőlük ötnél több. Az könnyen látható, hogy ha 2 m + 1 //>// 2 prím, akkor m 2-hatvány (mert ha d egy páratlan osztója m -nek, akkor 2 m / d + 1 egy 1-nél nagyobb osztója 2 m + 1 -nek, így megegyezik vele, tehát d = 1 ). Tehát az F n = 2 2 n + 1 alakú, ún. Fermat-számokat kell vizsgálni. n = 0 , 1, 2, 3, 4 esetén F n prím. P. Fermat ennek alapján azt sejtette, hogy F n minden természetes n -re prím, de sejtését L. Euler megcáfolta, bebizonyítva, hogy F 5 osztható 641-gyel. Azóta (számítógép segítségével) kiderült, hogy F n összetett, ha 5 ? n ? 23 , és bizonyos nagyobb n -ekre is. Egyetlen olyan 4-nél nagyobb n -et sem találtak, amelyre F n prím volna. A Fermat-számok az ún. Pepin-teszttel vizsgálhatók: F n akkor és csak akkor prím, ha 3 ( F n - 1 ) / 2 ? - 1 ( mod F n ) (ezt nem bizonyítjuk).

Befejezésül még két feladat Euler fenti eredményével kapcsolatban:

12. Bizonyítsuk be, hogy F n minden prímosztója 2 n + 1 k + 1 alakú! ( n ? 2 esetén valójában n + 2 írható a kitevőbe, de ezt nem bizonyítjuk.)

13. Bizonyítsuk be, hogy F 5 osztható 641-gyel! (Segítségül: 641 = 5 4 + 2 4 .)

1. Megoldások

1. Csupán szögfelezésre van szükség.

2. Szabályos n -szög persze pontosan akkor szerkeszthető, ha 2 ? / n nagyságú szög szerkeszthető. Ezért elég belátni, hogy van olyan egész u és v , amelyre

2 ? p q = u 2 ? p + v 2 ? q ,

azaz

1 = u q + v p .

Mivel p és q relatív prímek, ilyen u és v létezik.

3. p / q megszerkesztéséhez (ahol p , q egészek és q //>// 0 ) megszerkesztjük p -t, i -t, és q · i -t, majd a p -t q · i -vel összekötő egyenessel i -n át párhuzamost húzunk. Ez kimetszi p / q -t a valós tengelyből.

4. a + b és a - b vektorok összeadását, illetve kivonását jelenti, így a szerkesztés könnyen elvégezhető.

arg a b = arg a + arg b és arg a / b = arg a - arg b , így ezek a szögek megszerkeszthetőek (itt arg z az origót a z ponttal összekötő vektornak az x tengely pozitív felével bezárt irányított szögét jelenti, pontosabban, szögeknek egy mindkét irányban végtelen, 2 ? differenciájú számtani sorozatát).

a b = a · b és a / b = a / b , tehát elég, ha ismert szakaszok szorzatát és hányadosát meg tudjuk szerkeszteni. Ez a párhuzamos szelők tételének segítségével történhet. (Legyen az O P Q háromszögben O P = 1 és O Q = b . a b szerkesztéséhez legyen R az O P félegyenesen olyan, hogy O R = a és S az O Q félegyenesen olyan, hogy R S ? P Q , ekkor O S = a b . a / b szerkesztéséhez legyen T az O Q félegyenesen olyan, hogy O T = a , és U az O P félegyenesen olyan, hogy T U ? P Q , ekkor O U = a / b .)

Végül, ha a ? 0 és a egy olyan szám, amelynek négyzete a , akkor arg a = 1 / 2 · arg a , ez két szerkeszthető szöget jelent (a [ 0 , 2 ? ) intervallumban), míg a = a , ennek szerkesztése a magasságtétel segítségével történhet. (Legyen A , T , B ebben a sorrendben egy egyenesen úgy, hogy A T = a , T B = 1 , és messe a T -ben állított merőleges A B Thalész-körét C -ben. Ekkor T C = a .) Legvégül, 0 = 0 szerkeszthető.

5. ? és ß az ( x - ? ) ( x - ß ) = x 2 - ( ? + ß ) x + ? ß másodfokú polinom gyökei, ezért ? , ß = ? + ß ± ( ? + ß ) 2 - 4 ? ß 2 (ami persze közvetlenül is ellenőrizhető). Az előző feladat értelmében tehát ? és ß szerkeszthető.

6. Legyen ? = cos 2 ? 5 + i · sin 2 ? 5 . ( ? + ? 4 ) ( ? 2 + ? 3 ) = ? 3 + ? 4 + ? 6 + ? 7 = ? 3 + ? 4 + ? + ? 2 = - 1 + 1 + ? + ? 2 + ? 3 + ? 4 = - 1 + ? 5 - 1 ? - 1 = - 1 . Tehát ? + ? 4 és ? 2 + ? 3 összege és szorzata is ( - 1 ) , ami szerkeszthető, így ez a két szám is. ? · ? 4 = ? 2 · ? 3 = ? 5 = 1 , így ? , ? 2 , ? 3 , ? 4 szerkeszthetőek.

7. a) 2 4 = 16 ? - 1 ( mod 17 ) , így 2 8 = ( 2 4 ) 2 ? ( - 1 ) 2 = 1 , ezért a 2-hatványok mod 17 maradékai 8 szerint periodikus sorozatot alkotnak ( 2 8 ? 1 = 2 0 , 2 9 = 2 · 2 8 ? 2 · 2 0 = 2 1 , 2 10 = 2 · 2 9 ? 2 · 2 1 = 2 2 stb.), tehát legfeljebb nyolcféle maradék lép fel.

b) 3 0 = 1 , 3 1 = 3 , 3 2 = 9 ? - 8 , 3 3 ? 3 · ( - 8 ) ? - 7 3 4 ? 3 · ( - 7 ) ? - 4 , 3 5 ? 3 · ( - 4 ) ? 5 , 3 6 ? 3 · 5 ? - 2 , 3 7 ? 3 · ( - 2 ) = - 6 , 3 8 ? 3 · ( - 6 ) ? - 1 , ettől kezdve a fenti jobb oldalak ( - 1 ) -szereseit kapjuk a 3-hatványok legkisebb abszolútértékű maradékaiként ( 3 k + 8 = 3 8 · 3 k ? - 3 k ( mod 17 ) ), tehát 3 0 , 3 1 , …, 3 15 maradékai kiadják a [ - 8 ; 8 ] intervallum egészeit a 0 kivételével. Így a 0, 1, …, 15 számok fordulnak elő indexként.

A c) feladat megoldásából látni fogjuk, hogy kevesebb számolással is célt érhettünk volna.

c) Általában, ha az a egész szám nem osztható a p prímmel, akkor nevezzük az a rendjének ( mod p ), és jelöljük o p ( a ) -val a legkisebb olyan pozitív egész k -t, amelyre a k ? 1 ( mod p ) . Ilyen k biztosan van (egyrészt azért, mert a kis Fermat-tétel szerint k = p - 1 ilyen, másrészt azért, mert a skatulyaelv szerint van olyan 0 ? l //<// m egész, hogy a l ? a m ( mod p ) , amit a modulushoz relatív prím a l -nel osztva a m - l ? 1 ( mod p ) adódik). Az a -hatványok mod p maradékai o p ( a ) szerint periodikus sorozatot alkotnak ( a k + o p ( a ) = a o p ( a ) · a k ? a k ( mod p ) ), és egy perióduson belül csupa különböző szám szerepel (mert l //<// m , a l ? a m esetén a m - l ? 1 , tehát m - l ? o p ( a ) ). Így a n ? 1 ( mod p ) pontosan akkor teljesül, ha n osztható o p ( a ) -val; ebből és a kis Fermat-tételből adódik, hogy p - 1 osztható o p ( a ) -val. Az a -hatványok pontosan o p ( a ) -féle maradékot adnak mod p ; a pontosan akkor primitív gyök, ha o p ( a ) = p - 1 . Ha a primitív gyök, akkor 1 , a , , a p - 2 kiad minden nemnulla maradékot pontosan egyszer.

Speciálisan, 3 pontosan akkor primitív gyök mod 257 , ha o 257 ( 3 ) = 256 . Mivel o 257 ( 3 ) biztosan osztója 256-nak, ez ekvivalens azzal, hogy nem osztója 128-nak, azaz, hogy 3 128 ? 1 ( mod 257 ) . Számológéppel, hét egymást követő négyzetreemeléssel meggyőződhetünk róla, hogy valóban ez a helyzet, tehát 3 primitív gyök. (Persze minden négyzetreemelés után mod 257 maradékot érdemes számítani, hogy ne kapjunk túl nagy számokat.) Meg tudnánk jósolni a számolás előtt, hogy ha 3 128 257-es maradéka nem 1, akkor mennyi?

8. 3 16 ? 1 ( mod 17 ) miatt a 3-hatványok 17-es maradékainak sorozata 16 szerint periodikus, és egy ilyen perióduson belül nincs ismétlődés (épp ezt jelenti az, hogy a 3 primitív gyök), tehát ? 3 s = ? 3 t ekvivalens azzal, hogy s ? t ( mod 16 ) .

Az alábbiakat könnyebb lesz követni, ha a tizenhat primitív 17-edik egységgyököt egy kör kerületén képzeljük el, ilyen sorrendben: ? 3 0 , ? 3 1 , …, ? 3 15 . (Ez teljesen más, mint a megszokott sorrend!)

A célravezető csoportosítás a következő. Az ? 3 s ( s = 0 , 1 , , 15 ) primitív 17-edik egységgyököket osszuk két nyolcelemű csoportba s paritása szerint, majd négy négyelemű csoportba s négyes maradéka szerint, majd nyolc kételemű csoportba s nyolcas maradéka szerint, majd tizenhat egyelemű csoportba. Amikor s 2 k -as maradéka szerint csoportosítunk ( k = 0 , 1 , 2 , 3 , 4 ), akkor a létrejövő ( 2 4 - k elemű) csoportokat így jelöljük:

S 2 k , r = ? 3 s : s ? r ( mod 2 k ) ( r = 0 , 1 , , 2 k - 1 ) .

(Ezzel az S 1 , 0 = ? 3 0 , ? 3 1 , , ? 3 15 = ? , ? 2 , , ? 16 jelölést is bevezettük a teljes 16-elemű halmazra.) (Ha a tizenhat egységgyököt a fent említett módon képzeljük el egy kör kerületén, akkor S 2 k , r elemeit úgy kaphatjuk meg, hogy ? 3 r -et és tőle indulva, a kör mentén haladva minden 2 k -adik elemet tekintjük.)

9. Jelölje S 2 k , r elemeinek összegét ? 2 k , r . ? 1 , 0 = ? + ? 2 + + ? 16 = - 1 + ? 17 - 1 ? - 1 = - 1 szerkeszthető. Belátjuk, hogy ? 2 , 0 és ? 2 , 1 szerkeszthető. Az 5. feladat szerint elég belátni, hogy összegük és szorzatuk szerkeszthető. ? 2 , 0 + ? 2 , 1 = ? 1 , 0 valóban szerkeszthető.

? 2 , 0 · ? 2 , 1 = ? 3 0 + ? 3 2 + + ? 3 14 ? 3 1 + ? 3 3 + + ? 3 15 = = ? 3 0 + 3 1 + ? 3 1 + 3 2 + ? 3 2 + 3 3 + + ? 3 15 + 3 0 + + ? 3 0 + 3 3 + ? 3 1 + 3 4 + + ? 3 15 + 3 2 + + ? 3 0 + 3 5 + ? 3 1 + 3 6 + + ? 3 15 + 3 4 + + ? 3 0 + 3 7 + ? 3 1 + 3 8 + + ? 3 15 + 3 6 .

A kitevők mind a négy zárójelen belül egy-egy 16-tagú, 3 kvóciensű mértani sorozatot alkotnak mod 17 . Ezért mod 17 maradékaik vagy mind nullák (ez az eset valójában nem lép fel), vagy mind különböző nemnulla maradékok (mert 3 primitív gyök). (Valóban, ha s nem osztható 17-tel, akkor s , 3 s , 3 2 s , …, 3 15 s redukált maradékrendszer mod 17 , hiszen a 3-mal való szorzás 1-gyel növeli az index értékét mod 16 , így s , 3 s , 3 2 s , …, 3 15 s indexei között 0 , 1 , , 15 mindegyike pontosan egyszer fordul elő.) (A második esetben az egy zárójelben lévő primitív 17-dik egységgyököket úgy kaphatjuk meg, hogy bármelyiküktől kezdve egyesével lépkedünk a körön.) Ezért mind a négy zárójelben lévő összeg vagy 16 1-esből, vagy S 1 , 0 tizenhat eleméből áll, ezért vagy 16, vagy ? 1 , 0 , azaz ( - 1 ) . ? 2 , 0 · ? 2 , 1 tehát szerkeszthető (valójában ( - 4 ) ), így ? 2 , 0 és ? 2 , 1 is.

Hasonlóan, ? 4 , 0 , ? 4 , 1 , ? 4 , 2 , ? 4 , 3 szerkeszthetőségéhez elég belátni, hogy ? 4 , 0 + ? 4 , 2 , ? 4 , 0 · ? 4 , 2 , ? 4 , 1 + ? 4 , 3 , ? 4 , 1 · ? 4 , 3 szerkeszthető. ? 4 , 0 + ? 4 , 2 = ? 2 , 0 és ? 4 , 1 + ? 4 , 3 = ? 2 , 1 valóban szerkeszthető.

? 4 , 0 · ? 4 , 2 = ? 3 0 + ? 3 4 + ? 3 8 + ? 3 12 ? 3 2 + ? 3 6 + ? 3 10 + ? 3 14 = = ? 3 0 + 3 2 + ? 3 2 + 3 4 + ? 3 4 + 3 6 + + ? 3 14 + 3 0 + + ? 3 0 + 3 6 + ? 3 2 + 3 8 + + ? 3 14 + 3 4 .

A kitevők mindkét zárójelen belül egy-egy 8-tagú, 3 2 kvóciensű mértani sorozatot alkotnak mod 17 , így mod 17 maradékaik vagy mind nullák (ez az eset valójában nem lép fel), vagy mind különbözőek, de indexük paritása megegyező. (17-tel nem osztható szám indexét a 3 2 -nel való szorzás 2-vel növeli mod 16 .) (A második esetben az egy zárójelben lévő primitív 17-dik egységgyököket úgy kaphatjuk meg, hogy bármelyiküktől kezdve kettesével lépkedünk a körön.) Így mindkét zárójelben levő összeg vagy nyolc 1-esből, vagy S 2 , 0 nyolc eleméből, vagy S 2 , 1 nyolc eleméből áll, ezért vagy 8, vagy ? 2 , 0 , vagy ? 2 , 1 . ? 4 , 0 · ? 4 , 2 mindenképp szerkeszthető. ? 4 , 1 · ? 4 , 3 szerkeszthetősége ugyanígy igazolható.

Hasonlóan, ? 8 , 0 , ? 8 , 1 , …, ? 8 , 7 szerkeszthetőségéhez elég belátni, hogy ? 8 , 0 + ? 8 , 4 , ? 8 , 0 · ? 8 , 4 , …, ? 8 , 3 + ? 8 , 7 , ? 8 , 3 · ? 8 , 7 szerkeszthető. A négy összeg éppen ? 4 , 0 , ? 4 , 1 , ? 4 , 2 , ? 4 , 3 így szerkeszthető; a szorzatokra például

? 8 , 0 · ? 8 , 4 = ? 3 0 + ? 3 8 ? 3 4 + ? 3 12 = = ? 3 0 + 3 4 + ? 3 4 + 3 8 + ? 3 8 + 3 12 + ? 3 12 + 3 0 .

A kitevők 4-tagú, 3 4 kvóciensű mértani sorozatot alkotnak mod 17 , így mod 17 maradékaik vagy mind nullák (valójában nem), vagy mind különbözőek, de indexük 4-es maradéka megegyezik. Ezért ? 8 , 0 · ? 8 , 4 (és ugyanígy a másik három szorzat) ? { 4 , ? 4 , 0 , ? 4 , 1 , ? 4 , 2 , ? 4 , 3 } , és így szerkeszthető.

Végül, a ? 16 , r = ? 3 r primitív 17-ik egységgyökök szerkeszthetőségének igazolásához elég ? 16 , 0 · ? 16 , 8 , …, ? 16 , 7 · ? 16 , 15 szerkeszthetőségét belátni. De e számok mindegyike 1, mert

? 16 , r · ? 16 , r + 8 = ? 3 r + 3 r + 8 = ? 3 r ( 1 + 3 8 ) = 1 ,

mert a 7. b) feladat megoldása közben láttuk, hogy 3 8 ? - 1 ( mod 17 ) .

10. A bizonyítás kézenfekvő módon általánosítható, mihelyt tudjuk, hogy

a) minden Fermat-prímhez létezik primitív gyök.

b) ha g primitív gyök a p //>// 2 prímre nézve, akkor g p - 1 2 ? - 1 ( mod p ) .

A következő erősebb állítások is igazak:

a ' ) minden prímhez létezik primitív gyök;

a ) minden 3-nál nagyobb Fermat-prímre primitív gyök a 3 (de a 2 csak 3-ra és 5-re).

Ezek bizonyítása azonban nehezebb, és nincs rájuk szükségünk.

Az általánosított bizonyítást csak vázoljuk, mert semmilyen új gondolatra nincs szükség.

Legyen g egy primitív gyök a p = 2 m + 1 Fermat-prímre nézve. Az ? g 0 , ? g 1 , , ? g p - 2 primitív p -edik egységgyököket a p = 17 esettel analóg módon csoportosítjuk:

S 2 k , r = ? g s : s ? r ( mod 2 k ) ( k = 0 , 1 , , m ; r = 0 , 1 , , 2 k - 1 ) .

k szerinti teljes indukcióval megmutatjuk, hogy mindegyik S 2 k , r elemeinek összege, ? 2 k , r , szerkeszthető (tehát a ? 2 m , r = ? g r ( r = 0 , 1 , , 2 m - 1 ) primitív p -edik egységgyökök is). k = 0 -ra ez igaz, mert ? 1 , 0 a primitív p -edik egységgyökök összege, - 1 . Tegyük fel, hogy valamely 0 ? k //<// m -re mindegyik ? 2 k , r szerkeszthető, és lássuk be ugyanezt ( k + 1 ) -re! Az 5. feladat alapján elég belátni, hogy ? 2 k + 1 , r és ? 2 k + 1 , r + 2 k összege és szorzata szerkeszthető ( r = 0 , 1 , , 2 k - 1 ). Az összeg ? 2 k , r , az indukciós feltevés szerint szerkeszthető. A szorzat vizsgálatához különválasztjuk a k //<// m - 1 és k = m - 1 eseteket.

Ha k //<// m - 1 , akkor a

? 2 k + 1 , r · ? 2 k + 1 , r + 2 k = ? 0 ? s //<// 2 m s ? r ( 2 k + 1 ) ? g s · ? 0 ? t //<// 2 m t ? r + 2 k ( 2 k + 1 ) ? g t = ? 0 ? s //<// 2 m s ? r ( 2 k + 1 ) ? 0 ? t //<// 2 m t ? r + 2 k ( 2 k + 1 ) ? g s + g t

kifejezésben szereplő tagokat csoportosítsuk s és t mod 2 m vett távolsága szerint. (Ezen ( s - t ) -nek a legközelebbi 2 m -mel osztható egésztől való távolságát értjük.) A távolság lehetséges értékei 2 k , 3 · 2 k , …, 2 m - k - 1 - 1 2 k . Így 2 m - k - 2 rész-összeget kapunk, mindegyik 2 m - k tagból áll (mert a 2 m - k - 1 megengedett s érték bármelyikét és a lehetséges távolságok bármelyikét rögzítve pontosan két megengedett t érték van attól az s -től olyan távolságra).

A d távolsághoz tartozó rész-összeg

? 0 ? u //<// 2 m u ? r ( 2 k ) ? g u + g u + d .

Ebben ? kitevői 2 m - k -tagú, g 2 k kvóciensű mértani sorozatot alkotnak mod p , ezért mod p maradékaik vagy mind nullák (ez az eset valójában nem lép föl), vagy mind különbözőek, de indexük 2 k szerinti maradéka megegyezik. Tehát mindegyik rész-összeg vagy 2 m - k darab 1-esből, vagy (valamilyen r -re) S 2 k , r elemeiből áll. Így mindegyik rész-összeg ? 2 m - k , ? 2 k , 0 , ? 2 k , 1 , , ? 2 k , 2 k - 1 , és így szerkeszthető. Tehát ? 2 k + 1 , r · ? 2 k + 1 , r + 2 k is szerkeszthető.

Ha k = m - 1 , akkor

? 2 k + 1 , r · ? 2 k + 1 , r + 2 k = ? 2 m , r · ? 2 m , r + 2 m - 1 = = ? g r · ? g r + 2 m - 1 = ? g r + g r + 2 m - 1 = ? g r 1 + g 2 m - 1 = 1 ,

hiszen g 2 m - 1 = g p - 1 2 ? - 1 ( mod p ) (itt használjuk a b) állítást).

11. b) g p - 1 2 - 1 g p - 1 2 + 1 = g p - 1 - 1 osztható p -vel (kis Fermat-tétel), de a bal oldal első tényezője nem (mert g primitív gyök), így a második tényezője igen.

a) Tegyük fel indirekt módon, hogy 1, 2, …, p - 1 egyike sem primitív gyök a p Fermat-prímre nézve. Ekkor mindegyikük rendje[23] osztója a p - 1 2-hatványnak és kisebb nála, tehát osztója p - 1 2 -nek. Így az x p - 1 2 ? 1 ( mod p ) kongruenciának van p - 1 (páronként inkongruens) megoldása. Ezzel szemben teljes indukcióval belátjuk, hogy x 2 k ? c ( mod p ) -nek legfeljebb 2 k megoldása van (valójában az is igaz, hogy n -edfokú mod p kongruenciának legfeljebb n megoldása van). k = 0 -ra ez világos. Tegyük fel k -ra, és lássuk be k + 1 -re! x 2 k + 1 ? c ( mod p ) minden megoldása egy x 2 ? d ( mod p ) alakú kongruenciának is megoldása, ahol d az x 2 k ? c egy megoldása. Ilyen d -ből az indukciós feltevés szerint legfeljebb 2 k van, ezért elég belátni, hogy x 2 ? d -nek legfeljebb két megoldása van. Ez világos, mert ha x és y két megoldás, akkor x 2 - y 2 = ( x - y ) ( x + y ) osztható p -vel, tehát x ? ± y ( mod p ) (mert p prím).

12. Ha F n egy prímosztója p , akkor 2 2 n ? - 1 ( mod p ) , ezt négyzetre emelve 2 2 n + 1 ? 1 ( mod p ) . Tehát 2 rendje[24], o p ( 2 ) , osztója 2 n + 1 -nek, de 2 n -nek nem, ezért o p ( 2 ) = 2 n + 1 . De p - 1 osztható o p ( 2 ) -vel (kis Fermat-tétel), így készen vagyunk.

13.

F 5 = 2 32 + 1 = 2 4 · ( 2 7 ) 4 + 1 ? - 5 4 · ( 2 7 ) 4 + 1 = - ( 5 · 2 7 ) 4 + 1 = = - 640 4 + 1 ? - ( - 1 ) 4 + 1 = 0 ( mod 641 ) .


[23] Emlékeztetjük az olvasót, hogy a rend fogalmát a 7. c) feladat megoldásában definiáltuk.

[24] Emlékeztetjük az olvasót, hogy a rend fogalmát a 7. c) feladat megoldásában definiáltuk.