Calculadora da função totiente de Euler (φ)

Insira um número inteiro N (1 a 1.000.000) para calcular instantaneamente quantos inteiros entre 1 e N são coprimos com N (função totiente de Euler φ(N)), com a fatoração em números primos e a fórmula usada. Inclui uma tabela de referência de φ(n) de 1 a 100.

Tabela de referência de φ(n) de 1 a 100

Uma tabela que resume a fatoração em primos e o valor da função totiente de Euler para cada inteiro de 1 a 100.

N	Fatoração	φ(n)
1	1	1
2	2	1
3	3	2
4	2²	2
5	5	4
6	2 × 3	2
7	7	6
8	2³	4
9	3²	6
10	2 × 5	4
11	11	10
12	2² × 3	4
13	13	12
14	2 × 7	6
15	3 × 5	8
16	2⁴	8
17	17	16
18	2 × 3²	6
19	19	18
20	2² × 5	8
21	3 × 7	12
22	2 × 11	10
23	23	22
24	2³ × 3	8
25	5²	20
26	2 × 13	12
27	3³	18
28	2² × 7	12
29	29	28
30	2 × 3 × 5	8
31	31	30
32	2⁵	16
33	3 × 11	20
34	2 × 17	16
35	5 × 7	24
36	2² × 3²	12
37	37	36
38	2 × 19	18
39	3 × 13	24
40	2³ × 5	16
41	41	40
42	2 × 3 × 7	12
43	43	42
44	2² × 11	20
45	3² × 5	24
46	2 × 23	22
47	47	46
48	2⁴ × 3	16
49	7²	42
50	2 × 5²	20
51	3 × 17	32
52	2² × 13	24
53	53	52
54	2 × 3³	18
55	5 × 11	40
56	2³ × 7	24
57	3 × 19	36
58	2 × 29	28
59	59	58
60	2² × 3 × 5	16
61	61	60
62	2 × 31	30
63	3² × 7	36
64	2⁶	32
65	5 × 13	48
66	2 × 3 × 11	20
67	67	66
68	2² × 17	32
69	3 × 23	44
70	2 × 5 × 7	24
71	71	70
72	2³ × 3²	24
73	73	72
74	2 × 37	36
75	3 × 5²	40
76	2² × 19	36
77	7 × 11	60
78	2 × 3 × 13	24
79	79	78
80	2⁴ × 5	32
81	3⁴	54
82	2 × 41	40
83	83	82
84	2² × 3 × 7	24
85	5 × 17	64
86	2 × 43	42
87	3 × 29	56
88	2³ × 11	40
89	89	88
90	2 × 3² × 5	24
91	7 × 13	72
92	2² × 23	44
93	3 × 31	60
94	2 × 47	46
95	5 × 19	72
96	2⁵ × 3	32
97	97	96
98	2 × 7²	42
99	3² × 11	60
100	2² × 5²	40

Dicas

A função totiente de Euler φ(n) conta os inteiros entre 1 e n que são coprimos com n. Por exemplo, φ(9) = 6 (1, 2, 4, 5, 7 e 8 são coprimos com 9).
Quando n é um número primo p, φ(p) = p − 1, pois todos os números de 1 a p, exceto o próprio p, são coprimos com um primo.
Quando n é o produto de dois primos distintos p e q, φ(pq) = (p−1)(q−1) — propriedade usada diretamente na geração de chaves RSA.
A fórmula φ(n) = n × Π(1 − 1/p) é um produto sobre os fatores primos distintos p de n; o expoente de cada primo não afeta o resultado.
Esta ferramenta cobre o intervalo de 1 a 1.000.000 e calcula φ(n) instantaneamente por fatoração via divisão de teste.

Perguntas frequentes

Além de fundamental na teoria dos números, é central na criptografia, especialmente na geração de chaves RSA. A chave privada do RSA é obtida usando φ(n) = (p−1)(q−1).

Por convenção, define-se φ(1) = 1. Embora o único inteiro até 1 seja o próprio 1, definir φ(1) = 1 mantém consistentes as propriedades multiplicativas da função, sendo essa a convenção matemática padrão.

Sim. Como um primo p não tem divisores além de 1 e ele mesmo, todos os inteiros de 1 a p, exceto p, são coprimos com ele, portanto φ(p) = p − 1.

O RSA usa um número composto n = pq, produto de dois primos grandes, como parte da chave pública. Calcular a chave privada exige φ(n) = (p−1)(q−1), mas φ(n) não pode ser encontrado sem fatorar n — essa dificuldade de fatorar números grandes é a base da segurança do RSA.

Curiosidade — A função do século 18 que conta o que é coprimo

A função totiente de Euler foi introduzida por volta de 1763 pelo matemático suíço Leonhard Euler, originalmente ao generalizar o pequeno teorema de Fermat para números compostos. O símbolo φ (fi), hoje padrão, foi adotado mais tarde por outros matemáticos que sistematizaram a notação.

Contar números coprimos pode parecer simples, mas φ(n) tem várias propriedades elegantes. Por exemplo, somando φ(d) para cada divisor d de n, o resultado é sempre n (Σφ(d) = n) — uma das identidades fundamentais da teoria elementar dos números.

Hoje, φ(n) desempenha um papel essencial na criptografia RSA. O RSA usa o produto de dois primos grandes n = pq como parte da chave pública, e calcular a chave privada exige φ(n) = (p−1)(q−1). O fato de que φ(n) não pode ser calculado sem fatorar n (pelo menos com os algoritmos conhecidos atualmente) é um dos pilares da segurança do RSA.

Ver todas as curiosidades

Calculadora da função totiente de Euler (φ)

Tabela de referência de φ(n) de 1 a 100

Dicas

Perguntas frequentes

Para que serve a função totiente de Euler?

Por que φ(1) é igual a 1?

É fácil calcular φ(p) para um primo p?

Qual a relação entre φ(n) e a criptografia RSA?

Curiosidade — A função do século 18 que conta o que é coprimo