If you're seeing this message, it means we're having trouble loading external resources on our website.

Ha webszűrőt használsz, győződj meg róla, hogy a *.kastatic.org és a *.kasandbox.org nincsenek blokkolva.

Fő tartalom

Kis Fermat-tétel

Bevezetés: az elemi számelmélet kulcsfontosságú eredményének bemutatása gyöngyökkel illusztrálva. Készítette: Brit Cruise.

Szeretnél részt venni a beszélgetésben?

Még nincs hozzászólás.
Tudsz angolul? Kattints ide, ha meg szeretnéd nézni, milyen beszélgetések folynak a Khan Academy angol nyelvű oldalán.

Videóátirat

Bob valami nagyon érdekes dologra bukkant, miközben többszínű fülbevalókat készített gyöngyökből a boltja számára. A vásárlói szeretik a változatosságot, úgyhogy úgy döntött, minden méretben az összes lehetséges stílust elkészíti. Először három gyöngyből rakta ki az összes lehetséges stílust. Minden fülbevaló egy gyöngysorból indul ki, majd a végek összeragasztásával egy gyűrűt kapunk. Először is: hány lehetséges sorozat van? Két színnel és három gyönggyel háromszor választhatunk két színből. 2 · 2 · 2 = 8 lehetséges különböző sorozat lehet. Ezután ki kell venni az egyszínű sorozatokat, mivel csak többszínű fülbevalók kellenek. Majd a gyöngyöket össze kell ragasztani, hogy gyűrűket kapjunk. Bob arra számított, hogy hat különböző fülbevalója lesz, de történt valami. Egy csomó fülbevalót nem tudott megkülönböztetni. Kiderült, hogy csak két stílus lett, mert minden darabhoz két, vele megegyező darab tartozik. Figyeld meg, hogy a csoport darabjai forgatással megfeleltethetőek egymással. A csoportok mérete attól függ, hány forgatás kell ahhoz, hogy visszajussunk a kiinduló állapothoz. Azaz hány forgatás kell egy teljes ciklushoz. Ez azt jelenti, hogy a sokszínű láncok eredeti halmaza egyenlően osztódik hármas csoportokra. Igaz ez más méretek esetén is? Ez kényelmes lenne, hiszen Bob mindegyik stílusból ugyanannyit szeretne. Kipróbálja négy gyöngyből is. Először elkészíti az összes lehetséges sorozatot. Négy gyöngy esetén két színből választhat minden helyen, úgyhogy 2 · 2 · 2 · 2 = 16. Ezután eltávolítja az egyszínű sorozatokat, és gyűrűkbe ragasztja a többit. Egyforma méretű csoportok keletkeznek? Úgy tűnik, nem. Mi történt? Figyeld meg, hogyan rendeződnek csoportba a sorozatok! Ha a sorozatok stílusa megegyezik, az egyiket a másikból úgy is megkaphatod, hogy az egyik végéről a gyöngyöt átteszed a másik végére. Van egy olyan stílus, amihez csak két sorozat tartozik. Ennek az az oka, hogy a sorozat kettő hosszúságú ismétlődő csoportokból épül fel. Úgyhogy csak két forgatás kell, hogy visszakapjuk az eredetit. Ezért ebben a csoportban csak két elem van. Nem lehet azonos elemszámú csoportokra osztani. Mi a helyzet az öt hosszúságú lánccal? Azokat fel lehet osztani azonos elemszámú stílusokra? Hoppá! Bob hirtelen rájön, hogy nem is kell a sorozatokat megcsinálni ahhoz, hogy megtudja. Biztos, hogy működik, mert az ötöt nem lehet elkészíteni ismétlő csoportokból, mert az öt nem osztható fel egyenlő részekre. Az öt prímszám. Függetlenül attól, hogy milyen többszínű sorozatból indulsz ki, mindig öt forgatás vagy gyöngy eltolás kell ahhoz, hogy visszakapjuk az eredetit. Minden sorozathoz öt hosszúságú ciklus tartozik. Ellenőrizzük le! Először felépítjük az összes lehetséges sorozatot, majd eltávolítjuk a két egyszínűt. Azután a sorozatokat azonos stílusú csoportokba rendezzük, és minden csoportból elkészítünk egy fülbevalót. Figyeld meg, hogy minden fülbevaló esetén egy teljes ciklushoz pontosan öt forgatás tartozik. Ezért ha az összes sorozatból gyűrűket ragasztunk, akkor azok öttagú csoportokra oszlanak. De egy lépéssel továbbmegy. Eddig csak két színt használt, de rájött arra, hogy ennek akárhány szín esetében igaznak kell lennie. Azért, mert minden, P prím számú gyöngyből álló sokszínű fülbevaló ciklushossza P, mivel a prímszámok nem oszthatók fel egyforma hosszúságú darabokra. De ha összetett számú gyöngyöt használunk, például hatot, akkor mindig lesz olyan sorozat, amihez rövidebb ciklus tartozik, mivel ismétlődő darabokból épül fel, és ezért kisebb csoportok keletkeznek. És meglepő módon így a kis Fermat-tételbe botlott. Adva van A szín és P hosszúságú sorozatok, ahol P prímszám, a lehetséges sorozatok száma A · A · A, P-szer, azaz A a P-ediken. Amikor elveszi az egyszínű sorozatokat, pontosan A sorozatot fog eltávolítani, mivel minden színhez tartozik egy ilyen. Marad A a P-ediken mínusz A sorozat. Amikor ezeket a sorozatokat összeragasztja, P elemszámú csoportokba rendeződnek, mivel minden fülbevaló ciklushossza P. Ezért P osztója A a P-ediken mínusz A-nak, és ez a lényeg. Ezt az állítást megfogalmazhatjuk a moduláris aritmetika segítségével is. Gondold végig: ha elosztod A a P-edikent P-vel, maradékul A-t kapsz. Ezt úgy is írhatjuk, hogy A a P-ediken kongruens A-val moduló P. Rábukkantunk a számelmélet egyik alapvető törvényére, pedig csak gyöngyökkel játszottunk.