MathematicsTeoría de NúmerosUniversity

OCRAPOntarioNSWCBSEGCE O-LevelMoECAPS

Función Totient de Euler

Cuenta el número de enteros positivos hasta n que son coprimos con n.

Understand the formulaSee the free derivationOpen the full walkthrough

ϕ (n) = n p ∣ n \prod (1 - \frac{1}{p})

Open Full Walkthrough Try Calculator

This public page keeps the free explanation visible and leaves premium worked solving, advanced walkthroughs, and saved study tools inside the app.

Core idea

Overview

La Función Totient de Euler, denotada como φ(n), cuenta el número de enteros positivos hasta n que son relativamente primos con n. Es una función multiplicativa fundamental en teoría de números utilizada para explorar las propiedades de la aritmética modular y los grupos cíclicos.

When to use: Utilice esta función al calcular el orden del grupo multiplicativo de enteros módulo n. Es la herramienta principal para aplicar el Teorema de Euler en la exponenciación modular o al determinar el número de generadores en un grupo cíclico de orden n.

Why it matters: Esta ecuación es la piedra angular matemática del algoritmo de cifrado RSA, que asegura las comunicaciones digitales modernas. Permite el cálculo de claves privadas al determinar el totient del producto de dos números primos grandes.

Symbols

Variables

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

ϕ (n)

Totient Value

Variable

n

Input Integer

Variable

Walkthrough

Derivation

Derivacion de Función Totient de Euler

Esta derivación muestra cómo la función totiente de Euler, que cuenta los enteros positivos hasta un entero dado n que son coprimos con n, puede expresarse utilizando la factorización prima de n.

n es un entero positivo.
p denota un número primo.

Definición y Propiedad Multiplicativa:

Comenzamos definiendo la función totiente de Euler y estableciendo su crucial propiedad multiplicativa, que nos permite descomponer el cálculo para números compuestos en cálculos para sus factores de potencia 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) .

Caso para una Potencia Prima:

Para una potencia prima $p^{k}$ , los únicos números no coprimos con ella son sus múltiplos de $p$ . Restar estos del total de $p^{k}$ números da la 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}) .

Caso General usando Factorización Prima:

Usando el teorema fundamental de la aritmética, cualquier entero positivo $n$ puede expresarse de forma única como un producto de potencias primas. La propiedad multiplicativa de $ϕ (n)$ nos permite aplicar la fórmula de potencia prima a cada factor.

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}}) .

Sustitución y Simplificación:

Sustituyendo la fórmula derivada para $ϕ (p^{k})$ para cada factor de potencia prima y reorganizando términos, llegamos a la fórmula del producto para la función totiente de Euler, donde el producto se toma sobre todos los factores 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

Imagina un tamiz donde comienzas con todos los números del 1 a n, y luego filtras sistemáticamente todos los múltiplos de cada factor primo distinto de n, dejando solo aquellos números que no comparten factores comunes con n.

Term

La cuenta de enteros positivos menores o iguales a n que son coprimos con n.

Representa la 'densidad coprima' o 'primalidad relativa' de los números hasta n. Un

ϕ

(n) más alto significa que más números no comparten factores primos con n.

Term

El entero positivo para el cual se está calculando el totiente.

El límite superior del rango de enteros que se consideran; el 'universo' de números del 1 a n.

Term

Un factor primo distinto de n.

Estos son los bloques de construcción primos fundamentales de n, que, si se comparten, impiden que otros números sean coprimos con n.

Term

La proporción de números hasta n que no son divisibles por p.

Este factor 'elimina' los números que comparten un factor primo p con n, filtrando efectivamente los números no coprimos basándose en p.

Signs and relationships

(1 - \frac{1}{p}): La resta '1 - ...' representa el principio de exclusión. Del conjunto total (representado por 1), la proporción de números divisibles por un factor primo p (que es 1/p)

Free study cues

Insight

Canonical usage

La Función Totiente de Euler opera sobre y devuelve conteos enteros, que son cantidades inherentemente adimensionales en un sentido físico.

Dimension note

La función calcula un conteo de enteros, haciendo que tanto su entrada como su salida sean cantidades inherentemente adimensionales. No involucra unidades ni dimensiones físicas.

One free problem

Practice Problem

Un analista necesita determinar el número de enteros menores que 12 que no comparten factores comunes con 12 más que 1. Calcule el resultado de la función totient para este valor.

Hint: Los factores primos de 12 son 2 y 3.

The full worked solution stays in the interactive walkthrough.

Where it shows up

Real-World Context

En el caso de RSA cryptography, the totient of the product of two large primes p and q is \phi(n) = (p-1)(q-1), which se utiliza para calcular the decryption key, Euler's Totient Function se utiliza para calcular Totient Value from Input Integer. El resultado importa porque ayuda a conectar el cálculo con la forma, la tasa, la probabilidad o la restricción en el modelo.

Study smarter

Tips

Si n es primo, entonces φ(n) = n - 1.
Identifique solo los factores primos únicos; no repita factores si aparecen varias veces en la factorización.
Para una potencia prima pᵏ, el valor es pᵏ - pᵏ⁻¹.
La función es multiplicativa: φ(m ×n) = φ(m) ×φ(n) si m y n son coprimos.

Avoid these traps

Common Mistakes

Incluir incorrectamente todos los divisores en lugar de solo los factores primos únicos en la fórmula del producto.
Confundir phi(n) con el número de divisores $τ$ (n).

Common questions

Frequently Asked Questions

Esta derivación muestra cómo la función totiente de Euler, que cuenta los enteros positivos hasta un entero dado n que son coprimos con n, puede expresarse utilizando la factorización prima de n.

Utilice esta función al calcular el orden del grupo multiplicativo de enteros módulo n. Es la herramienta principal para aplicar el Teorema de Euler en la exponenciación modular o al determinar el número de generadores en un grupo cíclico de orden n.

Esta ecuación es la piedra angular matemática del algoritmo de cifrado RSA, que asegura las comunicaciones digitales modernas. Permite el cálculo de claves privadas al determinar el totient del producto de dos números primos grandes.

Incluir incorrectamente todos los divisores en lugar de solo los factores primos únicos en la fórmula del producto. Confundir phi(n) con el número de divisores \tau(n).

Si n es primo, entonces φ(n) = n - 1. Identifique solo los factores primos únicos; no repita factores si aparecen varias veces en la factorización. Para una potencia prima pᵏ, el valor es pᵏ - pᵏ⁻¹. La función es multiplicativa: φ(m ×n) = φ(m) ×φ(n) si m y n son 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.

Función Totient de Euler

Overview

Variables

Derivation

Definición y Propiedad Multiplicativa:

Caso para una Potencia Prima:

Caso General usando Factorización Prima:

Sustitución y Simplificación:

Intuition

Insight

Practice Problem

Real-World Context

Tips

Common Mistakes

Related Formulas

Fermat's Little Theorem

Lagrange's Theorem

Frequently Asked Questions

Sources