Função Totiente de Euler — Teoria dos Números

Jan 13 2023

Euler, uma das pessoas mais ocupadas na história da matemática, demonstrou essa função pela primeira vez em 1763. Ele tentou usar pi (π) para denotar a função, mas descobriu que pi estava ocupado.

Euler, uma das pessoas mais ocupadas da história da matemática, demonstrou essa função pela primeira vez em 1763. Ele tentou usar pi ( π) para denotar a função, mas descobriu que pi estava ocupado. Em 1801, Gauss sugeriu que usássemos phi ( ). Foi nomeado o 'Totient Function' em 1879, por James Joseph Sylvester.

Quando digo às pessoas que gosto de matemática...

Com o nome e a notação definidos, vamos ver o que ele faz. Um par coprimo é onde o máximo divisor comum que dois números compartilham é 1. Eles não têm fatores comuns maiores; eles são relativamente primos.

A função Totient nos diz quantos primos primos um número tem menor que ele mesmo. Os coprimos menores do 9 são 1, 2, 4, 5, 7 e 8. (9) = 6. Mas como ele faz isso?

Encontrando o Tociente

Para primos

Para números primos, o valor Totient é 1menor que ele mesmo. Todo número menor que um número primo é relativamente primo a ele. Esta é a definição de um número primo. Portanto, para qualquer primo p, (p) = p -1. Isso foi bastante simples.

Para Poderes Primários

Para um número primo pelevado a uma potência k, os únicos números menores pᵏque NÃO são seus coprimos são outros múltiplos de p. Isso ocorre porque pé o único fator em pᵏ.

pᵏO fator de All pode ser representado: p, 2p, 3p, ..., pᵏ⁻¹p.

pᵏ⁻¹é necessariamente o maior múltiplo de pmaior ou igual a pᵏporque pᵏ⁻¹p = p.

Portanto sabemos que pᵏtem pᵏ⁻¹números menores que ele que não são coprimos. Existem pᵏnúmeros inteiros menores que pᵏ. Se pᵏ⁻¹não são primos primos, então pᵏ - pᵏ⁻¹inteiros são primos primos a pᵏ.

Para potências primos, a fórmula para contar primos menores do que é: (pᵏ) = pᵏ - pᵏ⁻¹.

Para todo o resto

Para aqueles números que não são nem primos nem potências primos, usamos a Fórmula do Produto de Euler. Funciona da seguinte maneira.

Resolvendo para n, que tem jfatores primos, a fórmula do produto assume a forma:

n x (1 — 1/p₁) x (1 — 1/p₂) x ... x (1 — 1/pⱼ).

n = 42
> which has 3 prime factors
j = 3
ϕ(42) = ϕ(7 x 2 x 3) = 42 x (1 — 1/7) x (1 — 1/2) x (1 — 1/3) = 12.
ϕ(42) = 12

Um dos fatores primos de 42 é 3. Sabemos que 1 em 3 números é múltiplo de 3, e os outros 2 em 3 não são. Portanto, multiplicamos 42 por 2/3para nos dar a contagem de números menores que 42 que não compartilham o fator 3.

A repetição desse processo para todos os primos de 42 se parece com: 6/7 x 1/2 x 2/3 = 6/21. Isso nos dá a proporção de todos os números menores que 42 que não compartilham nenhum de seus fatores primos. Para obter a contagem, podemos fazer a proporção multiplicada pelo total: 6/21 x 42 = 12.

Podemos usar isso como uma prova corroborativa para poderes primos também. Descobrimos que, para qualquer potência primária pᵏ, o valor totiente é (pᵏ) = pᵏ - pᵏ⁻¹.

pᵏ — pᵏ⁻¹
pᵏ — (pᵏ x p⁻¹)
pᵏ — (pᵏ x 1/p)
pᵏ(1 — 1/p)

Usando a Função Totiente

Você está equipado para encontrar seu valor em qualquer caso, mas por que você iria querer isso? O Totient de Euler é fortemente apoiado ao trabalhar com a Função de Carmichael, como vimos em nossa explicação em um post anterior . Consequentemente, é muito importante para a criptografia digital.