(La première question est un des exercices de révision de Mme Jaulent, la seconde question provient d’un sujet d’informatique de M Pawlowski.)
On rappelle que l’indicatrice d’Euler \varphi désigne le cardinal du groupe des inversibles de \mathbb{Z}/n\mathbb{Z}.
- Soit n=p_1^{\alpha_1} ... p_k^{\alpha_k}. Montrer que \varphi(n) = n \prod_{i=1}^{k} \left( 1-\frac{1}{p_i} \right)
- Soit n \in \mathbb{N}. Montrer que n = \sum_{d | n} \varphi(d)
Besoin d’une indication ?
Pour la question 2, considérer pour chaque diviseur d l’ensemble des des entiers inférieurs à n dont le PGCD avec n est \frac{n}{d}. Quel est son cardinal ? Quelle sera l’union de ces ensembles pour tous les diviseurs de n et son intersection ?
RSS 2.0