Ordinea numerelor de modul

Exponentul sau ordinea multiplicativă a unui întreg modulo este cel mai mic număr întreg pozitiv astfel încât [1] [2] $A$ $m$ $\ell$

a^{\ell }\equiv 1{\pmod {m)).

Exponentul este definit doar pentru numere relativ prime la modulul , adică pentru elementele grupului de elemente inversabile ale inelului de resturi modulo . În plus, dacă exponentul numărului modulo este definit, atunci acesta este un divizor al valorii funcției Euler (o consecință a teoremei Lagrange ) și al valorii funcției Carmichael . $A$ $m$ $m$ $A$ $m$ $\varphi(m)$ $\lambda(m)$

Pentru a arăta dependența indicatorului de și , este de asemenea notat , iar dacă este fix, atunci pur și simplu . $\ell$ $A$ $m$ $P_m(a)$ $m$ $P(a)$

Proprietăți

$a\equiv b\pmod m\Rightarrow P(a)=P(b)$ , deci putem presupune că exponentul este dat pe clasa de reziduuri modulo . ${\bar {a}}$ $m$
$a^n\equiv 1\pmod m\Rightarrow P(a)\mid n$ . În special, și , unde este funcția Carmichael și este funcția Euler . $P(a)\mid\lambda(m)$ $P(a)\mid\varphi(m)$ $\lambda(m)$ $\varphi(m)$
$a^t\equiv a^s\pmod m \Leftrightarrow t\equiv s\pmod{P(a)}.$
$P(a^s)\mid P(a)$ ; dacă , atunci $\gcd(s,P(a))=1$ $P(a^s)=P(a).$
Dacă este un număr prim și , atunci sunt toate soluțiile comparației . $p$ $P(a)=k$ $a,\;\ldots ,\;a^{k)$ $x^k\equiv 1\pmod p$
Dacă este un număr prim, atunci este un generator al grupului . $p$ $P(a)=p-1\Săgeată stânga-dreapta a$ $\mathbb {Z} _{p}$
Dacă este numărul de clase de reziduuri cu indicatorul , atunci . Și pentru module simple chiar și . $\psi(k)$ $k$ $\sum \limits _{k\,\mid \,\varphi (m)}\psi (k)=\varphi (m)$ $\psi(k)=\varphi(k)$
Dacă este un număr prim, atunci grupul de reziduuri este ciclic și, prin urmare, dacă , unde este un generator, , și este coprim cu , atunci . În cazul general, pentru un modul arbitrar , o formulă similară poate fi derivată folosind teorema privind structura grupului de reziduuri multiplicative . $p$ ${\mathbb {Z}}_{p}^{{\times }}$ $a=g^{dk}$ $g$ $d\mid p-1$ $k$ $p-1$ $P(a)=\frac{p-1}{d}$ $m$ ${\mathbb {Z}}_{m}^{{\times }}$

Exemplu

Deoarece , dar , , , atunci ordinul lui 2 modulo 15 este 4. $2^4\equiv 1\pmod{15}$ $2^1\not\equiv 1\pmod{15}$ $2^2\not\equiv 1\pmod{15}$ $2^3\not\equiv 1\pmod{15}$

Calcul

Dacă se cunoaște descompunerea modulului în factori primi și se cunoaște descompunerea numerelor în factori primi, atunci exponentul unui număr dat poate fi găsit în timp polinomial din . Pentru a calcula, este suficient să găsiți factorizarea funcției Carmichael și să calculați all for all . Deoarece numărul de divizori este limitat de polinomul lui , iar modulo de exponenție are loc în timp polinomial, algoritmul de căutare va fi polinom. $m$ $pijamale}$ $p_j-1$ $A$ $\ln m$ $\lambda(m)$ $a^{d}\mod m$ $d\mid \lambda (m)$ $\ln m$

Aplicații

Personajele lui Dirichlet

Modulul caracterului Dirichlet este determinat de relațiile obligatorii și . Pentru ca aceste relații să se mențină, este necesar ca ele să fie egale cu o rădăcină complexă a unității . $\chi$ $m$ $\chi(ab)=\chi(a)\chi(b)$ $\chi(a)=\chi(a+m)$ $\chi(a)$ $P_{m}(a)$

Ordinea numerelor de modul

Proprietăți

Exemplu

Calcul

Aplicații

Personajele lui Dirichlet

Vezi și

Note

Literatură