Indicatrice d'Euler

Corto

Si $n$ est un entier naturel non nul on note $\varphi(n)$ le nombre d'entiers $k$ vérifiant $1\leq k \leq n$ et $pgcd(k,n)=1$. Je cherche des démonstration de $\lim_{n\to \infty} \varphi(n) = +\infty$ et, si possible, de façon élémentaire.

D'après le théorème des nombres premiers on sait qu'il y a environ $n/2\log(n) $ nombres premiers dans $[n/2;n]$ et ces nombres premiers sont forcément premiers avec $n$ d'où $\lim \varphi(n) =+\infty$. Le problème c'est que le théorème des nombres premiers ce n'est pas vraiment élémentaire (les inégalités démontrées par notre bien aimé Tchebychev non plus).

J'ai aussi essayé de montrer que $ \lim \varphi(n) \neq \infty \implies \sum 1/p_i <\infty$ mais sans grand succès. Je pense quand même que cette démonstration doit marcher avec plus d'efforts.

Bref si vous connaissez une démonstration sympa, même non élémentaire, je suis preneur.

Maxtimax

Il y a une démonstration sympa qui consiste à montrer que $\varphi (n) \geq \frac{\sqrt{n}}{2}$.

En effet, soit $n$ un entier naturel, $n=\displaystyle\prod_{i=1}^r p_i^{\alpha_i}$ sa décomposition en nombre premiers, $\alpha_i\geq 1$. Alors $\varphi(n) = \displaystyle\prod_{i=1}^rp_i^{\alpha_i-1}(p_i-1)$.

Pour $p_i\geq 3$, $p_i^{\alpha_i-1}(p_i-1) \geq \sqrt{p_i^{\alpha_i}}$ : ou bien $\alpha_i \geq 2$, auquel cas c'est évident, ou $\alpha_i=1$, auquel cas on compare $p_i-1$ et $\sqrt{p_i}$, donc $p_i^2 - 3p_i +1$ à $0$, et on voit facilement que pour $p_i\geq 3$ on a la bonne inégalité.

Pour $p_i = 2$, on veut comparer $2^{\alpha_i-1}$ à $\sqrt{2^{\alpha_i}}$, et c'est de là que vient le $\frac{1}{2}$ : $2^{\alpha_i-1}\geq \frac{\sqrt{2^{\alpha_i}}}{2}$ est claire.

Donc en réalité on a mieux : $\varphi (n) \geq \sqrt{n}$ si $n$ est impair ou divisible par $4$, $\varphi(n) \geq \frac{\sqrt{n}}{2}$ sinon.

noix de totos

En n'utilisant que des estimations élémentaires (i.e. ne dépassant pas le cadre des théorèmes de Mertens), on a pour tout $n \geqslant 16$
$$\log \left( \frac{\varphi(n)}{n} \right) = \sum_{p \mid n} \log \left( 1 - \frac{1}{p} \right) \geqslant - \sum_{p \mid n} \left( \frac{1}{p} + \frac{1}{p^2} \right) \geqslant - \log \log \log n - 4 - \log \zeta(2)$$
de sorte que
$$\varphi(n) \geqslant \frac{n}{ e^4 \zeta(2) \log \log n}.$$

Corto

Merci pour ces deux démo, je ne connaissais pas les théorèmes de Mertens. Si j'ai un peu de temps et que j'arrive à faire marcher une preuve partant de $\sum 1/p_i = +\infty$ je la posterai ici.

noix de totos

Les théorèmes de Mertens (1874) appartiennent exactement à l'étape qui précède le Théorème des Nombres Premiers (TNP). Ils sont donc considérés comme "élémentaires" (au sens où l'on n'a pas besoin de la variable complexe pour les démontrer).

La recherche actuelle est active pour déterminer des versions totalement explicites de ces théorèmes, et ce depuis l'apparition de l'article profond de Rosser & Schoenfeld (1962).

Comme tu as cité le TNP dans ton message, j'ai posté une preuve qui utilise donc des outils moins forts que le TNP. Ceci étant, la minoration que j'ai donnée ci-dessus est, à la constante près, quasi-optimale via
$$\liminf_{n \to \infty} \frac{\varphi(n) \log \log n}{n} = e^{- \gamma}$$
où $\gamma \approx 0,577 \dotsc$ est la constante d'Euler (Landau, 1903).

gai requin

Une autre preuve élémentaire mais qui ne donne aucun comportement asymptotique.

Pour tout réel $l$, $\{d\in\N^*;\varphi(d)=l\}$ est fini donc $l$ n'est pas valeur d'adhérence de $\varphi$ dont la seule valeur d'adhérence est donc $+\infty$.

@Maxtimax : Un petit échauffement avant de prouver Wedderburn en trois lignes. ;-)

reuns

Il n'y a qu'un nombre fini de $p^k$ petits

Donc si $n$ est grand alors il a un diviseur $p^k$ grand

donc $\varphi(p^k)$ qui est grand divise $\varphi(n)$

Qed $n$ grand implique $\varphi(n)$ grand

Poirot

@reuns : un nombre grand ne peut pas avoir beaucoup de petits facteurs premiers ?

reuns

$2^{10}$ n'a pas de grand facteur $p$ mais il a un grand facteur $p^k$

Dans $n = \prod_{p^k \| n} p^k$ les $p^k$ sont tous différents

Maxtimax

gai requin : je crois qu'on a encore du chemin... et des lignes :-D

Poirot

@reuns : et si je prends $N=2 \times 3 \times \dots \times p_n = \exp(\theta(p_n)) = \exp(p_n + o(p_n)) = \exp(n \log n + o(n \log n))$ tu trouves que $N$ n'est pas grand comparé à son plus grand facteur premier ?

Maxtimax

Poirot : l'argument de reuns ne compare pas $N$ à son facteur premier.
Pour une version (un tout petit peu) plus formelle qui te satisfera peut-être plus : $N$ fixé, l'ensemble des $n$ tels que le plus grand $p^k$ divisant $n$ est $\leq N$ est fini : il n'y a qu'un nombre fini de couples $(p,k)$ tels que $p$ premier, $k\geq 1$ et $p^k \leq N$. Si $n$ n'est pas dedans, alors il a un $p^k$ qui le divise qui est plus grand que $N$ et alors $\varphi(p^k) \leq \varphi(n)$.

Poirot

C'est plus clair, merci.