Sujet
Pré requis :
- Les nombres premiers sont les nombres entiers naturels différents de 1 n'ayant d'autres diviseurs que 1 et eux-mêmes.
Par exemple, \(2,3,5,7,11\) sont des nombres premiers. Par contre, 9 n'est pas un nombre premier car 3 est un diviseur de 9 .
- Deux nombres entiers naturels peuvent avoir des diviseurs communs différents de 1 ou non. S'ils n'en ont pas, ils sont dits premiers entre eux.
Par exemple, 4 et 9 sont premiers entre eux car 1 est leur seul diviseur commun.
6 et 10 ne sont pas premiers entre eux car ils ont 2 comme diviseur commun.
Soit \(n\) un entier naturel non nul. On note \(\varphi(n)\) le nombre d'entiers inférieurs à \(n\) et premiers avec \(n\). La fonction \(\varphi\) ainsi définie est appelée l'indicatrice d'Euler.
Exemple : \(\varphi(9)=6\) puisque les entiers inférieurs à 9 , premiers avec 9 , sont \(1,2,4,5,7,8\).
- Déterminer \(\varphi(15)\).
- Soit \(p\) un nombre premier.
a) Déterminer \(\varphi(p)\).
b) On admet que \(p^{2}\) admet exactement 3 diviseurs, les déterminer.
c) Justifier que les nombres \(p, 2 p, \ldots,(p-1) p\) sont distincts 2 à 2 , inférieurs à \(p^{2}\), et ont un diviseur commun différent de 1 avec \(p^{2}\) que vous préciserez.
On admet qu'il n'y en a pas d'autres.
d) En déduire que \(\varphi\left(p^{2}\right)=\left(p^{2}-1\right)-(p-1)\) puis que \(\varphi\left(p^{2}\right)=p \varphi(p)\).
e) Calculer \(\varphi(121)\).
3. Soient \(p\) et \(q\) deux nombres premiers distincts.
a) Justifier que les nombres \(p, 2 p \ldots,(q-1) p\) d'une part et \(q, 2 q, \ldots,(p-1) q\) d'autre part sont inférieurs à \(p q\), et ont un diviseur commun différent de 1 avec \(p q\) que vous préciserez.
On admet qu'il n'y en a pas d'autres et que ces nombres sont distincts 2 à 2 .
b) En déduire que \(p q=(p q-1)-(q-1)-(p-1)\), puis que \(\varphi(p q)=\varphi(p) \varphi(q)\).
c) Retrouver alors le résultat de \(\varphi(15)\).
4. Déterminer une valeur de \(n\) pour que \(\varphi(n)=60\).