Numere coprime.

Se definesc numerele coprime ca fiind numerele care nu au factori comuni.

Spre exemplu, 15 şi 26 sunt numere coprime:

→ numărul 15, are factorii: 3, 5

→ numărul 26, are factorii: 2, 13

Numere semiprime.

Se definesc numerele semiprime ca fiind numerele care se obţin prin înmulţirea a două numere prime (poate fi acelaşi număr prim).

Spre exemplu:

→ 15 este semiprim fiind egal cu 3·5

→ 9 este semiprim fiind egal cu 3·3

Numere prime în sistemul zecimal.

Se numeşte număr prim orice număr natural p, p>2, care are drept divizori pe ±1 şi ±p.

Exemple: 2, 3, 5, 7, 11, 13, 17, 19,....

Pentru a determina dacă un număr este prim, împărţim respectivul număr la toate numerele prime în ordine crescătoare, până când obţinem un cât mai mic sau egal cu împărţitorul.

Dacă numărul se divide cu unul dintre respectivele numere prime atunci numărul este un număr compus.

Numărul 209 este compus deoarece:

2 ∤ 209, 3 ∤ 209, 5 ∤ 209, 7 ∤ 209, 11 | 209 numărul prim 11 divide numărul 209.

Dacă numărul nu se divide cu nici unul dintre respectivele numere prime atunci numărul este un număr prim.

Numărul 97 este prim deoarece: 2 ∤ 209, 3 ∤ 209, 5 ∤ 209, 7 ∤ 209, 11 ∤ 209 şi deoarece câtul a devenit mai mic decât împărţitorul (97:11= 8 rest 9, unde 8 (câtul) < 11 (împărţitorul) se poate opri cautarea.

Lista numere prime.

ℼ(x) reprezintă numărul de numere prime ≤ decât x.

Pentru valori mici ale lui x (≤ ${\mathrm{10}}^{\mathrm{10}}$), valorile lui ℼ(x) se pot găsi relativ uşor.

Valoarea estimativă pentru ℼ(x) poate fi obţinută cu ajutorul formulei: $\frac{x}{\mathrm{ln(x)}}$

De remarcat faptul că $\frac{x}{\mathrm{ln(x)}}$ ≤ ℼ(x) pentru x > 10.

Se poate astfel obţine probabilitatea ca un număr sa fie prim: $\frac{1}{\mathrm{ln(x)}}$

Spre exemplu, dacă doresc să aflu un număr prim cu 3 cifre, se vor selecta numerele întregi de 3 cifre şi se vor testa dintre ele aproximativ ln(${\mathrm{10}}^3$) sau aproximativ 6.90 numere întregi înainte de a descoperi un număr prim. Ştiind că sunt 168 de numere prime de 3 cifre, valoarea obţinută reprezintă o aproximare.

În reprezentarea binară, toate numerele (cu excepţia numărului 2), încep şi se termină cu cifra 1.

Funcţia lui Euler φ(n).

Funcţia totient φ(n) a unui număr întreg pozitiv n>1 reprezintă numerele <n care sunt coprime cu numărul n. Pentru φ(1) este convenită valoarea φ(1)=1.

Determinare divizori.

Dacă un număr natural n are descompunerea canonică n = $p_1^{e_1}·p_2^{e_2}·...·p_k^{e_k}$, atunci divizorii săi naturali sunt termenii produsului: ($1+p_1+p_1^2+...+p_1^{e_1}$)·($1+p_2+p_2^2+...+p_2^{e_2}$)·...·($1+p_{\mathrm{k}}+p_{\mathrm{k}}^2+...+p_{\mathrm{k}}^{e_{\mathrm{k}}}$)

Astfel, numărul 13500 are descompunerea factorială $2^2$ · $3^3$ · $5^3$ va avea divizorii dintre termenii produsului: (1+2+$2^2$)·(1+3+$3^2$+$3^3$)·(1+5+$5^2$+$5^3$) = [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 25, 27, 30, 36, 45, 50, 54, 60, 75, 90, 100, 108, 125, 135, 150, 180, 225, 250, 270, 300, 375, 450, 500, 540, 675, 750, 900, 1125, 1350, 1500, 2250, 2700, 3375, 4500, 6750, 13500]

Omega Ω(n).

Se defineşte Ω(n) ca fiind numărul divizorilor primi ai unui număr natural n ţinând cont de multiplicitatea acestora.

Astfel, numărul 13500 are descompunerea factorială $2^2$ · $3^3$ · $5^3$ va avea Ω(n) (numărul divizorilor primi ţinând cont de multiplicitatea acestora): Ω(13500) = 2+3+3 = 8

Sigma σ₀(n).

Se defineşte σ₀(n) ca fiind numărul divizorilor primi ai unui număr natural n.

Dacă un număr natural n are descompunerea canonică $p_1^{e_1}·p_2^{e_2}·...·p_k^{e_k}$, atunci numărul divizorilor săi naturali notat prin σ₀(n) sau τ(n) este dat de formula: σ₀(n) = (1+e₁)·(1+e₂)·...·(1+e_k).

Astfel, numărul 13500 are descompunerea factorială $2^2$ · $3^3$ · $5^3$ va avea σ₀(n) (numărul divizorilor primi): σ₀(13500) = (1+2)·(1+3)·(1+3) = 48 de divizori.

Sigma σ₁(n).

Se defineşte σ₁(n) ca fiind suma divizorilor primi ai unui număr natural n.

Dacă un număr natural n are descompunerea canonică $p_1^{e_1}·p_2^{e_2}·...·p_k^{e_k}$, atunci suma divizorilor săi naturali notat prin σ₁(n) este dată de formula: σ₁(n) = $\frac{p_1^{e_1+1}-1}{e_1-1}$·$\frac{p_2^{e_2+1}-1}{e_2-1}$·...·$\frac{p_{\mathrm{k}}^{e_{\mathrm{k}}+1}-1}{e_{\mathrm{k}}-1}$.

Funcţia zeta.

Similar,funcţia zeta pentru numere prime are expresia: P(z)=$\sum _p\frac{1}{p^z}$=$\frac{1}{2^z}+\frac{1}{3^z}+\frac{1}{5^z}$+...