Correct exercise 4.

1 files changed, 106 insertions, 0 deletions

diff --git a/controle-20081202.tex b/controle-20081202.tex
index 3ad1420..963a706 100644
--- a/controle-20081202.tex
+++ b/controle-20081202.tex
@@ -318,6 +318,112 @@ ni de $13$, montrer que $\varphi(\frac{13}{18}n) = \varphi(n)$.
 combien les questions précédentes permettent-elles d'affirmer la
 véracité de la conjecture ?
 
+\begin{corrige}
+Rappelons du cours que si $u$ et $v$ sont premiers entre eux, on a
+\[
+\varphi(uv) = \varphi(u)\,\varphi(v)\tag{*}
+\]
+(c'est une conséquence immédiate du théorème chinois
+$(\mathbb{Z}/uv\mathbb{Z})^\times \cong
+(\mathbb{Z}/u\mathbb{Z})^\times \times
+(\mathbb{Z}/v\mathbb{Z})^\times$ en prenant les cardinaux).  \textit{A
+  contrario}, si $u$ est divisible par chaque nombre premier
+divisant $v$ (par exemple si $u|v$), on a
+\[
+\varphi(uv) = u \, \varphi(v)\tag{\textdagger}
+\]
+puisque $\varphi(v) = v\prod_{p|v}(1-\frac{1}{p})$ et $\varphi(uv) =
+uv\prod_{p|uv}(1-\frac{1}{p})$, le produit portant sur le même
+ensemble de nombres premiers $p$.
+
+(1a) Si $n$ est impair, c'est-à-dire si $2$ et $n$ sont premiers entre
+eux, alors $\varphi(2n) = \varphi(2)\,\varphi(n) = \varphi(n)$
+d'après (*) (remarquer $\varphi(2)=1$).
+
+(1b) Si $n$ est pair mais non multiple de $4$, le nombre
+$\frac{1}{2}n$ est un entier impair, donc de nouveau $\varphi(n) =
+\varphi(2\,\frac{1}{2}n) = \varphi(2)\,\varphi(\frac{1}{2}n) =
+\varphi(\frac{1}{2}n)$ d'après (*).
+
+(1c) Si $n$ est multiple de $4$ mais non de $12$, le nombre
+$\frac{1}{2}n$ est un entier pair mais non multiple de $3$ (donc
+premier à lui), donc d'une part $\varphi(\frac{3}{2}n) =
+\varphi(3\,\frac{1}{2}n) = \varphi(3)\,\varphi(\frac{1}{2}n) =
+2\varphi(\frac{1}{2}n)$ d'après (*) (remarquer $\varphi(3)=2$) et
+d'autre part $\varphi(n) = \varphi(2\,\frac{1}{2}n) =
+2\varphi(\frac{1}{2}n)$ d'après (\textdagger).  En rassemblant ces
+deux égalités, on a $\varphi(\frac{3}{2}n) = \varphi(n)$.
+
+(1d) Si $n$ est multiple de $12$ mais non de $36$, le nombre
+$\frac{1}{3}n$ est un entier pair mais non multiple de $3$, donc d'une
+part $\varphi(n) = \varphi(3\,\frac{1}{3}n) =
+\varphi(3)\,\varphi(\frac{1}{3}n) = 2\varphi(\frac{1}{3}n)$
+d'après (*) et d'autre part $\varphi(\frac{2}{3}n) =
+\varphi(2\,\frac{1}{3}n) = 2\varphi(\frac{1}{3}n)$
+d'après (\textdagger).  En rassemblant ces deux égalités, on a
+$\varphi(\frac{2}{3}n) = \varphi(n)$.
+
+(1e) Si $n$ est multiple de $36$ mais non de $252$, le nombre
+$\frac{1}{6}n$ est un entier multiple de $6$ mais non multiple de $7$,
+donc d'une part $\varphi(\frac{7}{6}n) = \varphi(7\,\frac{1}{6}n) =
+\varphi(7)\,\varphi(\frac{1}{6}n) = 6\varphi(\frac{1}{6}n)$
+d'après (*) (remarquer $\varphi(7)=6$) et d'autre part $\varphi(n) =
+\varphi(6\,\frac{1}{6}n) = 6\varphi(\frac{1}{6}n)$
+d'après (\textdagger).  En rassemblant ces deux égalités, on a
+$\varphi(\frac{7}{6}n) = \varphi(n)$.
+
+(1f) Si $n$ est multiple de $252$ mais non de $1764$, le nombre
+$\frac{1}{7}n$ est un entier multiple de $6$ mais non multiple de $7$,
+donc d'une part $\varphi(n) = \varphi(7\,\frac{1}{7}n) =
+\varphi(7)\,\varphi(\frac{1}{7}n) = 6\varphi(\frac{1}{7}n)$
+d'après (*) et d'autre part $\varphi(\frac{6}{7}n) =
+\varphi(6\,\frac{1}{7}n) = 6\varphi(\frac{1}{7}n)$
+d'après (\textdagger).  En rassemblant ces deux égalités, on a
+$\varphi(\frac{6}{7}n) = \varphi(n)$.
+
+(2) De façon exactement analogue à (1c) et (1e), si $n$ est multiple
+de $6^2\times 7^2 = 1764$ mais non de $6^2\times 7^2\times 43$, on
+montre que $\varphi(\frac{43}{42}n) = \varphi(n)$.  De façon
+exactement analogue à (1d) et (1f), si $n$ est multiple de $6^2\times
+7^2\times 43$ mais non de $6^2\times 7^2\times 43^2$, on montre que
+$\varphi(\frac{42}{43}n) = \varphi(n)$.
+
+Appelons $n$ un entier qui ne vérifie pas la conjecture, s'il existe.
+D'après (1a), $n$ doit être pair (car les entiers impairs vérifient la
+conjecture).  D'après (1b), il doit donc être multiple de $4$.
+D'après (1c), il doit alors être multiple de $12$.  D'après (1d), il
+doit alors être multiple de $36$.  D'après (1e), il doit alors être
+multiple de $36\times 7 = 252$.  D'après (1f), il doit alors être
+multiple de $36\times 7^2 = 1764$.  D'après le paragraphe précédent,
+il doit alors être multiple de $6^2\times 7^2\times 43$, puis de
+$6^2\times 7^2\times 43^2$.
+
+(On ne peut plus ensuite continuer ce petit jeu de façon aussi
+mécanique, puisque $6\times 7\times 43 + 1 = 1807$ n'est plus
+premier.)
+
+(3) Si $n$ est multiple de $(6\times 7 \times 43)^2$ mais ni de $27$
+ni de $13$, le nombre $\frac{1}{18}n$ est un entier multiple de $2$
+mais non multiple de $3$ ni de $7$, donc d'une part
+$\varphi(\frac{13}{18}n) = \varphi(13\,\frac{1}{18}n) =
+\varphi(13)\,\varphi(\frac{1}{18}n) = 12\varphi(\frac{1}{18}n)$
+d'après (*) et d'autre part $\varphi(n) = \varphi(9\times 2 \times
+\frac{1}{18}n) \buildrel\textrm{(*)}\over=
+\varphi(9)\varphi(2\,\frac{1}{18}n) = 6 \varphi(2\,\frac{1}{18}n)
+\buildrel\textrm{(\textdagger)}\over= 6\times 2\times
+\varphi(\frac{1}{18}n) = 12\varphi(\frac{1}{18}n)$.  En rassemblant
+ces deux égalités, on a $\varphi(\frac{13}{18}n) = \varphi(n)$.
+
+(4) Si $n$ ne vérifie pas la conjecture, on sait déjà qu'il doit être
+multiple de $6^2\times 7^2\times 43^2$, et la question (3) montre
+qu'il doit de plus l'être de $27$ (donc de $2^2\times 3^3\times
+7^2\times 43^2$) ou bien de $13$ (donc de $2^2\times 3^2\times
+7^2\times 13\times 43^2$).  Il doit donc au moins être égal à
+$2^2\times 3^3\times 7^2\times 43^2 \geq 9\times 10^6$.  On a donc
+montré que la conjecture était vraie au moins pour les neuf millions
+de premiers entiers naturels.
+\end{corrige}
+
 %
 %
 %