Multiplikatív rend

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

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 nemnegatív egész szám, melyre mint kitevőre a(z 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 rt.

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ó[szerkesztés]

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[szerkesztés]

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[szerkesztés]

A (multiplikatí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 14 15 16 17
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1
3 1 2 1 2 1 2 1 2 1 2 1 2
4 1 2 1 2 1 2 1 2 1
5 1 4 4 2 1 4 4 2 1 4 4 2 1 4
6 1 2 1 2 1 2
7 1 3 6 3 6 2 1 3 6 3 6 2 1 3 6
8 1 2 2 2 1 2 2 2 1
9 1 6 3 6 3 6 1 6 3 6 3 6
10 1 4 4 2 1 4 4
11 1 10 5 5 5 10 10 10 5 2 1 10 5 5 5 10
12 1 2 2 2 1 2

Kiterjesztett definíció[szerkesztés]

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[szerkesztés]

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 ij; 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[szerkesztés]

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[szerkesztés]