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 $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 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 z^r 1 maradékot ad m-mel osztva, és ha z^t 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 $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ó

Formálisan a következőt mondhatjuk: legyen $m\in \mathbb {Z} ^{+},i\in \mathbb {Z}$ , ekkor az i szám $o_{m}^{\times }(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, 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 ( $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

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ó

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 $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_{m}^{\times }(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_{m}^{\times }(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 i≤j; 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\leq 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

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.