From d26394a09b228d5b24e0c7147cd5055674952b51 Mon Sep 17 00:00:00 2001 From: david Date: Mon, 12 Jan 2009 18:05:42 +0000 Subject: Correct exercise 4. --- controle-20081202.tex | 106 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 106 insertions(+) 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} + % % % -- cgit v1.2.3