Néhány érdekes számhalmaz és alkalmazásaik

Bevezető példa: Milyen nap lesz 1000 nap múlva?

Megoldás: 1000 nap alatt eltelik néhány egész hét, és még néhány nap. Ez utóbbi a fontos. 1000-et maradékosan osztjuk 7-tel: az eredmény 142, a maradék 6. Tehát a keresett nap olyan, mint ami 6 nap múlva jön, és amilyen nap mellesleg tegnap is volt.

Az ilyen és hasonló kérdések megoldásában nagy segítséget nyújt egy különös számhalmaz. Fogjuk meg a számegyenest, és tekercseljük fel úgy, hogy a 7-es szám a 0-t fedje! Az így kapott halmaz mindössze hételemű, és pl. a 20-as "egyenlő" lesz a 6-ossal és a -1-gyel is. (Szemléletesen: a hétnek ugyanarra a napjára esnek.)

A 0-hoz tartozó számok mind oszthatók 7-tel, azaz maradékuk nulla. A 3-hoz tartozók 7-tel osztva 3 maradékot adnak, és így tovább. Ezért azt mondhatjuk, hogy e hételemű halmaz elemei maguk is halmazok: az illető 0;1;2;3;4;5;6 maradékokat szolgáltató egész számok halmazai. Def: Ezeket a 0;...;6 számok maradékosztályainak nevezzük. A hételemű karika hivatalos neve: a modulo 7 (azaz: 7 szerinti) maradékosztályok gyűrűje, vagy modulo 7 teljes maradékrendszer. Jelölés: Z₇.

Az ugyanazon maradékosztálybeli elemek "hetesileg egyezőek," szakkifejezéssel kongruensek egymással modulo 7. Jelölés. 1000 ≡ 6 (7) vagy 1000 ≡ -1 (7)

Megjegyzés: Némiképp meglepőnek tűnhet, hogy -10 nem 3, hanem 4 maradékot ad 7-tel osztva. Ezt úgy értelmezhetjük, hogy 4-gyel nagyobb, mint a balra legközelebbi 7-tel osztható szám, a -14. És mivel -10 3-mal kisebb, mint -7, azt is mondhatjuk, hogy -10 7-tel osztva "-3 maradékot ad."

Összeadás Z₇-ben

Kongruenciák megfelelő oldalait egymással össze lehet adni és egymásból ki lehet vonni. Például 17 ≡ 3 (7) és 8 ≡ 1 (7). Összeadva a 25 ≡ 4 (7) és a 9 ≡ 2 (7) igaz kongruenciák adódnak. Ennek oka az, hogy két szám összeadásakor a 7-es osztási maradékok is egymásra halmozódnak. Előfordulhat, hogy a végső maradék túlcsordul a 7-en vagy a 0-n, pl. 25 ≡ 4 (7) és 12 ≡ 5 (7) kongruenciákat összeadva 37 ≡ 9 ≡ 2 (7) és kivonva 13 ≡ -1 ≡ 6 (7), ami szintén igaz állítás.

1. házi feladat: 33 nap múlva kezdődik a dinnyemagköpő VB, amely a nyitónap után még 22 napig tart. Milyen napra esik a befejező versenynap? Felelj a 33 és a 22 összeadása nélkül is! Ellenőrizd az egyezést!

Szorzás Z₇-ben

Bonyolultabb feladat: Milyen napra esett száz éve az évnek ugyanez a napja? A válaszhoz úgy juthatunk el a legkönnyebben, hogy először kiderítjük, hány nap telt el azóta. 1899 és 1999 ugyanazon napja között 100·365 nap van, és még néhány szökőnap. Mivel 1900 nem volt szökőév, ezek száma 24, hiszen az elsőt kivéve minden négyéves szakaszra jut egy szökőnap. Tehát 36524 nap telt el azóta. Ez 7-tel osztva 5 maradékot ad, vagyis a keresett nap ugyanolyan, mint a naptárban 5-tel ezelőtti nap.

Ez a feladatot Z₇ nyelvén is megfogalmazhatjuk: Mivel kongruens -100·365 - 24 modulo 7? (Magyarul: milyen maradékot ad 7-tel osztva?) Ehhez darabonként megnézzük a maradékokat:

100 ≡ 2 (7)
365 ≡ 1 (7),
24 ≡ 3 (7).

Az "egyenlőségek" (kongruenciák) bal ill. jobb oldalait egymással összeszorozva és összeadva: 100·365+24 ≡ 2·1+3 ≡ 5 (7). Ugyanoda jutottunk, mint a 36524:7 maradékos osztással. Ennek az ellentettjét vesszük, mert a dolog a múltban volt, és készen vagyunk.

2. házi feladat: Vajon mindig szabad-e egy szorzást tartalmazó kongruenciában egy számot kicserélni olyannal, ami vele egyazon maradékosztályba esik? (Azaz fennmarad-e a ≡ jellel jelölt "egyezőség?") Ellenőrizd a választ a 10·10 ≡ ? (7), 100·10 ≡ ? (7), 58·38 ≡ ? (7) kongruenciákon! Mit ad maradékul (64+37)·(75-16) héttel osztva? Pluszkérdés: Ugye mennyivel könnyebb darabonként venni a maradékot, mint a nagy számot elosztani?

3. házi feladat: Bizonyítsd be, hogy ha a ≡ b (7), akkor 7|b-a!

A házi feladatok megoldásai

1. 33+22 ≡ 6 ≡ -1 (7), azaz a tegnapi nappal azonos. Összeadás nélkül: 33 ≡ 5 (7), 22 ≡ 1 (7), 5+1 ≡ 6 (7).

2. Igen, szabad. A példák megoldásai:
10·10 = 100 ≡ 2 (7). Másrészt 10 ≡ 3 (7), és 3·3 = 9 ≡ 2 (7).
100·10 = 1000 = 7·142+6, azaz 1000 ≡ 6 (7). Másrészt 10 ≡ 3 (7), 100 ≡ 2 (7), összeszorozva 1000 ≡ 6 (7).
58 ≡ 2 (7) és 38 ≡ 3 (7), összeszorozva 58·38 ≡ 6 (7). Fárasztóbb kiszámolni, hogy 58·38 = 2204 = 7·314+6.
Végül: (64+37)·(75-16) ≡ (1+2)·(5-2) ≡ 3·3 ≡ 2 (7).

Az állítás könnyen szemléltethető ábrán. Azt kell belátni, hogy egy szorzat annyit ad maradékul, mint a maradékok szorzata. Tekintsük ehhez az a, b számokat, amelyek rendre m₁, m₂ maradékot adnak 7-tel osztva. A belső osztóvonalak 7-esével követik egymást. Az a·b mennyiség satírozott részei 7-tel oszthatók. Az a·b maradéka tehát m₁ ·m₂, illetve annak további maradéka, ha túlcsordul 7-en.

Alkalmazás: 9-es próba. 10 minden hatványa 1-et ad maradékul 9-cel osztva, ezért minden számnak ugyanaz a maradéka, mint a jegyösszegének. 1. Hf: Állapítsuk meg egyszerűen, hogy lehet-e helyes a 271935·68452 = 18614594620 szorzás? Mennyire biztos ez a módszer?

Állítás: ha a ≡ b (7), akkor 7|b–a. Induljunk ki a bal oldalból, amely szerint a és b ugyanazt adja maradékul 7-tel osztva. Ha kivonjuk a-t b-ből, akkor a maradékaik is kivonódnak, így b–a maradéka 0 lesz. Ez pedig éppen azt jelenti, hogy 7| b–a.

Megjegyzés: az állítás megfordítható. Induljunk ki a jobb oldalból, és tegyük fel, hogy a bal oldal nem igaz (indirekt feltevés). Vagyis a és b más maradékot ad 7-tel osztva. Ezek a maradékok 0-nál nem kisebbek, és 7-nél kisebbek, tehát különbségük –7-nél nagyobb, 7-nél kisebb, és az indirekt feltevés miatt nem egyenlő 0-val. Ez a különbség azonban nem más, mint b–a maradéka, amely ezek szerint nem osztható 7-tel. (Indokold meg!) Ez ellentmondás, hiszen feltettük, hogy osztható. Mivel az indirekt feltevés megdőlt, készen vagyunk.

Ezt a tételkét igen szívesen fogjuk alkalmazni, mert a kongruencia eredeti definíciója ("ugyanazt a maradékot adják") elég nehezen kezelhető, míg az oszthatóság sokkal kézenfekvőbb fogalom. Egyébként az egyetemen éppen azzal definiálják két szám (modulo 7 vett) kongruensségét, hogy "különbségük osztható 7-tel."

---

2. Más maradékosztály-gyűrűk

Eddig leginkább a 7-tel való osztási maradékkal foglalkoztunk, mert ennyi napja van a hétnek. A gyakorlatban más számok is átvehetik a 7 szerepét. (Ezt úgy mondjuk, hogy más lesz a modulus.) Először is a 10 jön szóba, például az ilyen kérdések kapcsán: "Milyen jegyre végződik 7⁵⁰⁰ a 10-es számrendszerben?" Később erre (és nehezebbekre) is felelünk, de most az egyszerűség kedvéért kerítsük sorra a Z₆ gyűrűt. Ezt ugyanúgy kell lerajzolni, mint Z₇-et, ezért rögtön elkezdhetjük kitölteni a "szorzótáblát," amely tartalmazza a leglényegesebb tudnivalókat. Az összehasonlítás végett Z₇-re is csináljuk meg a szorzótáblát.

Z7 · 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 2 0 2 4 6 1 3 5 3 0 3 6 2 5 1 4 4 0 4 1 5 2 6 3 5 0 5 3 1 6 4 2 6 0 6 5 4 3 2 1

A táblázat kitöltése úgy történik, hogy vesszük a két szám közönséges (10-es számrendszerbeli) szorzatát, majd megnézzük, mit ad maradékul 7-tel (illetve 6-tal) osztva. Megfigyelhetjük, hogy Z7 minden sora az első sor átrendezése (kivéve persze a 0-val való szorzást). Z6-ban viszont nem ez a helyzet.

Z6 · 0 1 2 3 4 5 0 0 0 0 0 0 0 1 0 1 2 3 4 5 2 0 2 4 0 2 4 3 0 3 0 3 0 3 4 0 4 2 0 4 2 5 0 5 4 3 2 1

2. Hf. Mitől függ, hogy Z₆-ban egy szorzás "átrendezi"-e a számokat vagy "ismétel"? A kérdés így túl nehéz, ezért gyűjtsünk további tapasztalatokat Z₈, Z₉ és Z₁₀ szorzótábláján!

3. Hf. Vegyük észre, hogy ha egy g elemmel való szorzás "átrendezi" a számokat, akkor van olyan h, amelyre g·h = 1. Az ilyen h-t a g elem reciprokának nevezzük. Hogy festene Z₇-ben a 4/5 "tört?" (Először 1/5-öt érdemes megkeresni.) És Z₆-ban? No és az 1/2?

4. Hf. Ha jobban megnézzük Z₆-ot, szörnyű dolgot láthatunk: némely 0-tól különböző számok szorzata nulla! Melyek ezek? A teljesebb válaszhoz segítséget nyújthat Z₈, Z₉ és Z₁₀ szorzótáblája.

---

3. "Szép" és "csúnya" elemek

(A házi feladatok megoldásai menet közben jönnek elő)

1. 271935 jegyösszege 27, ennek 9-es maradéka 0, tehát a nagy számé is. 68452 pedig 7-et ad. A szorzat maradéka tehát 0 kell, hogy legyen, de ez nem teljesül, mert 18614594620 maradéka 1. Vagyis a szorzás rossz. Meg kell jegyeznünk, hogy a módszer nem szűri ki azokat a számolási hibákat, ahol pl. 9 helyére 0-et írtunk, mert ekkor a 9-es osztási maradék nem változik. Szintén észrevétlenek maradnak az olyasfajta durva hibák, amikor két összeadandó sor "elcsúszik" egymáshoz képest – elvégre ekkor valamelyik részeredmény tízszerese vagy éppen tizede lesz a valódinak, ami nem változtat a 9-es maradékán. A módszer tehát ún. negatív próba, azaz ha jelez, akkor hiba van, de nem minden hibát jelez. Mivel 9 db maradékosztály van, annak esélye, hogy egy elírás éppen 9-cel változtatja meg a jegyösszeget, 1/9 = 11%. Valójában az effajta hibák igen ritkák, mivel a szimpla tévesztések közül a 9-0 az egyedüli, amely megtréfálhat minket. Vagyis a módszer elég jó.

Megjegyzés: A 9-es próbánál egy fokkal jobb a 11-es próba. Mivel 1, 100, 10000 stb. 1-et ad maradékul, 10, 1000 és 100000 stb. pedig 10-et (egyelőre el kell hinnünk, hogy ez tovább is így van), és a 10 mint modulo 11 maradék kicserélhető –1-re, a szám a következő maradékot adja: 7593 = 3·1+9·10+5·100+7·1000 ≡ 3·1+9·(-1) +5·1+7·(-1) = 3-9+5-7 = -8 ≡ 3 (11). Szavakba öntve: jobbról és pozitívval kezdve váltott előjellel összeadjuk a jegyeket, és amit az eredmény ad maradékul 11-gyel osztva, azt adja a szám is. Itt is igaz, hogy szorzat maradéka a maradékok szorzata, vagyis az eredményt felhasználhatjuk a szorzás helyességének tesztelésére. Ha ugyanis valahol elírtunk egy jegyet, az a szorzást modulo 11 is elrontja, s ezt a kisebb számok körében hamarabb észrevesszük.

Mindkét módszer bizonytalan a kétszeri hibák kijelzésében, ezek során ugyanis előfordulhat, hogy a modulo 9 (vagy modulo 11) vett maradék nem változik. Ha azonban egyszerre alkalmazzuk a két módszert, akkor a szorzásban ejtett hibák nagy valószínűséggel lelepleződnek.

2. A Z₆-os szorzótábla tényleg nem sokat mond, ezért érdemes felrajzolni más táblázatokat is. A 0-t kihagyjuk.

Z8 · 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 2 2 4 6 0 2 4 6 3 3 6 1 4 7 2 5 4 4 0 4 0 4 0 4 5 5 2 7 4 1 6 3 6 6 4 2 0 6 4 2 7 7 6 5 4 3 2 1

Z9 · 1 2 3 4 5 6 7 8 1 1 2 3 4 5 6 7 8 2 2 4 6 8 1 3 5 7 3 3 6 0 3 6 0 3 6 4 4 8 3 7 2 6 1 5 5 5 1 6 2 7 3 8 4 6 6 3 0 6 3 0 6 3 7 7 5 3 1 8 6 4 2 8 8 7 6 5 4 3 2 1

Z10 · 1 2 3 4 5 6 7 8 9 1 1 2 3 4 5 6 7 8 9 2 2 4 6 8 0 2 4 6 8 3 3 6 9 2 5 8 1 4 7 4 4 8 2 6 0 4 8 2 6 5 5 0 5 0 5 0 5 0 5 6 6 2 8 4 0 6 2 8 4 7 7 4 1 8 5 4 9 6 3 8 8 6 4 2 0 8 6 4 2 9 9 8 7 6 5 4 3 2 1

A "csúnyán" viselkedő elemek: Z₆-ban 2, 3 és 4; Z₈-ban 2, 4 és 6; Z₉-ben 3 és 6; végül Z₁₀-ben 2, 4, 5, 6 és 8. Ezekre az jellemző, hogy minden "gyanús" számnak van közös prímtényezője (azaz 1-nél nagyobb közös osztója) a modulussal. Azok pedig, amelyeknek nincs, szemlátomást "átrendezik" a számsort. Def: Az m modulusú teljes maradékrendszernek (Z_m) azokat az elemeit, amelyek (pozitív egészként tekintve) az m modulushoz relatív prímek, modulo m redukált maradékosztályoknak nevezzük. Noha ez igen félelmetesen hangzik, van egy szemléletes átfogalmazása, amelyre a most megsejtett tétel vezet rá bennünket.

Tétel: Ha a Z_m gyűrűben a k elem relatív prím az m modulushoz, akkor a k-val való szorzás (mint függvény) Z_met kölcsönösen egyértelmű módon viszi önmagába ("átrendezi").

Bizonyítás: Egy függvényt akkor nevezünk kölcsönösen egyértelműnek, ha különböző elemek képe sosem ugyanaz. Tegyük fel indirekt módon, hogy van két olyan elem Z_m-ben, amelyek nem egyenlők, de képük (azaz k-szorosuk) ugyanaz. Jelöljük őket a-val és b-vel. A k·a = k·b (mint Z_m-beli egyenlőség) kongruenciává alakítható: k·a ≡ k·b (modulo m). Ebben minden betűt egész számnak fogunk fel (és nem maradékosztálynak). Az 1./3. leckepélda segítségével ezt átfogalmazhatjuk oszthatósággá: m|k·a-k·b, azaz m|k·(a–b). Használhatjuk a számelméleti ismereteinket: mivel m, k és a–b prímtényezőkre bontható, akkor fog fennállni az oszthatóság, ha m minden prímtényezője megtalálható a jobb oldalon. No de k-t úgy vettük, hogy ne legyen m-mel közös osztója, így m összes prímtényezője kénytelen a–b-ben szerepelni. Ez azt jelenti, hogy m|a–b, ami kongruencianyelven így szól: a ≡ b (m). Ha most a és b újra maradékosztállyá változik, kapjuk, hogy ők mint Z_m-beli elemek egyenlőek. Ez azonban ellentmond az indirekt feltevésnek. Ezzel a tételt beláttuk.

Meg lehet mutatni, hogy ha m-nek és k-nak van közös osztója, akkor a k-val való szorzás "ismételni" fogja a számsor egy részét, azaz lesz két különböző elem, amelynek ugyanaz a k-szorosa. Bizonyítás helyett egy példát mutatunk, amely minden lényeges dolgot tartalmaz. Legyen m = 30, k = 25. Megkeressük az LNKO-t (5), és elosztjuk vele a 30-at: 6. Ha két egész szám különbsége 6, akkor modulo 30 nem egyenlőek, de 25-szöröseik egymástól 25·6 = 150 távolságra lesznek, azaz egyenlők modulo 30. Mindez nem működik, ha pl. k = 13-at veszünk. Szemléletesen: a 13·a ≡ 13·b (30) kongruenciát "végigoszthatjuk" 13-mal (azaz következik belőle, hogy a ≡ b (30)), mert a 13 relatív prím a 30-hoz. A modulo m redukált maradékosztályok tehát pontosan azok, amelyekkel osztani lehet.

Megjegyzés: Ha a modulus prím, akkor a 0 kivételével mindegyik maradékosztály ilyen.

1. házi feladat: Ábrázold nyíldiagramon a Z₈-beli x→ 3·x függvényt, és egy másikon az x→ 6·x függvényt!

Megjegyzés: A modulo m redukált maradékosztályok számát φ(m)-mel jelöljük. A φ függvényt, amely minden m-hez ezt a számot rendeli, Euler-féle számelméleti függvénynek nevezzük.

A 3. "észrevételt" észrevétlenül be is bizonyítottuk, hiszen ha egy szorzás átrendezi a számsort, akkor egy valamihez hozzá fogja rendelni az 1-et is. Ez lesz a szorzószám (redukált maradékosztály!) reciproka. A Z₇-es és Z₆-os szorzótábla szerint 5-nek a hetes reciproka 3, hatos reciproka pedig önmaga. A 4/5 tört definíciója az lehetne, hogy "4·(1/5)," ez Z₇-ben 4·3 ≡ 5, illetve Z₆-ban 4·5 ≡ 2. Mindezek a szorzótáblából is visszakereshetők.

Az 1/2-del más a helyzet. Z₇ táblája szerint 2·4 ≡ 1, azaz 1/2 = 4. Viszont a Z₆-os szorzótábla 2-höz tartozó sorában hiába keresünk 1-est. Z₆-ban létezik 0/2, 2/2, 4/2 tört (és mindegyiknek két értéke van, ami sérti az ízlésünket), de 1/2 egy sincs! Általánosan is bebizonyítható, hogy ha k-nak és m-nek van közös osztója, akkor k-nak nincs reciproka modulo m. Ismét egy példát veszünk: legyen m = 15, k = 6. LNKO-juk 3, ezért k-nak akárhányszorosa (mint egész szám) is osztható lesz 3-mal, tehát 15-tel osztva 0, 3, 6, 9 vagy 12 maradékot kell adnia. Ahhoz pedig, hogy k-nak legyen reciproka modulo 15, az kell, hogy valamelyik többszörös 1-et adjon maradékul.

4. Most már igen könnyű lesz felelni erre a kérdésre is. A nullák csakis azoknak az elemeknek a soraiban jelentkeznek, amelyeknek van közös osztójuk a modulussal. (A 0-val való szorzástól eltekintünk, ez ún. triviális eset, azaz túl egyszerű, semmitmondó.) Vegyük példának Z₉-ben 6-ot. Ezt 3-mal vagy 6-tal kell szorozni, hogy 9-cel osztható legyen. Ezért vannak ezeken a helyeken nullák. Z₈-ban pedig 4-nek egyenesen három ilyen "nullosztó"-párja van: 2, 4 és 6 – ezek tartalmaznak még egy kettes prímtényezőt a 8-cal való oszthatósághoz.

2. házi feladat: Az "Ecc-pecc, kimehetsz" kezdetű kiszámoló hivatalos, legrövidebb változata (amely "Fuss!"-ra végződik) 17 ütemegységből áll. Vajon miért kell eltérni a ritmikailag kétségkívül jobb 16-tól? Lehetséges-e, hogy a kiszámoló (esetleg sokszori) elmondása után arra esik a választás, akin a számolást elkezdtük? Ha a társaság kevés emberből áll (pl. 6), akkor hány ütemre rövidíthető az Ecc-pecc? Vajon így is "igazságos" lesz?

Feladat: Móricka rossz fát tett a tűzre, ezért most büntetésből fogalmazást kell írnia egy lepedőnyi papírlapra. Apja, aki foglalkozására nézve matektanár, a következő feltételeket szabta neki:

A szavaknak sorrendben az ábécé megfelelő betűjével kell kezdődniük (zs után a jön).

Minden sorban ugyanannyi szónak kell lennie. Ez a szám legalább tíz és legfeljebb húsz kell, hogy legyen.

Akkor van vége a körmölésnek, ha egy sor éppen az ábécé utolsó betűjével kezdődő szóval zárul.

Az ábécé 27 betűje: a-á, b, c, cs, d, e-é, f, g-gy, h, i-í, j, k, l-ly, m, n-ny, o-ó, ö-ő, p, r, s, sz, t-ty, u-ú, ü-ű, v, z, zs. Adjunk tanácsot Mórickának, hogyan úszhatja meg a dolgot a legkevesebb szenvedéssel!

Megoldás: Jelöljük a leírandó sorok számát s-sel, az egy sorban lévő szavak számát n-nel! Kell, hogy 27|n·s, és hogy a leírandó szavak n·s száma a lehető legkisebb legyen. Vegyük sorra n megengedett értékeit, és állítsuk elő mindegyikhez a legkisebb s-et!

n	10	11	12	13	14	15	16	17	18	19	20
s	27	27	9	27	27	9	27	27	3	27	27
n·s	270	297	108	351	378	135	432	459	54	513	540

Szembetűnő, hogy a legkedvezőbb eredményt akkor kaptuk, amikor az n paraméter ("állítgatható szám") a 27-nek minél több prímtényezőjét tartalmazta. A kongruenciák nyelvén megfogalmazva: az n·s ≡ 0 (27)-nek akkor lesz igen sok s megoldása (és köztük egy olyan s, amely pozitív egészként tekintve "kicsi"), ha az n paraméter és 27 minél több prímtényezőben egyezik. Tudjuk: ha n és 27 relatív prím, akkor az n·s ≡ 0 (27) kongruenciát csak az s ≡ 0 ≡ 27 triviális megoldás elégíti ki (27 sor). Tehát a redukált maradékosztályok nem mindig "szépek."

Az édesapát ez az 54 szó nem hatotta meg, ezért amikor Móricka újabb csínytettet követett el, annyiban megváltoztatta a feltételeket, hogy az első szót a lap tetejére kell írni cím gyanánt, utána a b-betűvel kezdődhet az első sor. Minden más szabály ugyanaz. Segítsünk a lurkónak!

A különbség a kongruencián kitűnően előjön: lesz n·s szó a szövegben és egy a címben; összegük osztható 27-tel. Ezt átfogalmazva: n·s+1 ≡ 0 (27), átrendezve n·s ≡ -1 (27). Ez így "felbonthatatlan," de a -1-et modulo 27 ki lehet cserélni vele kongruens számra: n·s ≡ 26 (27). Jé, ez már felbontható, n = 13, s = 2, azaz 27 szó! Úgy látszik, a találékony apuka nem figyelt valamire. Nosza, bezárkózott, osztott-szorzott, majd az új szabályokat is módosította, hogy legközelebb ne érhesse meglepetés: az ábécé 24 betűs lesz (c-cs, s-sz, z-zs)! 3. házi feladat: Mit tegyünk, ha Móricka ismét kikap?

4. A házi feladatok megoldásai

1.

2. Egy m tagú társaság modellje legyen a Z_m gyűrű, és kezdjük az 1. számú emberről a számolást. Ha többször is elmondjuk a kiszámolót (ha pl. több embert is ki akarunk választani), akkor modulo m adogatjuk önmagához a 17-et. Ez voltaképpen a 17·1, 17·2, 17·3,... elemek sorát adja, amely úgy esztétikus, hogyha nincs benne ismétlődés. A 17 prímszám, vagyis saját többszörösein kívül minden egész számhoz relatív prím. Emiatt a 17-tel nem osztható modulusú gyűrűket átrendezi, míg például a 16 ütemű kiszámoló bármely páros létszámú társaságnak kihagyná bizonyos tagjait (köztük az elsőt), míg másokat többször is sorra kerítene.

Itt merül fel eddigi anyagunk legmélyebb kérdése. Ha egy hat fős társaság a 17 ≡ 11 ≡ 5 (6) kongruencia alapján bevezetné a 11 vagy az 5 ütemből álló kiszámolót, akkor ezek is igazságosak lennének, mert mind a 11, mind az 5 relatív prímek a modulushoz, csakúgy, mint a 17. Nem lehetséges-e azonban, hogy valamely modulusra az egymással kongruens egész számok egyike relatív prím a modulushoz, a másik nem? Ezen tudniillik igen sok múlik: a redukált maradékosztály egész definíciója megdől, ha mégis így áll a dolog. Ugyanaz a maradékosztály redukált lenne az egyik képviselője (szakszóval: reprezentánsa) miatt, és "csúnya" volna a másik miatt.

A következő kis tétel megnyugtatóan rendezi a kérdést. Eszerint az egyazon maradékosztályba tartozó összes egész számnak a modulussal vett LNKO-ja ugyanaz a szám.

Bizonyítás: Legyen Z_m egyik maradékosztálya k, amely jelölje egyszersmind ennek az osztálynak egyik tagját is. Legyen LNKO(k,m) = d: ez az a legnagyobb "tégla," amelyből mindkettő kirakható. Mivel d|m, d-vel bármely másik k' reprezentáns is osztható, mert a köztük lévő távolság is "kitéglázható." Mivel d közös osztója m-nek és k'-nek, ezek LNKO-ja (d') többszöröse lesz neki. Ez a gondolatmenet fordított irányban is eljátszható, azaz beláttuk, hogy d és d' kölcsönösen osztói egymásnak. A pozitív egészek körében ez csak akkor lehetséges, ha egyenlők.

3. Meg kell oldani az n·s ≡ -1 (24) kongruenciát úgy, hogy 10 ≤ n ≤ 20, és hogy n·s a lehető legkisebb legyen. A szokásos próbálgatásos módszerrel igyekszünk szorzattá alakítani "-1-et," azazhogy ennek a maradékosztálynak a reprezentánsait. Először lefelé indulunk el, és ügyelünk n korlátaira:

n·s ≡ -1 ≡ -25 = 5·(-5) ≡ 5·19. Csak n lehet a 19, így a leírandó szavak száma e változatban 5·19+1 = 96.

n·s ≡ -49 = 7·(-7) ≡ 7·17. Itt n = 17, a szavak száma 7·17+1 = 120. Most felfelé lépdelünk:

n·s ≡ -1≡ 23 ≡ 47 ≡ 71 ≡ 95 (már volt*) ≡ 119 (*) ≡ 143 = 13·11. Mindkettő lehet az n, és a szószám 144.

Ha tovább keresgélünk, csak olyan összetett számokat kapunk, amelyeknek a feladathoz illő tényezői a 11, 13, 17 vagy 19 számokkal kongruensek modulo 24 – és Mórickának legalább 96 szavas fogalmazást kell kiizzadnia. Honnan tudhatjuk, hogy nincs más megoldás? Onnan, hogy a 10 és 20 közti tartományban éppen ezek az n paraméterértékek lesznek 24-hez relatív prímek. Más n'-kre nem lehet n'·s' ≡ -1 (24), mert ekkor egy előjelváltással azt kapnánk, hogy a "csúnya" n'-nek van 24 szerinti reciproka: –s'. Megjegyzés: Ezt a fáradságot csak úgy lehet megtakarítani, ha elkészítjük a 24-es szorzótábla n = 11; 13; 17; 19 elemekhez tartozó sorait, és megkeressük, milyen s tartozik a –1 ≡ 23 táblázatelemhez.

1. házi feladat: Írjunk számítógépes programot, amely rögzített (esetleg tetszőleges beadott) modulusú gyűrűnek elkészíti a szorzótábláját! Az osztási maradékot BASIC-ben az egészrészfüggvénnyel, PASCAL-ban ezen kívül az "a div b" maradékos osztással állíthatjuk elő. Írjunk egy másik programot, amely "eloszt" két számot!

2. házi feladat: Gondolkodjunk el azon, hogyan lehetséges az iménti 3.c házi feladatban, hogy 24-esével lépdelve hol prímszámot, hot összetett számot kapunk! Nem mond ez ellent a mai tételnek? Van-e értelme egy Z_m-beli elem prímtényezős felbontásáról beszélni? Próbáljuk hatványozni Z_m elemeit: milyen logikát követnek?

5. Hatványozás Z_m-ben

Először jöjjenek a házi feladatok megoldásai

1..

Szorzótáblát készítő program

INPUT "modulus"; m
FOR i = 1 TO m - 1
FOR j = 1 TO m - 1
szorzat = i * j
maradek = szorzat - m * INT(szorzat / m) 
LOCATE i + 1, 3 * j: PRINT maradek
NEXT j
NEXT i

Reciprokkereső program

INPUT "modulus"; m
INPUT "Minek akarod a reciprokat"; g
FOR h = 1 TO m - 1
hanyados = (g * h - 1) / m
IF INT(hanyados) = hanyados THEN PRINT g; " reciproka modulo "; m; ": "; h: END
NEXT h
PRINT "A "; g; " elemnek nincs reciproka modulo "; m; "."

Osztóprogram

INPUT "modulus"; m
INPUT "Mit akarsz elosztani"; k
INPUT "Mivel"; l
FOR h = 0 TO m - 1
hanyados = (l * h - k) / m
IF INT(hanyados) = hanyados THEN PRINT k; "/"; l; " modulo "; m; ": "; h: t = 1
NEXT h
IF t = 0 THEN PRINT "A "; k; "/"; l; " tort nem letezik modulo "; m; "."

2. Tényleg meglepőnek tűnik a dolog, mivel épp most bizonyítottuk be, hogy egy maradékosztálynak vagy minden eleme "szép," vagy mindegyik "csúnya." Ennek azonban nem mond ellent, hogy a "szépek" közt legyenek prímek és összetett számok – csak egyiknek se legyen a modulussal közös osztója. A "csúnyákat" pedig az a tulajdonság fogja összetartani, hogy mindnek ugyanaz az LNKO-ja m-mel. Viszont ez a tapasztalat teljesen értelmetlenné teszi a prímtényezős felbontás fogalmát modulo m, mert ugyanabba a maradékosztályba teljesen különböző számelméleti tulajdonságú elemek tartoznak. A felbontás nem lesz egyértelmű. Valamilyen ésszerűséget azonban meg lehet állapítani.

Tétel: Egy modulo m redukált maradékosztály csak redukált maradékosztályok szorzatára bontható. Nem redukált maradékosztályok bármilyen szorzattá bontásában lesz nem redukált maradékosztály.

Bizonyítás: Ha a szereplő maradékosztályokat egész számoknak tekintjük, akkor alkalmazhatjuk számelméleti tudásunkat. A szorzatnak a modulussal vett minden esetleges közös osztója a szorzat valamelyik tényezőjétől származik; ha pedig a szorzat relatív prím a modulushoz, akkor a tényezők is.

A hatványozás igen érdekes művelet modulo m. Néhány elem hatványozási sora ("mértani sorozat") :

Modulo 7: 0 → 0 1 → 1 2 → 4 → 1 3 → 2 → 6 → 4 → 5 → 1 4 → 2 → 1 5 → 4 → 6 → 2 → 3 → 1 6 → 1

Modulo 8: 0 → 0 1 → 1 2 → 4 → 0 3 → 1 4 → 0, 5 → 1 → 5 6 → 4 → 0 7 → 1

Modulo 9: 0 → 0 1 → 1 2 → 4 → 8 → 7 → 5 → 1 3 → 0 4 → 7 → 1 5 → 7 → 8 → 4 → 2 → 1 6 → 0 7 → 4 → 1 8 → 1

Látszik, hogy a sorozat vagy 0-kba fullad, vagy szakaszosan ismétli önmagát. A szakaszok vagy körök elemszáma változó, és még redukált maradékosztály hatványozásakor sem biztos, hogy végigmegyünk az összes redukált maradékosztályon. Def: A k elem (modulo m értett) rendjének nevezzük azt a legkisebb r pozitív egész számot, amelyre igaz, hogy k^r ≡ 1 (m), ahol ilyen kitevő létezik. Bebizonyítható (de nem tesszük meg), hogy minden redukált maradékosztálynak van rendje, és hogy ez osztója az összes redukált maradékosztályok számának (amit φ(m)-mel jelölünk). Azaz minden redukált maradékosztály φ(m)-edik hatványa 1.

A leghasznosabbak a 10 (ill. a neki megfelelő maradékosztály) hatványai: ezekkel ugyanis oszthatósági szabályokat lehet adni valamely szám 10-es számrendszerbeli alakjához. Pl. modulo 3 10 minden hatványa 1-gyel kongruens, amiből következik, hogy pl. 7453 ≡ 7+4+5+3 ≡ 0 (3). A hármas oszthatósági szabály tehát az, hogy össze kell adni a jegyeket. Ugyanez igaz 9-re is, mert 10 hatványai modulo 9 is 1-gyel kongruensek.

Próbáljunk meg m = 7-re oszthatósági szabályt adni! 10 ≡ 3 (7), és ennek hatványai rendre 1,3,2,6,4,5,1..., ill. ha modulo 7 kicseréljük a túl nagyokat könnyebben kezelhető negatív reprezentánsokra: 1,3,2,-1,-3,-2,1... Ezzel pl. 6675921 ≡ 1·1+2·3+9·2+5·(-1)+7·(-3)+6·(-2)+6·1 = -7 ≡ 0 (7), vagyis a szám 7-tel osztható. A jegyeket jobbról indulva az 1,3,2,-1,-3,-2,1... számokkal szorozva összeadjuk, és ha az így kapott számban megvan a 7, akkor az eredetiben is. (Sőt, az is igaz, hogy az eredeti szám 7-es osztási maradéka megegyezik a kapottéval.) A számolás egyszerűsítése érdekében megtehetjük, hogy a vizsgálandó szám jegyeit azok hetes maradékával helyettesítjük, azaz az iménti 6675921 helyett 6605221-et írunk.

Megjegyzés: mivel az oszthatósági sor hattagú, de hármasával előjelet vált, minden olyan hatjegyű szám, amelynek jegyei hármasával ismétlődnek (pl. 956956 vagy 001001) osztható lesz 7-tel. Ezen alapul a 7-tel való oszthatóságnak egy könnyebb szabálya: ha a szám legalább négy-, öt- vagy hatjegyű, akkor az utolsó három jegye által alkotott számból vonjuk ki az előtte lévő jegyek alkotta számot. Ha (az akár negatív) különbség osztható 7-tel, akkor a szám is, ha pedig nem, akkor az sem. Megjegyzés: a 956956 típusú számok 13-mal is oszthatók, ezért rájuk is érvényes a 7-re adott szabály.

11-es oszthatósági szabály: 10 ≡ -1 (11), 100 ≡ 1 (11), tehát hatványozási sora -1, 1, -1, 1... Vagyis ha a jegyeket jobbról +1-gyel kezdve váltott előjellel összeadjuk, és a kapott szám 11-gyel osztható, akkor az eredeti is.

Oszthatósági szabály 13-ra: 1 ≡ 1 (13), 10 ≡ -3 (13), 100 ≡ -4 (13), 1000 ≡ -1 (13), 10000 ≡ 3 (13), 100000 ≡ 4 (13), s utána ismét 1 jön. Az oszthatósági sor hattagú, és előjelváltásos ismétlődés van benne. A szám jegyeit tehát jobbról balra haladva a fenti számsor elemeivel szorozva kell összeadni, s ha ez még mindig túl nagy, akkor az eljárást ismételni lehet.

Minden "valamirevaló" prímszámra (10-es számrendszerben ez a 2-n és az 5-ön kívül az összes prímet jelenti) adható oszthatósági sor, és így oszthatósági szabály is. Ez azonban a legtöbb esetben igen hosszú (elemszáma φ(m) valamelyik osztójával egyenlő), és gyakorlati alkalmazásra nem ajánlható. Az érdekesség kedvéért megemlítjük még, hogy a 101-nek négyelemű (és előjelváltó) oszthatósági sora van: 1, 10, -1, -10. Itt tehát váltott előjellel kell összeadni jobbról indulva a kétjegyű tagokat, s ha ez osztható 101-gyel, akkor maga a szám is.

---

6. Kártyakeverés

Utolsónak még egy érdekes alkalmazást tekinthetünk, amely gyakran felmerül a kártyások körében. Sokszor mondják, hogy az "összefésülős" keverés (amellett, hogy rongálja a lapok sarkait) nem elég hatékony, mert néhány keverés alatt esetleg az eredeti sorrend is visszaállhat. Vizsgáljuk meg ezt az állítást, mert amilyen meglepő, olyan kevesen hisznek benne.

Vegyünk egy kártyapaklit, amiben páros számú lap van, és keverjük meg az összefésülős módszerrel. Ennek lényege, hogy megfelezzük a csomagot, majd a jobb félen lévőket becsúsztatjuk a bal oldaliak közé úgy, hogy a bal szélső elé is új lap kerüljön. Ezt a módszert egy idealizált eseten keresztül mutatjuk be, amelyben valóban fésűszerűen illeszkednek össze a lapok. (A valóságban szerencsére nem így szokott lenni.)

Álljon a pakli tíz számozott lapból. (Állhatna 32-ből is, de a logika ugyanez volna.) Az összefésülés itt úgy fog hatni a lapokra, amint az az ábrán látszik. A hatodik az első elé, a tizedik az ötödik elé kerül.

A lapok sorrendje néhány keverés után:

0.	1	2	3	4	5	6	7	8	9	10
1.	6	1	7	2	8	3	9	4	10	5
2.	3	6	9	1	4	7	10	2	5	8
3.	7	3	10	6	2	9	5	1	8	4
4.	9	7	5	3	1	10	8	6	4	2
5.	10	9	8	7	6	5	4	3	2	1

A lapok sorrendje 5 keverés után éppen megfordult az eredetihez képest!

6.	5	10	4	9	3	8	2	7	1	6
7.	8	5	2	10	7	4	1	9	6	3
8.	4	8	1	5	9	2	6	10	3	7
9.	2	4	6	8	10	1	3	5	7	9
10.	1	2	3	4	5	6	7	8	9	10

Tíz keverés után pedig visszaáll az eredeti sorrend!

Minek köszönhető ez a rövidség? A józan ész azt sugallja, hogy mivel 10 kártyát irdatlanul sokféleképpen lehet sorbarakni, csak igen sokára állhat elő még egyszer a kezdeti sorrend.

Nézzük meg az ábrát még egyszer. Az első keverés után a kis sorszámú lapok a saját sorszámuk kétszeresével jelölt helyre vándoroltak, a nagy sorszámúakra azonban ez nem igaz. Viszont jobbról nézve ők is ugyanúgy mozdultak el, mint bal oldali társaik. Miért ne lehetne őket jobbról indulva megszámozni, ezúttal a negatív számokkal? Ez esetben az ő sorszámuk is a kétszeresére változik a keverés után ... ha a jobbról számozott –10-edik hely egybeesik a balról számozott elsővel, a –9-edik hely a másodikkal, és így tovább. Ennek érdekében a sorszámokat tekintsük úgy, mint egy olyan maradékosztály tagjait, amelyben –1 ≡ 10, –9 ≡ 2 stb. Ez a Z₁₁ gyűrű.

Kövessük most az első lap vándorútját a táblázatban. A sorszámokat alakítsuk át modulo 11, ha szükséges.

1 → 2 → 4 → 8 → "16"≡5 → 10 → "20"≡9 → "18"≡7 → "14"≡3 → 6 → 12≡1

Hasonló utat tesz meg pl. a 7. lap is (minden lépésben megkétszereződik modulo 11), így már nem meglepő, hogy a tizedik keverés után visszatér oda, ahonnan elindult:

7 → 14≡3 → 6 → 12≡1 → 2 → 4 → 8 → 16≡5 → 10 → 9 → 18≡7

Ezek szerint mindegyik kártya ugyanazon a körpályán halad végig, és ugyanannyi lépésben ér vissza.

A következő kérdés nyilván az, hogy más kártyapaklik esetén hány keverés után áll vissza az eredeti elrendeződés. (Kártyatrükkhöz ugyan ez a keverés – éppen pontatlansága miatt – nem alkalmazható, de egy hozzá hasonlót Monge francia matematikus már kétszáz éve sikerrel alkalmazott.)

Az elmélet a különféle paklikra igen változatos eredményt ad. Pirossal jelöltük az olyan keveréssorozatokat, amelyekben a 10-eshez hasonlóan először megfordul a sorrend.

Elemszám	2	4	6	8	10	12	14	16	18	20	22	24	26	28	30	32	34	36	38	40	42	44	46	48	50
Keverésszám	2	4	3	6	10	12	4	8	18	6	11	20	18	28	5	10	12	36	12	20	14	12	23	21	8

Célszerű itt általánosan megfogalmazni a kérdést. Ha egy 2n lapból álló paklit keverünk, akkor arra kell felelnünk, hogy az első lap hány lépésben ér vissza, azaz 2-nek hányadik hatványa 1 – mégpedig a modulo (2n+1) gyűrűben. Ezt a számot, a keverések számát úgy nevezzük: 2 rendje modulo (2n+1).

Erről a számról korábban bizonyítás nélkül kimondtuk, hogy φ(2n+1) valamelyik osztójával egyenlő. Emlékeztető: φ(2n+1) azon 1 és 2n+1 közti egészek száma, amelyeknek relatív prímek 2n+1-hez. Gondoljuk meg, hogy ezek száma legfeljebb 2n.

Mikor lesz a szükséges keverésszám kicsi, és mikor nagy? A második kérdésre válaszolunk előbb. Olyan n-et kell keresni, amelyre φ(2n+1) éppen 2n-nel lesz egyenlő, magyarul olyan számot, amely az összes, nála kisebb számhoz relatív prím. Ez akkor van így, ha 2n+1 maga is prím.

És valóban, ha pl. 2n = 10, 18, 28 vagy 36, akkor 2n+1 prímszám, és nincs más lehetőség, mint hogy ennyiszer megkeverjük a paklit, míg visszaáll.

No és mikor lesz a szükséges keverésszám kicsi? A táblázat alapján 2n = 14, 20 és 30 ilyen, de ennek alapján nehéz lenne megállapítani bármiféle szabályt. Viszont nyilván azok a 2n-ek lesznek jók, amelyekben az első kártya "egy lendülettel" (csak "növekedve") jut el a 2n+2-edik (azaz az első) helyre. Tehát az a kedvező eset, ha 2n+2 (egész számként tekintve) 2-hatvány. Az olyan elemszámú paklik rendeződnek vissza gyorsan, amelyek egy 2-hatványnál 2-vel kisebbek.

Hasonlóan meg lehet mutatni, hogy ha 2n éppen 2-hatvány, akkor az előbbi esethez tartozó keverésszám esetén éppen megfordul a sorrend. Ugyanis az 1-es ilyenkor a 2n. helyre jut el "egy lendülettel," és ez éppen az utolsó hely, mert –1-gyel kongruens modulo (2n+1). Pl. ha 2n = 32, akkor öt lépésben fordul meg a sorrend, és további öt keverés után visszaáll. Vagyis a 32 lapos magyar kártyát nem érdemes ötször megkeverni...

Annak pontos meghatározása, hogy mennyi 2 rendje modulo (2n+1), magasabb ismereteket igényel. Most tehát meg kell elégednünk e néhány speciális eset vizsgálatával.