Rădăcina primitivă modul n

Funcţia modulo reprezintă restul împărţirii a două numere întregi a şi b. Astfel, a mod b = r, dacă r = a - n·b şi 0 ≤ r < b.

Câteva exemple de utilizare:

⋄$3^1$ mod 7 = 3. Se observă că 3 < 7, şi se poate astfel folosi expresia: 3 - 7 · 0 = 3

⋄$3^2$ mod 7 = 2. Se observă că 2 < 7, şi se poate astfel folosi expresia: 9 - 7 · 1 = 2

⋄$3^3$ mod 7 = 6. Se observă că 6 < 7, şi se poate astfel folosi expresia: 27 - 7 · 3 = 6

⋄$3^4$ mod 7 = 4. Se observă că 4 < 7, şi se poate astfel folosi expresia: 81 - 7 · 11 = 4

⋄$3^5$ mod 7 = 5. Se observă că 5 < 7, şi se poate astfel folosi expresia: 243 - 7 · 24 = 5

⋄$3^6$ mod 7 = 1. Se observă că 1 < 7, şi se poate astfel folosi expresia: 729 - 7 · 104 = 1

Se poate astfel observa cum un număr $g^k$ mod n se va repeta după o anumită valoare a lui k, deoarece mod n produce un număr finit de valori.

Numărul g este rădăcina primitivă modulo n, dacă pentru orice număr a coprim cu n, (gcd(a,n)=1), există un număr întreg k astfel încât: $g^k$ ≣ a (mod n).Numărul k este astfel indexul numărului a cu baza g modulo n.

Cea mai mică valoare a lui k pentru care $g^k$ ≣ 1 (mod n) este φ(n) şi poartă denumirea de ordinul multiplicativ a rădăcinii primitive modulo n.

Numărul rădăcinilor primitive modulo n este egal cu φ(φ(n)).

Împărţirea pentru numere naturale: împărţirea întreagă (fără rest).

Dacă a ∈ ℕ şi b ∈ ${\mathbb{N}}^{*}$, atunci există q ∈ ℕ şi r ∈ ℕ astfel încât a = b·q +r, cu 0 ≤ r < b,q şi r fiind unic determinaţi cu această proprietate.

Spre exemplu: a = 39 şi b = 12, există q = 3 şi r = 3, astfel încât 39 = 3 · 12 + 3.

Împărţirea pentru numere întregi.

Dacă a ∈ ℤ şi b ∈ ${\mathbb{Z}}^{*}$, atunci există q ∈ ℤ şi r ∈ ℤ astfel încât a = b·q +r, cu 0 ≤ r < |b|, q şi r fiind unic determinaţi cu această proprietate. .

Denumiri folosite: a - deîmpărţit, b - împărţitor, q - cât, r - rest.