Indicatorul lui Euler

Indicatorul lui Euler sau funcția lui Euler se notează cu φ(n) (unde n este un număr natural nenul) și contorizează numerele întregi pozitive 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 143 de valori ale lui φ(n) sunt:^[1]

φ(n) pentru 1 ≤ n ≤ 143

+	0	1	2	3	4	5	6	7	8	9	10	11
0	N/A	1	1	2	2	4	2	6	4	6	4	10
12	4	12	6	8	8	16	6	18	8	12	10	22
24	8	20	12	18	12	28	8	30	16	20	16	24
36	12	36	18	24	16	40	12	42	20	24	22	46
48	16	42	20	32	24	52	18	40	24	36	28	58
60	16	60	30	36	32	48	20	66	32	44	24	70
72	24	72	36	40	36	60	24	78	32	54	40	82
84	24	64	42	56	40	88	24	72	44	60	46	72
96	32	96	42	60	40	100	32	102	48	48	52	106
108	36	108	40	72	48	112	36	88	56	72	58	96
120	32	110	60	80	60	100	36	126	64	84	48	130
132	40	108	66	72	64	136	44	138	48	92	70	120

• Dacă ${\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}$ este descompunerea în factori primi distincți ai lui n unde ${\displaystyle p_{i}}$ sunt numere prime distincte, este valabilă formula

${\displaystyle \varphi (n)=(p_{1}-1)p_{1}^{k_{1}-1}\cdots (p_{r}-1)p_{r}^{k_{r}-1}}$

Primele 100 de valori ale funcției lui Euler

Aceasta se poate scrie și

${\displaystyle \varphi (n)=n\prod _{p|n}\left(1-{\frac {1}{p}}\right)}$

unde produsul se face după numerele prime distincte p_r.

Un număr nontotient este un număr întreg pozitiv ${\displaystyle n}$ pentru care ecuația φ(x) = ${\displaystyle n}$ nu are soluții.^[2] Primele numere nontotiente sunt: 14, 26, 34, 38, 50, 62, 68, 74, 76, 86, 90, 94, 98... ^[3]

Teorema lui Euler

${\displaystyle 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.

• Dacă n este număr prim se obține mica teoremă a lui Fermat.
• Dacă (a, b) = 1 spunem că a și b sunt prime între ele.