Indicatorul lui Euler

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

Indicatorul lui Euler sau funcția lui Euler se notează cu φ(n) (unde n este un număr natural nenul ) și φ(n) reprezintă numărul de numere mai mici sau egale cu n și prime cu acesta.

  • Exemple: φ(0) = 1 prin convenție; φ(1) = 1 ;φ(2) = 1 ; φ(3) = 2 ; φ(4) = 2 ;φ(5) = 4 ;φ(720) = 192 ; φ(p) = p-1 , dacă p este număr prim.
  • Primele valori ale lui φ(n)
\phi(n) +0 +1 +2 +3 +4 +5 +6 +7 +8 +9
0+   1 1 2 2 4 2 6 4 6
10+ 4 10 4 12 6 8 8 16 6 18
20+ 8 12 10 22 8 20 12 18 12 28
30+ 8 30 16 20 16 24 12 36 18 24
40+ 16 40 12 42 20 24 22 46 16 42
50+ 20 32 24 52 18 40 24 36 28 58
60+ 16 60 30 36 32 48 20 66 32 44
70+ 24 70 24 72 36 40 36 60 24 78
80+ 32 54 40 82 24 64 42 56 40 88
  • Dacă n = p_1^{k_1} \cdots p_r^{k_r} este descompunerea în factori primi distincți ai lui n unde p_j sunt numere prime distincte, avem formula
\phi(n)=(p_{1}-1)p_{1}^{k_{1}-1} \cdots (p_{r}-1)p_{r}^{k_{r}-1}

Aceasta se poate scrie și

\phi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)

unde produsul se face după numerele prime distincte pr.

Teorema lui Euler[modificare | modificare sursă]

a^{\varphi (n)} \equiv 1 \pmod{n}, unde (a, n) = 1 , φ(n) este indicatorul lui Euler, a este număr întreg și n>1 , natural.

Legături externe[modificare | modificare sursă]