Multiplikatív rend

A Wikipédiából, a szabad lexikonbó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 (pl. 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.

Tartalomjegyzék

[szerkesztés] Formális definíció

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 om(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 .

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

[szerkesztés] Rendtáblázat

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

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

[szerkesztés] 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 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 pl., 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”.

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

[szerkesztés] Lásd még