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  m \in \mathbb{Z}^{+} 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  o^{\times}(a) -val vagy jelöljük (esetleg  o_{\times}(a) -val vagy  o_{R^{\times}}(a) -val vagy  o_{R^{*}}(a) -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 | forrásszöveg szerkesztése]

Formálisan a következőt mondhatjuk: legyen  m \in \mathbb{Z}^{+} , i \in \mathbb{Z} , ekkor az i szám  o^{\times}_{m}(i) -vel, vagy röviden  o_{m}(i) -vel jelölt multiplikatív rendje a következő szám:  o_{m}(i) := min \left\{ e \in \mathbb{N}^{+} \ | \ i^{e} \equiv 1 \pmod{m} \right\} .

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  (a^{i})_{ i \in \mathbb{Z}} = \left( a^{0} , a^{1} , a^{2} , ... , a^{i} , ... \right) 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  i indexeik, azaz a többszörözőik kongruensek mod(m). Ezt bővebben a rend c. szócikkben tárgyaljuk. Azu említett tétel bizonyítása megtalálható azonban e cikkben is, lentebb .

Létezése: nem mindig létezik[szerkesztés | forrásszöveg szerkesztése]

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 ( 2^{1} \equiv 2 \pmod{4} , 2^{2} \equiv 0 \pmod{4} , és általában ha k>1, akkor is  2^{5} \equiv 0 \pmod{4} ). 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  \mathbb{Z}_{m} 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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 kiterjeszhetjü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 | forrásszöveg szerkesztése]

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  o_{m}^{\times}(a) , azaz legyen  \left( a, m \right) = 1  ; ekkor

 a^{i} \equiv a^{j} \pmod{m} \Leftrightarrow i \equiv j \pmod{o^{\times}_{m}(a)} .

Ekkor a dolog a kongruenciák egyszerűsítési szabályából következik. Jelöljük a rendet röviden  o(a) := o^{\times}_{m}(a) -val

  • Legyen  i \equiv j \pmod{o(a)} , tehát i=ko(a)+j. Ekkor  a^{i} = a^{ko(a)+j} = (a^{o(a)})^{k} \cdot a^{j} \equiv 1^{k}a^{j} = a^{j} \pmod{m}  ;
  • Legyen most  a^{i} \equiv a^{j} \pmod{m} , ezt írjuk át így (tegyük fel hogy ij; a jelöléseket így is megválaszthatjuk):  a^{j-i} \equiv 1 \pmod{m} . Most osszuk el maradékosan  j-i -t a nem nulla o(a) számmal, kapjuk például, hogy  j-i = qo(a)+r , ahol q,r∈ℤ és a maradékos osztás definíciója szerint  0 \le r < o(a) . Ekkor  1 \equiv a^{j-i} \equiv a^{qo(a)+r} = a^{qo(a)}a^{r} = ( a^{ o(a) } )^{q} \cdot a^{r} \equiv 1^{q} a^{r} = a^{r} \pmod{m} , tehát  a^{r} \equiv 1 \pmod{m} . 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  r=0 . Tehát  j-i = qo(a) (+0) ; azaz  j = qo(a)+i , azaz  o(a) \ | \ j-i  ; ami épp azt jelenti, hogy  i \equiv j \pmod{o(a)} . QED.

Speciális esetként azt kapjuk, hogy egy i∈ℕ egész számra  a^{i} \equiv 1 \pmod{m} \Leftrightarrow o(a)|i , hiszen ezt átírhatjuk úgy, hogy  a^{i} \equiv a^{0} \pmod{m} \Leftrightarrow i \equiv 0 \pmod{o(a)} , é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 | forrásszöveg szerkesztése]

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  p \in \mathbb{Z} számok nevezetessége, hogy generálják a mod(m) multiplikatív redukált maradékosztály-csoport elemeit, azaz bármely  j \in \mathbb{Z} számra  \left( j , m \right) = 1 esetén  j \equiv p^{k} \pmod{m} valamilyen  k \in \mathbb{Z}^{+} -ra.

Lásd még[szerkesztés | forrásszöveg szerkesztése]