Fonction indicatrice d’Euler

Core idea

Overview

La fonction indicatrice d’Euler, notée φ(n), compte le nombre d’entiers positifs inférieurs ou égaux à n qui sont premiers avec n. C’est une fonction multiplicative fondamentale en théorie des nombres, utilisée pour explorer les propriétés de l’arithmétique modulaire et des groupes cycliques.

When to use: Utilisez cette fonction lorsque vous calculez l’ordre du groupe multiplicatif des entiers modulo n. C’est l’outil principal pour appliquer le théorème d’Euler en exponentiation modulaire ou pour déterminer le nombre de générateurs dans un groupe cyclique d’ordre n.

Why it matters: Cette équation est la pierre angulaire mathématique de l’algorithme de chiffrement RSA, qui sécurise les communications numériques modernes. Elle permet de calculer des clés privées en déterminant l’indicatrice du produit de deux grands nombres premiers.

Symbols

Variables

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

ϕ (n)

Totient Value

Variable

n

Input Integer

Variable

Walkthrough

Derivation

Dérivation/Compréhension de la fonction indicatrice d'Euler

Cette dérivation montre comment la fonction indicatrice d'Euler, qui compte les entiers positifs jusqu'à un entier donné n qui sont premiers avec n, peut être exprimée en utilisant la factorisation première de n.

n est un entier positif.
p désigne un nombre premier.

1

Définition et propriété multiplicative :

Nous commençons par définir la fonction indicatrice d'Euler et énoncer sa propriété multiplicative cruciale, qui nous permet de décomposer le calcul pour les nombres composés en calculs pour leurs facteurs de puissance première.

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

Cas pour une puissance première :

Pour une puissance première $p^{k}$ , les seuls nombres qui ne sont pas premiers avec elle sont ses multiples de $p$ . Soustraire ceux-ci du total $p^{k}$ des nombres donne la formule pour $ϕ (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

Cas général utilisant la factorisation première :

En utilisant le théorème fondamental de l'arithmétique, tout entier positif $n$ peut être exprimé de manière unique comme un produit de puissances premières. La propriété multiplicative de $ϕ (n)$ nous permet d'appliquer la formule de puissance première à chaque facteur.

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

Substitution et simplification :

En substituant la formule dérivée pour $ϕ (p^{k})$ pour chaque facteur de puissance première et en réorganisant les termes, nous arrivons à la formule produit pour la fonction indicatrice d'Euler, où le produit est pris sur tous les facteurs premiers distincts $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

Imaginez un tamis où vous commencez avec tous les nombres de 1 à n, puis filtrez systématiquement tous les multiples de chaque facteur premier distinct de n, ne laissant que les nombres qui ne partagent aucun facteur commun avec n.

Term

Le compte des entiers positifs inférieurs ou égaux à n qui sont premiers avec n.

Représente la « densité de coprimalité » ou la « primalité relative » des nombres jusqu'à n. Un

ϕ

(n) plus élevé signifie que plus de nombres ne partagent aucun facteur premier commun avec n.

Term

L'entier positif pour lequel l'indicatrice est calculée.

La limite supérieure de l'intervalle des entiers considérés ; l'« univers » des nombres de 1 à n.

Term

Un facteur premier distinct de n.

Ce sont les briques premières fondamentales de n, qui, si elles sont partagées, empêchent d'autres nombres d'être premiers avec n.

Term

La proportion de nombres jusqu'à n qui ne sont pas divisibles par p.

Ce facteur « élimine » les nombres qui partagent un facteur premier p avec n, filtrant efficacement les nombres non premiers avec n basés sur p.

Signs and relationships

(1 - \frac{1}{p}): La soustraction '1 - ...' représente le principe d'exclusion. À partir de l'ensemble total (représenté par 1), la proportion de nombres divisibles par un facteur premier p (qui est 1/p)

Free study cues

Insight

Canonical usage

La fonction indicatrice d'Euler opère sur et renvoie des comptages entiers, qui sont intrinsèquement sans dimension dans un sens physique.

Dimension note

La fonction calcule un comptage d'entiers, rendant son entrée et sa sortie intrinsèquement sans dimension. Elle ne fait intervenir ni unités ni dimensions physiques.

One free problem

Practice Problem

Un analyste doit déterminer le nombre d’entiers inférieurs à 12 qui n’ont aucun facteur commun avec 12 autre que 1. Calculez le résultat de la fonction indicatrice pour cette valeur.

Hint: Les facteurs premiers de 12 sont 2 et 3.

The full worked solution stays in the interactive walkthrough.

Where it shows up

Real-World Context

Dans RSA cryptography, the totient of the product of two large primes p and q is \phi(n) = (p-1)(q-1), which est utilisé(e) pour calculer the decryption key, Euler's Totient Function est utilisé(e) pour calculer Totient Value from Input Integer. Le résultat est important car it helps connect the calculation to the shape, rate, probability, or constraint in the model.

Study smarter

Tips

Si n est premier, alors φ(n) = n - 1.
Identifiez uniquement les facteurs premiers distincts ; ne répétez pas les facteurs s’ils apparaissent plusieurs fois dans la décomposition.
Pour une puissance première pᵏ, la valeur est pᵏ - pᵏ⁻¹.
La fonction est multiplicative : φ(m ×n) = φ(m) ×φ(n) si m et n sont premiers entre eux.

Avoid these traps

Common Mistakes

Inclure à tort tous les diviseurs au lieu des seuls facteurs premiers distincts dans la formule produit.
Confondre phi(n) avec le nombre de diviseurs $τ$ (n).

Keep going

Related Formulas

Common questions

Frequently Asked Questions

Cette dérivation montre comment la fonction indicatrice d'Euler, qui compte les entiers positifs jusqu'à un entier donné n qui sont premiers avec n, peut être exprimée en utilisant la factorisation première de n.

Utilisez cette fonction lorsque vous calculez l’ordre du groupe multiplicatif des entiers modulo n. C’est l’outil principal pour appliquer le théorème d’Euler en exponentiation modulaire ou pour déterminer le nombre de générateurs dans un groupe cyclique d’ordre n.

Cette équation est la pierre angulaire mathématique de l’algorithme de chiffrement RSA, qui sécurise les communications numériques modernes. Elle permet de calculer des clés privées en déterminant l’indicatrice du produit de deux grands nombres premiers.

Inclure à tort tous les diviseurs au lieu des seuls facteurs premiers distincts dans la formule produit. Confondre phi(n) avec le nombre de diviseurs \tau(n).

Dans RSA cryptography, the totient of the product of two large primes p and q is \phi(n) = (p-1)(q-1), which est utilisé(e) pour calculer the decryption key, Euler's Totient Function est utilisé(e) pour calculer Totient Value from Input Integer. Le résultat est important car it helps connect the calculation to the shape, rate, probability, or constraint in the model.

Si n est premier, alors φ(n) = n - 1. Identifiez uniquement les facteurs premiers distincts ; ne répétez pas les facteurs s’ils apparaissent plusieurs fois dans la décomposition. Pour une puissance première pᵏ, la valeur est pᵏ - pᵏ⁻¹. La fonction est multiplicative : φ(m ×n) = φ(m) ×φ(n) si m et n sont premiers entre eux.

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

Définition et propriété multiplicative :

Cas pour une puissance première :

Cas général utilisant la factorisation première :

Substitution et simplification :

Intuition

Insight

Practice Problem

Real-World Context

Tips

Common Mistakes

Related Formulas

Fermat's Little Theorem

Lagrange's Theorem

Frequently Asked Questions

Sources