L’indicatrice d’Euler

Rappels et notations

Soit {n\in\mathbb N^*}. On écrit {x\equiv y\ [n]} si {n} divise {x-y}, c’est-à-dire si {y=x+kn} pour un entier {k}, ou encore si {x,y} ont le même reste dans la division par {n}.

C’est une relation d’équivalence sur {\mathbb Z}. La classe de {x} est {\overline x=\{x+kn:k\in\mathbb Z\}}. L’ensemble des classes, noté {\mathbb Z_n}, possède {n} éléments : {\overline0,\ldots,\overline{n-1}}.

Les lois {\overline x+\overline y=\overline{x+y}} et {\overline x\,\overline y=\overline{xy}} en font un anneau commutatif. On note {U_n} son groupe multiplicatif des éléments inversibles.

L’indicateur d’Euler {\varphi(n)} est le nombre d’entiers de {\{1,\ldots,n\}} premiers avec {n}. On note {m\wedge n} le PGCD et {m\vee n} le PPCM.

Énoncé et corrigé

Soit {p} un nombre premier.

1. (a) Préciser la valeur de {\varphi(p)}.

1. (b) Pour tout entier {m\ge1}, montrer que {\varphi(p^m)=p^m-p^{m-1}}.

2. (a) Soit {a\in\mathbb Z}. Montrer que {\overline a\in U_n\iff a\wedge n=1}. Il en résulte que {\varphi(n)} est l’ordre du groupe {U_n}.

2. (b) Soit {a} premier avec {n}. Montrer que {a^{\varphi(n)}\equiv1\ [n]} de deux façons : en utilisant l’ordre de {\overline a} dans {U_n}, puis en justifiant que {x\mapsto\overline a x} est une bijection de {U_n}.

Quel résultat obtient-on quand {n} est premier ?

2. (c) Montrer que, pour tout {n\ge3}, {\varphi(n)} est pair.

3. On suppose {n\ge2}. Montrer l’équivalence des conditions : {n} est premier ; {\mathbb Z_n} est un corps ; {\mathbb Z_n} est intègre.

4. On choisit indépendamment deux entiers {a,b} au hasard dans {\{1,\ldots,n\}}. Montrer que la probabilité d’avoir {a\wedge b=1} est {p_n=\frac1{n^2}\left(2\sum_{k=1}^n\varphi(k)-1\right)}On admet que {p_n\to6/\pi^2}. On interprète ce résultat en disant que la probabilité pour que deux entiers choisis au hasard soient premiers entre eux vaut {6/\pi^2}.

Dans la question 5, {m,n\in\mathbb N^*} sont premiers entre eux et {um+vn=1} avec {u,v\in\mathbb Z}.

On note {\overline x} la classe modulo {mn}, {\widehat x} celle modulo {m}, et {\widetilde x} celle modulo {n}.

5. (a) Montrer qu’on définit une application {\psi:\mathbb Z_{mn}\to\mathbb Z_m\times\mathbb Z_n} en posant {\psi(\overline x)=(\widehat x,\widetilde x)}.

5. (b) Montrer que {\psi} est un isomorphisme d’anneaux.

5. (c) Pour tout {(\widehat y,\widetilde z)\in U_m\times U_n}, montrer que {\psi^{-1}(\widehat y,\widetilde z)=\overline x}, avec {x=umz+vny}.

5. (d) Montrer que la restriction de {\psi} à {U_{mn}} est une bijection sur {U_m\times U_n}.

5. (e) En déduire {\varphi(mn)=\varphi(m)\varphi(n)}.

Pour {n\ge1}, on note {P_n} l’ensemble des diviseurs premiers de {n} ; en particulier {P_1=\varnothing}.

6. (a) Montrer que {P_m\cap P_n=P_{m\wedge n}} et {P_m\cup P_n=P_{m\vee n}=P_{mn}}. Que dire de {P_m,P_n} si {m,n} sont premiers entre eux ?

6. (b) Pour tout {n\ge1}, montrer que {\varphi(n)=n\prod_{p\in P_n}\left(1-\frac1p\right)}Calculer {\varphi(10!)}.

6. (c) Pour tous {m,n\ge1}, montrer que {\varphi(m)\varphi(n)\le\varphi(mn)}, avec égalité seulement lorsque {m,n} sont premiers entre eux.

7. (a) Montrer que si {m\mid n}, alors {\varphi(m)\mid\varphi(n)}.

7. (b) Montrer que {\varphi(m)\vee\varphi(n)} divise {\varphi(m\vee n)} et que {\varphi(m\wedge n)} divise {\varphi(m)\wedge\varphi(n)}.

On fixe {n\in\mathbb N^*} et l’on note {D_n} l’ensemble de ses diviseurs positifs.

8. (a) Soit {f:\{1,\ldots,n\}\to D_n}, {f(k)=n\wedge k}. Montrer que chaque {d\in D_n} possède exactement {\varphi(n/d)} antécédents.

8. (b) En déduire {\sum\limits_{d\in D_n}\varphi(d)=n}.

8. (c) On définit {\mu(k)=0} si {k} est divisible par le carré d’un premier ; sinon {\mu(k)=(-1)^r}, où {r} est le nombre de ses diviseurs premiers.

Prouver que {\varphi(n)=\sum_{d\in D_n}\mu(d)\frac nd}Indication : raisonner par récurrence sur le nombre de diviseurs premiers de {n}.