Additív rend

A Wikipédiából, a szabad enciklopédiából

Az additív rend fogalmával a matematikában elsősorban a számelmélet és az algebra foglalkozik.

Legyen adott egy m ∈ ℤ egész szám. Egy egész szám (vagy mod(m) maradékosztály) modulo m vagy röviden mod(m) additív rendje az a legkisebb nemnegatív egész szám, mellyel a számot (vagy maradékosztályt) megszorozva, m-mel osztható számot kapunk; vagyis 0-val kongruens számot modulo m. Ugyanez a definíció elmondható maradékosztályokra is: a kettő, más megfogalmazásban, lényegében ugyanaz. A formális definíció egész számokra illetve maradékosztályokra vonatkozó változatai is olvashatóak e cikkben.

A könnyebb érthetőség kedvéért mondjunk egy példát. Mondjuk két óceánjáró hajó, a „Missou Mary” 5 hónaponként, a „Mama Leone” pedig 6 hónaponként köt ki ugyanabban a kikötőben. Ha egy adott hónapban mindketten a kikötőben voltak, kérdés, hogy mennyi idő múlva találkoznak újra?

  • Egy lehetséges és elemi megoldás, hogy a visszatérési periódusok legkisebb közös többszörösét, azaz [5,6]=30-at kell venni, tehát 2 év és 6 hónap múlva.
  • E mögött az van, hogy addig kell többszöröznünk az egyik számot, mondjuk a hatot, míg a másikkal, 5-tel osztható szorzatot nem kapunk. Az első ilyen többszörös szolgáltatja a megoldást. Azaz 6, 2×6=6+6=12, 3×6=6+6+6=18, 4×6=24 nem megoldások, de a legkisebb ilyen többszörös, 5×6=30 már igen, mert osztható öttel. Tehát úgy is megoldhatjuk a feladatot, ha a 6-nak a mod(5) additív rendjét számoljuk ki, majd azzal megszorozzuk. Persze fordítva is gondolkodhatunk: kiszámoljuk 5 mod(6) rendjét (6), és a két számot összeszorozzuk. Mindkét eljárás tényleg a legkisebb közös többszörös kiszámítását jelenti, hisz az additív rend definíciója miatt a szám és mod(m) rendje szorzata a legkisebb olyan szám, melynek mindkét szám (a szám és modulusa) osztója, tehát épp a szám és modulusa legkisebb közös többszöröse.

Az egész számokra és maradékosztályokra értelmezett „additív rend” kifejezést még a következő értelemben is használjuk: adott egy R = (U,+,×) gyűrű. Ekkor az a∈U elem (U,+) additív csoportbeli rendjét nevezzük az a ∈ U elem additív rendjének, és ezt, ahogyan az egész számokra értelmezett additív rendet is o{+}(a)-val jelöljük (esetleg, hogy megkülönböztessük a két fogalmat, -val).

Az egészek számokra és maradékosztályokra értelmezett additív rend tulajdonképp az utóbbi fogalom speciális esete (tehát ez ad jogot az azonos jelölésmód alkalmazására is), minthogy (ℤ,+,×) és (ℤm,+,×) is gyűrűk: egy egész szám vagy mod(m) maradékosztály additív rendje annak a (ℤm,+) csoportbeli rendje. Az általánosabb, gyűrűben értelmezett additív rendfogalom gyakorlatilag a csoportelméletben értelmezett rendfogalom alkalmazása egy speciális helyzetben (ezt az indokolja, hogy tekinthető az (U,×) multiplikatív félcsoportra vonatkozó rend is, tehát „additív” és „multiplikatív” rend is létezik, mert kétféle csoporttal vagy félcsoporttal is dolgunk van gyűrűk esetében), ezért a rend cikkben foglalkozunk velük általánosabban (ezeken kívül a (moduláris) számelméletben a csoportelmélettől függetlenül is definiálható a multiplikatív rend ).

Értelmezés az egészek körében[szerkesztés]

Definíció egész számokra[szerkesztés]

Legyenek egész számok, ekkor additív rendje mod(m) az természetes szám (két, egyenértékű definíciót is megadtunk).

Belátható, hogy a>1 esetén az additív rend az a∈ℤ egész szám vagy maradékosztály többszörösei sorozatának mod(m) maradékainak (minimális) periódusa. Ez azon a tételen alapul, pontosabban ezt az a tétel fogalmazza meg még precízebb formában, hogy az a két többszöröse akkor és csak akkor egyenlő, ha a fenti sorozatban az indexeik, azaz a többszörözőik kongruensek mod(m). Ezt bővebben a rend c. szócikkben tárgyaljuk, mert egy csoportelméleti tétel speciális esete. Az idézett tétel bizonyítása lentebb megtalálható.

Egyértelmű létezése[szerkesztés]

Könnyen látható, hogy ilyen pozitív egész szám általában létezik,

  • hiszen ha m>0, akkor biztos, hogy , mivel , ezért az halmaz nem üres (0 <m ∈ A), és így a természetes számok jólrendezettsége miatt létezik minimuma, ami jólrendezett struktúrákban ráadásul biztosan egyértelmű. Ha m<0, akkor ugyanez a gondolatmenet alkalmazható, csak m helyett -m-mel. Ezért: tetszőleges egész számnak tetszőleges nem nulla egész modulusra nézve létezik additív rendje.
  • ha m = 0, akkor is biztosan teljesül, csakhogy ekkor az m szám nem pozitív egész, tehát az A halmaz mégis csak üres lehet; ha ezen kívül nincs más e; és általában üres is. Ugyanis m=0|ei azt jelenti, hogy található olyan d egész szám, melyre ei = d×0 = 0, tehát hogy e = m = 0 vagy i = 0. Azaz, csak az i = 0 -ra nem üres az halmaz, de egyébként az egyetlen eleme e = 0 lenne csak (ami nem lehet eleme, kizártuk az e = 0 esetet az kifejezéssel A definíciójában).

Tehát m = 0 -ra csak i = 0 -nak létezik additív rendje, de egyébként nemnegatív i-re és pozitív m-re a rend létezik és egyértelmű. Lentebb belátjuk, hogy tetszőleges, akár negatív i és m egészekre (m=0 kivételével) is egyértelműen létezik a rend.

Kiterjesztett definíciók[szerkesztés]

Nulla modulusra[szerkesztés]

Kiterjeszthetjük ezért a rend definícióját így (ahogy az csoportokban is szokásos): , vagyis ha az i-t szorozva m-mel osztható szorzatot adó szorzók halmaza nem üres, akkor a rend e halmaz minimuma, és 0, ha e halmaz üres. E kiterjesztésben .

Egy másik lehetséges kiterjesztésben  :

Az előzőekben elmondottak szerint a következő definíció is ugyanezt jelenti:

Negatív számokra[szerkesztés]

Negatív egészekre és modulusra is kiterjeszthető a definíció; ugyanis egy negatív szám épp akkor osztható egy számmal, mikor pozitív ellentettje, tehát tetszőleges egészekre

Kiszámítása[szerkesztés]

A cikk elején lévő példa alapján sejthető. Ez általában is igaz. Egy szám additív rendjét tehát a következőképp számolhatjuk ki:

 ;

vagyis az m modulust osztjuk a modulus és a szám legnagyobb közös osztójával. Az utóbbi kiszámítási mód nemcsak gazdaságosabb, mivel a legnagyobb közös osztó kisebb és könnyebben számolható, mint a legkisebb közös többszörös, hanem még i = 0-ra is működik, a 0 additív rendje eszerint minden nem nulla modulusra 1.

Bizonyítás (vázolva): A rend definíció szerint a legkisebb olyan természetes szám, mellyel az adott számot szorozva, a modulussal osztható szorzatot kapunk. Ez a szorzat tehát a legkisebb olyan természetes szám, mely a modulusnak is, és az adott számnak is többszöröse – ez pedig épp az adott szám és a modulus legkisebb közös többszörösének definíciója. Felhasználva, hogy tetszőleges i,m egészekre , a második egyenlőség is adódik.

Táblázat[szerkesztés]

Az additív rend kis egész számokra a következőképp alakul:

↓m,i→ 0    1 2 3 4 5 6 7 8 9 10 11 12 13
0 1 0/∞ 0/∞ 0/∞ 0/∞ 0/∞ 0/∞ 0/∞ 0/∞ 0/∞ 0/∞ 0/∞ 0/∞ 0/∞
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 2 1 2 1 5 1 2 1 2 1 2 1 2
3 1 3 3 1 3 3 1 3 3 1 3 3 1 3
4 1 4 2 4 1 4 2 4 1 4 2 4 1 4
5 1 5 5 5 5 1 5 5 5 5 1 5 5 5
6 1 6 3 2 3 6 1 6 3 2 3 6 1 6
7 1 7 7 7 7 7 7 1 7 7 7 7 7 7
8 1 8 4 8 2 8 4 8 1 8 4 8 2 8
9 1 9 9 3 9 9 3 9 9 1 9 9 3 9
10 1 10 5 10 5 2 5 10 5 10 1 10 5 10
11 1 11 11 11 11 11 11 11 11 11 11 1 11 11
12 1 12 6 4 3 12 2 12 3 4 6 12 1 12
  • Megjegyzések:
    • a 0/∞ jelölés nem 0 osztva végtelennel, hanem azt jelenti, hogy 0 modulusra nézve nem létezik additív rend, ezért önkényesen 0-nak, vagy (a /-jel ezt jelenti, nem osztást) ∞-nek definiáljuk. Mindkét definíciónak megvan a maga oka (ld. rend).
    • A fentebbiekkel összhangban a táblázat negatív egészekre is kiterjeszthető, a modulus is lehet negatív akár.

Az additív rend maradékosztály-tulajdonság[szerkesztés]

Észrevehetjük, és vegyük is észre, hogy minden sorban az sorozat periodikus. Mégpedig a (minimális) periódus éppenséggel az m modulus! Tehát ha i mod(m) rendje n, akkor i+m, i+2m,i+km rendje is n, a táblázatból sejthetően minden -re, de az utána következő megjegyzésből adódóan minden -re is! Ez tehát azt jelenti, hogy a rend maradékosztály-tulajdonság. Valóban így is van.

Tétel: Legyen m ≠ 0 egész szám. Ekkor mod(m) kongruens egész számok additív rendje egyezik: . Bizonyítás: Érvényes , mivel ha , s ekkor . Tehát i és j bármely (számmal vett) többszöröse egyszerre kongruens (vagy nem kongruens) mod(m), azaz az m-mel osztható szorzatot adó szorzóik halmaza megegyezik, és ekkor ennek minimuma, ami pont az additív rend, is megegyezik.

Értelmezés a maradékosztályok körében[szerkesztés]

A maradékosztályokról[szerkesztés]

A továbbhaladás előtt érdemes elolvasni a maradékosztály és a kongruencia szócikket.

Legyen ismét két egész szám, ekkor az m modulusra vagy maradékra nézve (röviden mod(m)) maradékosztálynak nevezzük az = . Pontosan az m-mel osztva i-vel azonos maradékot adó számok tartoznak az maradékosztályba (a maradékosztály elemeit a maradékosztály reprezentánsainak is nevezzük). Tehát két maradékosztály egyenlő akkor és csak akkor, ha valamely két elemük (azaz ha összes elemük) mod(m) kongruens.

Ha az m szám rögzített, röviden csak -t írunk. A maradékosztályok halmazát, mely osztályfelbontása -nek, jelöli. Minden m-re pontosan m darab maradékosztály van (az m=0-t kivéve, mert mod(0) maradékosztály végtelen sok van: minden egész szám külön osztályba tartozik), végtelen sok elemmel (kivéve m=0, minden mod(0) osztály egyelemű).

Maradékosztály additív rendje[szerkesztés]

Tekintsük a mod(m) maradékosztályokat az összeadás műveletével, mely additív és neutrális elemes Abel-csoport, tehát csoport. Ha , és m>0, akkor létezik, mégpedig egyértelműen olyan pozitív egész szám, hogy legyen.

  • I. bizonyítás: ezt tulajdonképp az előzőekben beláttuk. Legyen m>0, tetszőleges -re létezik, mint a legkisebb olyan e szám, melyre , azaz amelyre ahogy a fentebb beláttuk. Tehát egy osztály additív rendje pontosan a reprezentánsa(inak) additív rendje, utóbbiról meg már tudjuk, hogy létezik és pozitív, ha m>0. Ezzel kész is vagyunk .
    • Tehát az egy osztályba tartozó egészek rendje megegyezik. Fordítva azonban ez nem igaz: különböző maradékosztályoknak is lehet azonos az additív rendje. Például mod(6) , noha
    • A fenti bizonyítás nem működik m = 0-ra, hiszen már az egészek körében sem működött. Hasonlóan, mint ama szituációban, most is belátható, hogy a mod(0) maradékosztályoknak tényleg nincs is pozitív rendje. Ez esetben a rend-definíció hasonló kiterjesztéseit alkalmazzuk, mint az egészeknél.
  • II. bizonyítás (vázlatosan): Könnyű belátni, hogy véges csoport (ha m>0), és ebből is következik az állítás. Ugyanis ha egy elemet elkezdünk többszörözni: x, x+x=2x, x+x+x=3x, … stb., akkor lesz két olyan többszörös, hogy fx=ex legyen. Ha ilyenek nem lennének, azaz semelyik két többszörös nem lenne egyenlő, mindegyik különböző lenne, akkor végtelen sok különböző elem lenne e félcsoportban, de ez a végessége miatt lehetetlen. Tehát ilyen e,f létezik, és ekkor – itt használjuk fel, hogy csoportról van szó – fx-ex = (f-e)x = 0. Tehát az f-e ≠ 0 természetes szám megfelelő. QED .
    • Ez a bizonyítás sem működik a mod(0) esetre és csak erre, mert végtelen halmaz.

Tehát m ≠ 0 modulusra a rendet a következőképp definiálhatjuk:

Egyéb bizonyítások a létezésre és egyértelműségre[szerkesztés]

III. bizonyítás: Adott az osztály, oldjuk meg az kongruenciát (ha úgy tetszik, a egyenletet). E kongruenciák szabályos megoldása a következő: mindkét oldalt oszthatjuk i-vel, de a modulust -re kell változtatni. Tehát a megoldás az osztály. Ennek kell a legkisebb pozitív elemét venni, ez m=0 esetén ; nem pozitív (sőt i=0 esetén így nem is értelmezhető); de más esetben a nevező biztosan pozitív (0-nál nagyobb szám bármilyen egésszel vett legnagyobb közös osztója nem nulla ugyanis, hanem pozitív), és a számláló is az, tehát sejthető, hogy ez az elem . És valóban, ez pozitív számok hányadosa lévén pozitív, továbbá nála kisebb pozitív szám már nincs az osztályban: ugyanis ha lenne ennél kisebb pozitív d, akkor , innen a két elem különbsége nemnegatív, ráadásul m-mel osztható, azaz , ahol 0 ≠ k; azaz , ám a bal oldal legfeljebb m, míg a jobb oldal a k=0 és d=0 esetet kivéve nagyobb mint m. Tehát vagy k=0, azaz , vagy pedig d=0, holott feltettük, hogy pozitív. Így az állítást beláttuk.

Vannak olyan elemi (nem-algebrai szemléletű) művek, melyekben ez a bizonyítás található vázlatosan, holott látjuk, mennyivel egyszerűbb lehetőségek léteznek.

Kiterjesztett definíciók maradékosztályokra[szerkesztés]

A pozitív egész értékű rend definícióját kiterjeszthetjük mod(0) maradékosztályokra is, úgy, ahogy az egészek körében tettük, egyszerűen csak az kifejezés helyett irandó (tehát valamiképp jelezni kell, hogy maradékosztályokról van szó), és egészek kongruenciája helyett maradékosztályok egyenlősége. Például a legegyszerűbb, harmadik kiterjesztést közüljük maradékosztályokra helyesbítve, de az első kettőnél is hasonlóan lehetséges:

Fontosabb tulajdonságok[szerkesztés]

Közöljük az additív rend néhány fontos (az eddigieken túli) matematikai tulajdonságát, egész számokra fogalmazva. A maradékosztályokra való átfogalmazás nem olyan nehéz, csak számok helyett maradékosztályt és kongruencia helyett egyenlőségjelet kell írni (utóbbi a halmazon belüli egyenlőség).

  1. Ha , , és

Rövid indoklás:

  • 1. Egy kongruenciát i-vel egyszerűsíthetünk úgy, hogy a modulust osztjuk i-nek és a modulusnak a legnagyobb közös osztójával, a kapott hányados pedig, az egyszerűsített kongruencia modulusa, az előző szakasz szerint épp az i mod(m) rendje.
    • Ezek szerint: kongruenciát egy szorzóval egyszerűsítve az egyszerűsített kongruencia modulusa a szorzó eredeti modulus szerinti rendje.
  • 2. Az előző tulajdonsághoz teljesen hasonló: egyszerűsítünk i-vel úgy, hogy a modulust osztjuk (i, m)-mel, a kapott hányados – az egyszerűsített kongruencia modulusa – az i rendje mod(m); az egyszerűsített kongruencia szerint tehát j kongruens nullával mod ( o+m(i) ), ami épp azt jelenti, hogy osztható ezzel a renddel.
    • Ezek szerint szorzat akkor és csak akkor kongruens 0-val mod(m), ha bérmely tényezőjének mod(m) affitív rendje osztója a másik tényezőnek.
    • Ezt egy populárisabb (és maradékosztályokra is általánosítható) formában inkább úgy szoktuk megfogalmazni, hogy egy számot mod(m) eltüntető/lenullázó szorzók épp a mod(m) additív rend többszörösei; még rövidebben az additív rend osztója minden 0-t adó szorzónak (és csak ezeknek).
  • 3. Mivel o+m(i) (m,'i) = m, ha m ≠ 0; és (m,'i) egész, az oszthatóság definíciója szerint a rend osztója a modulusnak. Egyenlőség tényleg csak akkor van, ha (m,'i) = 1, azaz a modulus és a szám relatív prímek.
    • Maradékosztályokra vonatkozó, csoportelméleti tárgyalásban: a modulus egy 0-t adó többszöröző szám minden maradékosztályra, így a rend ennek osztója (ez egy egyszerű csoportelméleti tételből következik). tehát arról van szó, hogy mivel a modulus mindig az additív rend többszöröse, ezért a modulus egy 0-t adó szorzó (az előző pont szerint).
    • Csoportelméleti szemszögből ez a kijelentés úgy is interpretálható, hogy egy maradékosztály akkor és csak akkor generátoreleme a additív maradékosztály-csoportnak, ha redukált, azaz ha reprezentánsa(i) relatív prím(ek) a modulushoz.
  • 4. Mivel , tehát 3. szerint és , így .
    • Tehát összeg rendje osztója a rendek legkisebb közös többszörösének. Egyenlőség azonban nem mindig áll fönn: például , holott .
  • 5. Mivel és , szorozva az első kongruenciát j-vel, a másodikat i-vel, és , az első szerint i rendje, a második szerint j rendje „0-t adó többszörös” ij-re, tehát többszöröse ij rendjének: is teljesül, tehát ij rendje (közös) osztója mindkét rendnek, és ezért osztója a legnagyobb közös osztójuknak is.

Kapcsolódó szócikkek[szerkesztés]