De rădăcini primitive modulo n este un concept de aritmetica modulară în teoria numerelor . Ele sunt ( în cazul în care acestea există) a generatoarelor din grupul de invertibles ale inelului ℤ / n ℤ .
Dacă n este un număr întreg strict pozitiv, numerele prime cu n , luate modulo n , formează un grup de multiplicare, notat ( Z / n Z ) × sau Z n × . Acest grup este ciclic dacă și numai dacă n este egal cu 4 sau p k sau 2 p k pentru un număr prim p ≥ 3 și k ≥ 0. Un generator al acestui grup ciclic se numește rădăcină primitivă modulo n sau element primitiv de Z n × . O rădăcină primitivă modulo n este deci un număr întreg g astfel încât orice inversabil din Z / n Z este o putere a lui g modulo n .
Luați de exemplu n = 14. Elementele lui ( Z / 14 Z ) × sunt clasele de congruență 1, 3, 5, 9, 11 și 13. Deci 3 este o rădăcină primitivă modulo 14 și avem 3 2 ≡ 9, 3 3 ≡ 13, 3 4 ≡ 11, 3 5 ≡ 5 și 3 6 ≡ 1 (modulo 14). Singura altă rădăcină primitivă modulo 14 este 5.
Iată un tabel care conține cele mai mici rădăcini primitive pentru unele valori ale lui n (continuare A046145 din OEIS )
nu | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
rădăcină primitivă mod n | 1 | 2 | 3 | 2 | 5 | 3 | - | 2 | 3 | 2 | - | 2 | 3 |
Iată un tabel care dă cele mai mici rădăcini primitive r modulo numerele prime p mai mici de 1 000 (continuare A001918 a OEIS ):
Nu cunoaștem nicio formulă generală simplă pentru a calcula rădăcinile primitive modulo n . Există totuși o metodă pentru a testa dacă un număr întreg m este rădăcina primitivă mod n - adică dacă ordinul său multiplicativ modulul n este egal cu φ ( n ) ( ordinea lui Z n × ) - care este mai rapid decât un calcul simplu mod n al tuturor puterilor sale succesive până la exponentul φ ( n ):
Am calculat anterior φ ( n ) și am determinat divizorii săi primi, adică p 1 , ..., p k . Verificăm dacă niciunul nu împarte m . Apoi, se calculează utilizând, de exemplu, metoda exponențierii rapide . Numărul întreg m este o rădăcină primitivă dacă și numai dacă aceste k rezultate sunt toate diferite de 1.
Rădăcinile primitive mod n sunt rădăcinile din ℤ / n ℤ ale φ ( n ) -th polinomului ciclotomic Φ φ ( n ) .
Pentru orice număr prim p , al n - lea polinom ciclotomic Φ n este ireductibil pe câmpul finit Z p dacă și numai dacă p este o rădăcină primitivă modulo n . În consecință, numărul întreg n modulo care nu are nicio rădăcină primitivă (continuare A033949 a OEIS ) sunt acelea astfel încât Φ n este reductibil pe toate Z p . Acestea sunt, de asemenea, modulele întregi care 1 are rădăcini pătrate, altele decât 1 și –1.
Numărul rădăcinilor primitive modulo n (suita A046144 din OEIS ), atunci când există (suita A033948 ), este egal cu φ (φ ( n )), deoarece orice grup ciclic de ordine r are generatori φ ( r ).
Pentru orice număr prim p , se notează cu g p cea mai mică rădăcină primitivă modulo p (între 1 și p - 1). Avem următoarele două rezultate:
Conjecturăm că orice număr întreg relativ, altul decât –1 și nu pătrat, este un modulo de rădăcină primitivă o infinitate de numere prime (a se vedea „ Conjectura lui Artin asupra rădăcinilor primitive ”).
(ro) Shuguang Li și Carl Pomerance , „Primitive Roots: A Survey” , în Methods Theoretic Methods , Springer ,2002( citiți online [PDF] ) , p. 219-231