Indicatorul lui Euler
De la Wikipedia, enciclopedia liberă
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 decât 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)
| φ(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ă
este descompunerea în factori primi distincţi ai lui n unde pj sunt numere prime distincte, avem formula
Aceasta se poate scrie şi
unde produsul se face după numerele prime distincte pr.
[modifică] Teorema lui Euler
, unde (a, n) = 1 , φ(n) este indicatorul lui Euler, a este număr întreg şi n>1 , natural.
- Dacă n este număr prim se obţine mica teoremă a lui Fermat.
- Am notat cu (a, b) cel mai mare divizor comun dintre a şi b.
- Dacă (a, b) = 1 spunem că a şi b sunt prime între ele.
