Função Totiente de Euler

Core idea

Overview

A Função Totiente de Euler, denotada como φ(n), conta o número de inteiros positivos até n que são primos entre si com n. É uma função multiplicativa fundamental na teoria dos números, usada para explorar as propriedades da aritmética modular e dos grupos cíclicos.

When to use: Use esta função ao calcular a ordem do grupo multiplicativo de inteiros módulo n. É a ferramenta principal para aplicar o Teorema de Euler na exponenciação modular ou ao determinar o número de geradores em um grupo cíclico de ordem n.

Why it matters: Esta equação é o alicerce matemático do algoritmo de criptografia RSA, que protege as comunicações digitais modernas. Permite o cálculo de chaves privadas, determinando a totiente do produto de dois grandes números primos.

Symbols

Variables

$ϕ$ (n) = Totient Value, n = Input Integer

ϕ (n)

Totient Value

Variable

n

Input Integer

Variable

Walkthrough

Derivation

Derivação/Compreensão da Função Totiente de Euler

Esta derivação mostra como a função totiente de Euler, que conta os inteiros positivos até um dado inteiro n que são relativamente primos a n, pode ser expressa usando a fatoração em primos de n.

n é um inteiro positivo.
p denota um número primo.

1

Definição e Propriedade Multiplicativa:

Começamos definindo a função totiente de Euler e declarando sua crucial propriedade multiplicativa, que nos permite decompor o cálculo para números compostos em cálculos para seus fatores de potência prima.

Euler’s totient function ϕ (n) counts the positive integers up to n that are relatively prime to n . It is a multiplicative function, meaning if g cd (m, n) = 1, then ϕ (mn) = ϕ (m) ϕ (n) .

2

Caso para uma Potência Prima:

Para uma potência prima $p^{k}$ , os únicos números não relativamente primos a ela são seus múltiplos de $p$ . Subtrair estes dos $p^{k}$ números totais dá a fórmula para $ϕ (p^{k})$ .

Consider n = p^{k} for a prime p and integer k \geq 1. The integers not relatively prime to p^{k} are multiples of p : p, 2 p, \dots, p^{k - 1} p . There are p^{k - 1} such multiples up to p^{k} . ϕ (p^{k}) = p^{k} - p^{k - 1} = p^{k} (1 - \frac{1}{p}) .

3

Caso Geral usando Fatoração em Primos:

Usando o teorema fundamental da aritmética, qualquer inteiro positivo $n$ pode ser expresso unicamente como um produto de potências primas. A propriedade multiplicativa de $ϕ (n)$ nos permite aplicar a fórmula da potência prima a cada fator.

Let the prime factorization of n be n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}} . Due to the multiplicative property, we can write: ϕ (n) = ϕ (p_{1}^{k_{1}}) ϕ (p_{2}^{k_{2}}) \dots ϕ (p_{r}^{k_{r}}) .

4

Substituição e Simplificação:

Ao substituir a fórmula derivada para $ϕ (p^{k})$ para cada fator de potência prima e rearranjar os termos, chegamos à fórmula do produto para a função totiente de Euler, onde o produto é tomado sobre todos os fatores primos distintos $p$ de $n$ .

Substitute the formula for ϕ (p^{k}) into the expression: ϕ (n) = p_{1}^{k_{1}} (1 - \frac{1}{p _{1}}) \cdot p_{2}^{k_{2}} (1 - \frac{1}{p _{2}}) \dots p_{r}^{k_{r}} (1 - \frac{1}{p _{r}}) ϕ (n) = (p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}) (1 - \frac{1}{p _{1}}) (1 - \frac{1}{p _{2}}) \dots (1 - \frac{1}{p _{r}}) Recognizing that n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}, we get: ϕ (n) = n p ∣ n \prod (1 - \frac{1}{p}) .

Result

Substitute the formula for ϕ (p^{k}) into the expression: ϕ (n) = p_{1}^{k_{1}} (1 - \frac{1}{p _{1}}) \cdot p_{2}^{k_{2}} (1 - \frac{1}{p _{2}}) \dots p_{r}^{k_{r}} (1 - \frac{1}{p _{r}}) ϕ (n) = (p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}) (1 - \frac{1}{p _{1}}) (1 - \frac{1}{p _{2}}) \dots (1 - \frac{1}{p _{r}}) Recognizing that n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}, we get: ϕ (n) = n p ∣ n \prod (1 - \frac{1}{p}) .

Source: Rosen, K. H. (2011). Elementary Number Theory and Its Applications (6th ed.). Pearson.

Why it behaves this way

Intuition

Imagine uma peneira onde você começa com todos os números de 1 a n, e então filtra sistematicamente todos os múltiplos de cada fator primo distinto de n, deixando apenas aqueles números que não compartilham fatores comuns com n.

Term

A contagem de inteiros positivos menores ou iguais a n que são coprimos a n.

Representa a 'densidade coprima' ou 'primalidade relativa' dos números até n. Um

ϕ

(n) maior significa que mais números não compartilham fatores primos com n.

Term

O inteiro positivo para o qual o totiente está sendo calculado.

O limite superior do intervalo de inteiros considerados; o 'universo' de números de 1 a n.

Term

Um fator primo distinto de n.

Estes são os blocos de construção primos fundamentais de n, que, se compartilhados, impedem que outros números sejam coprimos a n.

Term

A proporção de números até n que não são divisíveis por p.

Este fator 'remove' os números que compartilham um fator primo p com n, efetivamente filtrando números não coprimos com base em p.

Signs and relationships

(1 - \frac{1}{p}): A subtração '1 - ...' representa o princípio de exclusão. Do conjunto total (representado por 1), a proporção de números divisíveis por um fator primo p (que é 1/p)

Free study cues

Insight

Canonical usage

A Função Totiente de Euler opera sobre e retorna contagens inteiras, que são grandezas inerentemente adimensionais em sentido físico.

Dimension note

A função calcula uma contagem de inteiros, tornando tanto sua entrada quanto sua saída grandezas inerentemente adimensionais. Ela não envolve unidades ou dimensões físicas.

One free problem

Practice Problem

Um analista precisa determinar o número de inteiros menores que 12 que não compartilham fatores comuns com 12 além de 1. Calcule o resultado da função totiente para este valor.

Hint: Os fatores primos de 12 são 2 e 3.

The full worked solution stays in the interactive walkthrough.

Where it shows up

Real-World Context

No caso de RSA cryptography, the totient of the product of two large primes p and q is \phi(n) = (p-1)(q-1), which é utilizado para calcular the decryption key, Euler's Totient Function é utilizado para calcular Totient Value from Input Integer. O resultado importa porque ajuda a conectar o cálculo com a forma, a taxa, a probabilidade ou a restrição no modelo.

Study smarter

Tips

Se n é primo, então φ(n) = n - 1.
Identifique apenas fatores primos únicos; não repita fatores se eles aparecerem várias vezes na fatoração.
Para uma potência prima pᵏ, o valor é pᵏ - pᵏ⁻¹.
A função é multiplicativa: φ(m ×n) = φ(m) ×φ(n) se m e n são coprimos.

Avoid these traps

Common Mistakes

Incluir incorretamente todos os divisores em vez de apenas fatores primos únicos na fórmula do produto.
Confundir phi(n) com o número de divisores $τ$ (n).

Keep going

Related Formulas

Common questions

Frequently Asked Questions

Esta derivação mostra como a função totiente de Euler, que conta os inteiros positivos até um dado inteiro n que são relativamente primos a n, pode ser expressa usando a fatoração em primos de n.

Use esta função ao calcular a ordem do grupo multiplicativo de inteiros módulo n. É a ferramenta principal para aplicar o Teorema de Euler na exponenciação modular ou ao determinar o número de geradores em um grupo cíclico de ordem n.

Esta equação é o alicerce matemático do algoritmo de criptografia RSA, que protege as comunicações digitais modernas. Permite o cálculo de chaves privadas, determinando a totiente do produto de dois grandes números primos.

Incluir incorretamente todos os divisores em vez de apenas fatores primos únicos na fórmula do produto. Confundir phi(n) com o número de divisores \tau(n).

No caso de RSA cryptography, the totient of the product of two large primes p and q is \phi(n) = (p-1)(q-1), which é utilizado para calcular the decryption key, Euler's Totient Function é utilizado para calcular Totient Value from Input Integer. O resultado importa porque ajuda a conectar o cálculo com a forma, a taxa, a probabilidade ou a restrição no modelo.

Se n é primo, então φ(n) = n - 1. Identifique apenas fatores primos únicos; não repita fatores se eles aparecerem várias vezes na fatoração. Para uma potência prima pᵏ, o valor é pᵏ - pᵏ⁻¹. A função é multiplicativa: φ(m ×n) = φ(m) ×φ(n) se m e n são coprimos.

References

Sources

Wikipedia: Euler's totient function
Rosen, Kenneth H. Elementary Number Theory and Its Applications. 6th ed. Pearson, 2011.
A Friendly Introduction to Number Theory by Joseph H. Silverman
Elementary Number Theory and Its Applications by Kenneth H. Rosen
Rosen, K. H. (2011). Elementary Number Theory and Its Applications (6th ed.). Pearson.

Overview

Variables

Derivation

Definição e Propriedade Multiplicativa:

Caso para uma Potência Prima:

Caso Geral usando Fatoração em Primos:

Substituição e Simplificação:

Intuition

Insight

Practice Problem

Real-World Context

Tips

Common Mistakes

Related Formulas

Fermat's Little Theorem

Lagrange's Theorem

Frequently Asked Questions

Sources