Multiplikatív rend

A multiplikatív rend, rövidebben rend fogalmával a matematikában elsősorban a számelmélet és az algebra foglalkozik.

Legyen adott egy  pozitív egész szám. Egy másik adott (a) egész szám vagy maradékosztály modulo m vagy röviden mod(m) multiplikatív rendje az a legkisebb pozitív egész szám, melyre mint kitevőre az (a) számot emelve, 1-gyel kongruens számot kapunk modulo m. Azaz z-nek a mod(m) multiplikatív rendje az az r pozitív egész, amelyre mint hatványkitevőre z-t emelve zr 1 maradékot ad m-mel osztva, és ha zt is 1 maradékot ad, akkor r ≤ t.

Ugyanezek a definíciók elmondható maradékosztályokra is: a kettő, más megfogalmazásban, lényegében ugyanaz.

Megjegyzés: létezik additív rend is. Rendnek rövidebben a bonyolultabb (például nehezebben számolható), és fontosabb alkalmazásokkal bíró multiplikatív rendet nevezzük.

Az itt tárgyalt, egész számokra és maradékosztályokra definiált „multiplikatív rend” kifejezést a következő értelemben is használjuk: adott egy R = (U,+,×) test. Ekkor az a ∈ U elem (U,×) multiplikatív csoportbeli rendjét nevezzük az a ∈ U elem multiplikatív rendjének, és ezt -val vagy jelöljük (esetleg  -val vagy  -val vagy  -val vagy hasonlóan). Mivel ez gyakorlatilag a csoportelméletben értelmezett rendfogalom alkalmazása egy speciális helyzetben (amit az indokol, hogy tekinthető az (U,+) additív csoportra vonatkozó rend is), ezért a rend cikkben foglalkozunk vele külön.

Formális definíció 

Formálisan a következőt mondhatjuk: legyen , ekkor az i szám  -vel, vagy röviden -vel jelölt multiplikatív rendje a következő szám: .

A multiplikatív rend kiszámítására egyszerű explicit képletet (ellentétben az additív renddel) nem ismerünk. Könnyű viszont belátni, hogy ez a rend is egy maradékosztály-tulajdonság: a mod(m) egymással kongruens számok multiplikatív rendje egyenlő (ez a kongruenciák hatványozhatóságából következik).

Belátható, hogy ha a>1, akkor a multiplikatív rend az a∈ℕ egész szám vagy maradékosztály hatványai  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 ha az a-nak létezik rendje, akkor két hatványa 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, az említett tétel bizonyítása megtalálható azonban e cikkben is, lentebb .

Létezése: nem mindig létezik 

Nincs minden számnak minden modulusra nézve multiplikatív rendje, például mod(4) (vagy akár mod(6)) nincs multiplikatív rendje a 2-nek ( , és általában ha k>1, akkor is ). Egy számnak akkor és csak akkor létezik multiplikatív rendje, ha relatív prím a modulushoz.

Ennek mélyebb, csoportelméletre épülő magyarázata: a mod(m) redukált maradékosztályok véges csoportot alkotnak a szorzásra nézve, melynek rendje φ(m); és véges csoportban minden elemnek van rendje, a legkisebb szám azon pozitív számok közt, melyre mint kitevőre az elemet emelve az egységelem adódik. Ilyen pozitív szám mindig van (tehát egy legkisebb, azaz a rend is létezik), mégpedig a csoport rendje, azaz φ(m). Nem mindig ez az összes elem rendje – azaz az elem rendje nem felt. a csoport rendje – azonban Lagrange tétele szerint az elem rendje ennek a számnak osztója (ha az elem és a csoport rendje véletlenül egybeesik, akkor az elem egy primitív gyök mod(m)). Ha a szorzásra nézve a maradékosztályok csoportot alkotnának, akkor minden maradékosztálynak lenne multiplikatív rendje, sajnos azonban általában  nem csoport, mert a szorzás nem invertálható (például a nem redukált maradékosztályok zérusosztók, és így nem invertálhatóak- egyébként pontosan a redukált maradékosztályok invertálhatóak, tehát pontosan akkor invertálható minden nem nulla elem, azaz pontosan akkor vagyunk csoportban, ha m prím, mivel pontosan a prímekre igaz, hogy minden nem nulla osztály redukált). Pontatlanul fogalmazva tehát azt mondhatjuk, hogy multiplikatív rend mod(m) azért nem mindig létezik, mert léteznek mod(m) zérusosztók.

Rendtáblázat 

A (multiplikatív) rend kis egész számokra a következőképp alakul:

Kiterjesztett definíció 

Mivel bármely pozitív szám nulladik hatványa 1, ami automatikusan kongruens önmagával tetszőleges nem nulla modulus esetén; ezért az üres helyekre 0-t (esetleg ∞-t) írva nyugodtan kiterjeszthetjük a definíciót úgy, hogy minden nemnegatív számnak legyen rendje. Ez arra szolgál, hogy ne legyen már üres hely a táblázatban, ne legyen a rend parciális függvény. Tulajdonképpen csak így van értelme azt mondani, hogy a multiplikatív rend periódusa a hatványok sorozatának. Az ilyesfajta kiterjesztésnek azonban nincs ezen kívül fontos szerepe a számelméletben.

Fontosabb tulajdonságok 

A legeslegfontosabb megemlíteni a következő tételt:

Legyen m>0 egész szám, továbbá a,'i,'j∈ℕ; továbbá létezzen  , azaz legyen  ; ekkor
  . 
Ekkor a dolog a kongruenciák egyszerűsítési szabályából következik. Jelöljük a rendet röviden  -val
 Legyen , tehát i=ko(a)+j. Ekkor  ;
 Legyen most  , ezt írjuk át így (tegyük fel, hogy i≤j; a jelöléseket így is megválaszthatjuk):  . Most osszuk el maradékosan -t a nem nulla o(a) számmal, kapjuk például, hogy , ahol q,r∈ℤ és a maradékos osztás definíciója szerint  . Ekkor  , tehát  . Azonban o(a) a rend definíciója alapján a legkisebb pozitív egész, amelyre a-t emelve 1-gyel mod(m) kongruens számot kapunk, és az előző szerint r egy nála kisebb nemnegatív egész. Ez csak úgy lehetséges, ha nem pozitív az r, azaz . Tehát ; azaz  , azaz  ; ami épp azt jelenti, hogy  . QED.

Speciális esetként azt kapjuk, hogy egy i∈ℕ egész számra , hiszen ezt átírhatjuk úgy, hogy  , és ez már tényleg az előző tétel egyik esete (j=0) . Ez utóbbit röviden úgy fogalmazhatjuk meg, hogy a mod(m) 1-et adó kitevők pontosan a (multiplikatív) rend többszörösei; vagy szokásosabb, de pongyolább megfogalmazásban, „a rend osztója az 1-et adó kitevőknek”.

RMO és primitív gyök 

Ha egy maradékosztálynak létezik mod(m) multiplikatív rendje, akkor redukált maradékosztálynak (RMO) is nevezzük.

Ha egy számnak a mod(m) multiplikatív rendje épp φ(m), akkor neve primitív gyök modulo(m). Az ilyen  számok nevezetessége, hogy generálják a mod(m) multiplikatív redukált maradékosztály-csoport elemeit, azaz bármely  számra  esetén  valamilyen  -ra.

Lásd még 

 Moduláris számelmélet
 kongruencia
 Rend (csoportelmélet)
 Rend (matematika)

Számelmélet