Lecture zen
soixante-quinze francs en pièces de quarante sous.
Gustave FLAUBERT, Madame Bovary, 1857.
Bases de l’arithmétique.
Arithmétique
Bases de l’arithmétique.
Le père Rouault vint apporter à Charles le paiement de sa jambe remise,
soixante-quinze francs en pièces de quarante sous.
Gustave FLAUBERT, Madame Bovary, 1857.
Pour bien aborder ce chapitre
Un très beau chapitre. Tellement beau que nous allons le traiter deux fois ! En effet, il a beaucoup de points communs avec le suivant. On peut expliquer ces points communs à l’aide de la théorie des idéaux d’un anneau, mais ce n’est pas l’objet ici.
Par ailleurs l’arithmétique a toujours fasciné les hommes, les mathématiciens comme les profanes. Avec un peu de curiosité et d’observation, n’importe qui peut conjecturer des propriétés qui peuvent s’avérer ardues à démontrer. On peut par exemple contempler le tableau des derniers chiffres de \(i^j\) pour \(0\leqslant i \leqslant 9\) et \(1\leqslant j \leqslant 5\). Une explication viendra plus tard... \[\begin{array}{|c||c|c|c|c|c|c|c|c|c|} \hline j\setminus i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \hline 1&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 2&1 & 4 & 9 & 6 & 5 & 6 & 9 & 4 & 1 \\ \hline 3&1 & 8 & 7 & 4 & 5 & 6 & 3 & 2 & 9 \\ \hline 4&1 & 6 & 1 & 6 & 5 & 6 & 1 & 6 & 1 \\ \hline 5&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \newline \hline \end{array}\]
Par ailleurs, on peut s’émerveiller devant les nombres premiers, le mystère de leur répartition et la beauté gratuite de leur étude. Gratuite ? Rien n’est moins sûr ! La découverte d’un algorithme rapide de décomposition en facteurs premiers mettrait à mal bien des codes secrets et l’arithmétique est devenu un secteur d’étude stratégique.
Parmi les nombreux mathématiciens qui se sont intéressés à l’arithmétique, le nom de Gauss se détache. Toute sa vie durant, il est revenu sur des problèmes d’arithmétique. Mais on peut citer Euclide, Diophante, Fermat, Legendre, Euler et Ramanujan.
L’arithmétique est une école de rigueur. Mais une fois les mécanismes acquis, ce chapitre devient une récréation.
Relation de divisibilité, division euclidienne
Relation de divisibilité
(Divisibilité). Soient deux entiers relatifs \((a,b)\in \mathbb{Z}^{2}\). On dit que l’entier \(a\) divise l’entier \(b\) si et seulement si il existe \(k\in \mathbb{Z}\) tel que \(b=ka\).
On notera \(a \mid b\) (se lit \(a\) divise \(b\) ) le fait que l’entier \(a\) divise l’entier \(b\).
(Propriétés de la divisibilité).
Soit \(a,b,c\in\mathbb{Z}\) et \(k_1,k_2\in\mathbb{Z}\). Alors : \[\left[a|b \quad \textrm{ et} \quad a|c\right]\Rightarrow a|\left(k_1b+k_2c\right)\]
En effet: \[\left[a|b \quad \textrm{ et} \quad a|c\right] \Rightarrow \begin{cases} \exists
k\in \mathbb{Z}, \quad b=ka \newline \exists k'\in \mathbb{Z}, \quad c=k'a\end{cases} \Rightarrow
k_1b+k_2c = k_1 k a + k_2 k' a = \left(k_1 k + k_2 k'\right) a \Rightarrow
a|\left(k_1b+k_2c\right)\]
Congruences
(Congruence). Considérons un entier strictement positif \(n \in \mathbb{N}^*\) et deux entiers \((a, b) \in \mathbb{Z}^{2}\). On dit que l’entier \(a\) est congru à l’entier \(b\) modulo \(n\), et l’on note \(a \equiv b \; [n]\) lorsque l’entier \(n\) divise l’entier \((b-a)\) : \[a \equiv b \; [n] \Longleftrightarrow n | (b - a).\]
(Compatibilité des lois avec les congruences). Soient quatre entiers \((a, b, c, d) \in \mathbb{Z}^{4}\) et un entier \(n \in \mathbb{N}^*\). On suppose que
Alors
Laissée en exercice. Le troisième point peut se démontrer à partir du deuxième par récurrence sur \(k\).
Pour démontrer que \(a\mid b\) il peut être intéressant de démontrer que \(b \equiv 0 \; [a]\).
On veut démontrer que \(641\) divise \(2^{32}+1\).
Cet exemple historique est dû à Euler et fournit un contre-exemple à une conjecture de Fermat : \[\forall n\in \mathbb{N}, 2^{2^n}+1 \textrm{ est premier}.\]
On remarque que \(n = 641 = 1 + 640 = 1 + 5\times 2^7 = 625 + 16 = 5^4 + 2^4\).
On en déduit \(5\times 2^7 \equiv -1 \; [n]\). En élevant à la puissance \(4\), on a \(5^4\times 2^{28} \equiv 1 \; [n]\). Comme \(5^4 \equiv -2^4 \; [n]\), on obtient \(-2^4\times 2^{28} \equiv 1 \; [n]\) soit en ajoutant \(2^{32}\) aux deux membres, \(0 \equiv 2^{32}+1 \; [n]\), ce qu’il fallait vérifier.
Pour un nombre entier \(n\) (écrit en base \(10\)) on a \(n \equiv a \; [10]\) où \(a\) désigne le chiffre des unités de \(n\). Ainsi la dernière ligne du tableau des \(i^j\) p. [tableau_i_puissance_j] peut se lire \(i^5 \equiv i \; [10]\) pour tous entiers \(i\).
On a \(10 \equiv 1 \; [9]\) et donc \(\forall k\in\mathbb{N}, 10^k \equiv 1 \; [9]\). En particulier \(\sum_{k=0}^p a_k 10^k \equiv \sum_{k=0}^p a_k \; [9]\). Autrement dit, un nombre entier \(n = \sum_{k=0}^p a_k 10^k\) (écrit en base \(10\)) est congru modulo \(9\) à la somme de ses chiffres, et donc aussi à la somme des chiffres de la somme de ses chiffres, etc. C’est le principe de la preuve par neuf enseignée autrefois à l’école élémentaire. Elle peut s’énoncer de la façon suivante : << Le produit des restes des deux facteurs modulo 9 est congru au reste du produit modulo 9 >>.
...combien font, par exemple, trois milliards sept cent cinquante-cinq millions neuf cent quatre-vingt-dix-huit mille deux cent cinquante et un, multiplié par cinq milliards cent soixante-deux millions trois cent trois mille cinq cent huit? L’Élève, très vite. Ça fait dix-neuf quintillions trois cent quatre-vingt dix quadrillions deux trillions huit cent quarante quatre milliards deux cent dix-neuf millions cent soixante-quatre mille cinq cent huit...
Moralité, le résultat donné par l’élève est faux.
L’exemple suivant est dû à Eugène Ionesco (La Leçon 1951).
Le Professeur
...combien font, par exemple, trois milliards sept cent cinquante-cinq millions neuf cent quatre-vingt-dix-huit mille deux cent cinquante et un, multiplié par cinq milliards cent soixante-deux millions trois cent trois mille cinq cent huit? L’Élève, très vite. Ça fait dix-neuf quintillions trois cent quatre-vingt dix quadrillions deux trillions huit cent quarante quatre milliards deux cent dix-neuf millions cent soixante-quatre mille cinq cent huit...
On prend \(a = 3 755 998 251\), \(b = 5 162 303 508\). La somme des chiffres de \(a\) vaut \(54\) donc \(a \equiv 0 \; [9]\). De même la somme des chiffres de \(b\) vaut \(33\) donc \(b \equiv 6 \; [9]\). Donc le produit \(ab\) est congru à \(0\) modulo \(9\).
La somme des chiffres du produit \(c=19 390 002 844 219 164 508\) annoncé par l’élève vaut \(76\) donc \(c \equiv 4 \; [9]\).
On peut de demander quelle est valeur exacte du produit. Faute d’un logiciel de calcul formel qui donnerait la solution, on travaille avec une calculatrice qui donne quatorze chiffres significatif (en l’occurence il s’agit d’un tableur).
Bien entendu, on vérifie avec la preuve par neuf que \(ab \equiv 0 \; [9]\).
Il donne \(3 755 998 251 \times 5 162 303 508 = 19 389 602 947 179 200 000\). Il est clair que les derniers chiffres sont faux. Pour les trouver, on travaille modulo \(10^7\), ce qui va donner les sept derniers chiffres : Soit \(a' = 5 998 251\) et \(b' = 2 303 508\). On a \(a \equiv a' \; [10^7]\) et \(b \equiv b' \; [10^7]\). On a donc \(ab \equiv a'b' \; [10^7]\). Le tableur donne \(a'b' = 13 817 019 164 508 \equiv 19 164 508 \pmod{10^7}\). On peut donc reconstituer \(ab = 19 389 602 947 179 164 508\).
(Système complet de restes modulo \(m\)). Soit \(m\) un entier \(\geqslant 2\). On appelle système complet de restes modulo \(m\) un système d’entiers contenant un et un seul représentant de chaque classe.
Exemples : \(\llbracket 0,m-1\rrbracket\), système de \(m\) entiers consécutifs, \(m\) entiers non congrus modulo \(m\) deux à deux.
Soit \(x\longmapsto f(x) = \sum_{i=0}^n a_i x^i\) une fonction polynôme où les \(a_i\in\mathbb{Z}\).
On suppose que l’on a \(f(r)\) non congru à \(0\) modulo \(m\) pour \(r\) décrivant un système complet de restes modulo \(m\). On a alors \(\forall x\in\mathbb{Z}, f(x)\) non congru à \(0\) modulo \(m\).
En effet, soit \(x\in\mathbb{Z}\), il existe un \(r\) appartenant au système complet de restes modulo \(m\), tel que \(x \equiv r \; [m]\). Comme par ailleurs, \(\sum_{i=0}^n a_i x^i \equiv \sum_{i=0}^n a_i r^i \; [m]\), le résultat en découle.
Division euclidienne
(Division Euclidienne). Soient deux entiers \((a,b)\in \mathbb{Z} \times \mathbb{N}\) avec \(b\neq 0\). Alors il existe un \((q,r)\in \mathbb{Z}\times \mathbb{N}\) tel que :
On dit que l’entier \(q\) est le quotient et l’entier \(r\) le reste de la division euclidienne de \(a\) par \(b\).
PGCD, théorèmes d’Euclide et de Bézout
Considérons deux nombres \(a,b \in \mathbb{Z}^*\).
L’ensemble des diviseurs communs à \(a\) et \(b\) est non vide car il contient \(1\). Il est majoré par \(\max\left(\left|a\right|,\left|b\right|\right)\) donc il possède un plus grand élément.
De même, l’ensemble des multiples communs positifs à \(a\) et \(b\) est non vide car il contient \(ab\). Comme cet ensemble est une partie de \(\mathbb{N}\), il possède un plus petit élément.
Ces deux observations justifient la définition suivante :
(PGCD, PPCM). Soient deux entiers non tous deux nuls \((a,b) \in \left(\mathbb{Z}^*\right)^2\).
(Théorème d’Euclide). Soient deux entiers \((a, b) \in \left(\mathbb{Z}^*\right)^2\). Effectuons la division euclidienne de l’entier \(a\) par l’entier \(b\) : \[\exists!(q, r) \in \mathbb{N}^{2}~:\quad
a = bq + r \quad \textrm{ et} \quad
0 \leqslant r < b .\] Alors : \[a\wedge b = b\wedge r.\]
Comme \(r=a-bq\), tout entier divisant à la fois \(a\) et \(b\) divise aussi \(r\). L’ensemble des diviseurs communs à \(a\) et \(b\) est égal à l’ensemble des diviseurs communs à \(b\) et \(r\). En particulier, ces deux ensembles ont le même plus grand élément, ce qui s’écrit aussi : \(a\wedge b = b\wedge r\).
Le théorème précédent justifie l’algorithme d’Euclide pour trouver le pgcd de deux entiers non nuls \((a, b) \in {\mathbb{N}^*}^2\). On pose \(r_0 = a\), \(r_1 = b\) et on définit ensuite \(\forall k \geqslant 1\), les couples \((q_k, r_k)\) en utilisant une division euclidienne : \[\textrm{ si } r_k \neq 0,~\exists!(q_k, r_{k+1}) \in \mathbb{Z}^{2} ~|~ r_{k-1} = q_kr_k + r_{k+1} \textrm{ et } 0 \leqslant r_{k+1} < r_k.\] Comme la suite d’entiers \((r_k)\) est strictement décroissante, il existe un rang \(n \geqslant 1\) tel que \(r_n \neq 0\) et \(r_{n+1} = 0\). D’après le théorème d’Euclide, on a \(\forall k\in \llbracket 0,n - 1\rrbracket\), \(a \wedge b = r_k \wedge r_{k+1}\). Comme \(r_n\) divise \(r_{n-1}\), on a \(r_n\wedge r_{n-1} = r_n\). Par conséquent, le dernier reste non-nul \(r_n\) est le pgcd des entiers \((a, b)\).
Déterminons le pgcd des entiers \(366\) et \(43\) en utilisant l’algorithme d’Euclide : \[\begin{aligned}
366&=&\fbox{43}\times 8 + \fbox{22}\\
\fbox{43}&=&\ovalbox{\fbox{22}}\times1+\ovalbox{21}\\
\ovalbox{22}&=&\fbox{\ovalbox{21}}\times 1 + \fbox{1}\\
\fbox{21}&=&\fbox{1}\times 21+0
\end{aligned}\] donc \(366\wedge 43=1\).
pgcd := proc(a, b)
local A, B, r;
A := a;
B := b;
while (b > 0) do
r := irem(A, B);
A := B;
B := r;
od;
A;
end;
ou sous une forme récursive :
pgcd := proc(a, b)
if b = 0 then a
else
pgcd(b,irem(a,b))
fi;
end;
(Nombres premiers entre eux). On dit que deux nombres \(a\) et \(b\) sont premiers entre eux si et seulement si leur plus grand diviseur commun est \(1\), autrement dit si et seulement si \(a\wedge b=1\).
Étienne Bézout, né le 31 mars 1730 à Nemours, mort le 27 septembre 1783 à Basses-Loges)Mathématicien français. Auteur de différents livres d’enseignement qu’il rédigea à l’attention des gardes de la marine ou des élèves du corps de l’artillerie. Il est surtout connu pour le théorème ci dessous mais il a travaillé également sur les déterminants et les équations algébriques. Son nom est attaché à d’autres théorèmes en géométrie algébrique et intersections de courbes.
(Coefficients de Bézout). Soient deux entiers non nuls \((a, b) \in \left(\mathbb{Z}^*\right)^2\). Il existe \((u,v) \in
{\mathbb{Z}}^2\) tels que \[au+bv=a\wedge b.\] Un tel couple \((u,v)\) est appelé couple de coefficients de Bézout de \(a\) et \(b\).
Quitte à considérer \(\left|a\right|\) et \(\left|b\right|\) à la place de \(a\) et \(b\), on peut supposer \(a\) et \(b\) positifs. La preuve se fait par récurrence sur \(b\). Si \(b=0\), alors \(a\wedge b=a\) et \(1.a+0.b=a\) donc un couple de coefficient de Bézout est \(\left(1,0\right)\). On fixe \(b\in\mathbb{N}^*\) et on suppose que la propriété est vraie pour tout \(a\in\mathbb{N}\) et tout nombre \(n\) de l’intervalle d’entiers \(\llbracket 0,b-1\rrbracket\). Par division euclidienne, il existe \(\left(q,r\right)\in\mathbb{N}^2\) tels que \(a=bq+r\) et \(0\leqslant r\leqslant b-1\). D’après le théorème d’Euclide, on sait que \(a\wedge b=b\wedge r\). On applique l’hypothèse de récurrence à \(b\) et \(r\), il existe \((U,V)\in
{\mathbb{Z}}^2\) tels que \(U b+ V r=b\wedge r\). Donc \(Ub+V\left(a-bq\right)=a\wedge b\) et \(V a+\left(U-Vq\right)b=a\wedge b\). La propriété est alors prouvée par récurrence.
Il n’y a pas unicité du couple de coefficients de Bézout de deux entiers. Voir exercice [bezout_toutes_les_solutions] p. [bezout_toutes_les_solutions].
(Théorème de Bézout). Soient deux entiers non nuls \((a, b) \in \left(\mathbb{Z}^*\right)^2\). On a \[a \wedge b = 1 \Longleftrightarrow \left[\exists(u, v) \in \mathbb{Z}^{2}~: \quad
1 = au + bv\right].\]
Soient deux entiers \((a, b) \in \mathbb{Z} \times \mathbb{N}^*\) premiers entre eux. L’algorithme d’Euclide permet de trouver un couple de Bézout \((u,v) \in \mathbb{Z}^{2}\) tel que \(au + bv = 1\). On définit les suites \((r_k)\) et \((q_k)\) des restes et des quotients dans l’algorithme d’Euclide. Notons \(r_n = a\wedge b = 1\) le dernier reste non-nul. On pose \(r_0 = a\), \(r_1 = b\) et par récurrence, on définit \[\forall k \geqslant 1,~ r_{k-1} = q_kr_k + r_{k+1} \textrm{ avec } 0 < r_{k+1}
\leqslant r_k.\] On définit simultanément deux suites \((u_k)\) et \((v_k)\) telles que \[\forall k \in [0, n],~ r_k = u_ka + v_k b\] Pour que cette propriété soit vraie pour tout \(k \in \llbracket 0,n\rrbracket\), on doit poser : \[(u_0, v_0) = (1, 0),~(u_1, v_1) = (0, 1)~\textrm{ et }
\forall k \in \llbracket 2,n\rrbracket,~\begin{cases}
u_{k+1} = u_{k-1} - q_ku_k \\
v_{k+1} = v_{k-1} - q_kv_k
\end{cases}.\] On a alors \(1 = au_n + bv_n\).
\(r_0 = a\) | \(r_1 = b\) | \(r_2\) | … | \(r_k\) | … | 1 |
---|---|---|---|---|---|---|
\(q_1\) | \(q_2\) | … | \(q_k\) | … | \(q_n\) | |
\(1\) | \(0\) | \(u_2\) | … | \(u_k\) | … | \(u_n = u\) |
\(0\) | \(1\) | \(v_2\) | … | \(v_k\) | … | \(v_n = v\) |
Voici une procédure Maple qui prend comme paramètres \(a\) et \(b\) et qui retourne \(a \wedge b\), ainsi qu’un couple de Bézout \((U, V)\)
bezout := proc(a, b)
local R, RR, Q, U, UU, V, VV, temp;
R := a;
RR := b;
U := 1;
UU := 0;
V := 0;
VV := 1;
$\#$Cond entrée : R = r0, RR = r1, U = u0, V = v0, UU = u1, VV = v1
while (RR > 0) do
Q := iquo(R, RR);
temp := UU;
UU := U - Q * UU;
U:=temp;
temp := VV;
VV := V - Q * VV;
V := temp;
temp := RR;
RR := irem(R, RR);
R := temp;
$\#$INV : R = rk, RR = r_{k+1}, U = uk, UU = u_{k+1}, V = vk, VV = v_{k+1},
$\#$ Q = qk, k : nombre de passages dans la boucle while
od;
$\#$Cond sortie : RR = u_{n+1}=0, R = r_n = pgcd(a, b), U = u_n, V = v_n
R, U, V;
end;
Déterminons grâce à l’algorithme d’Euclide un couple de Bézout pour \(a = 22\) et \(b= 17\).
et \(\boxed{1=7\times 22-9\times 17}\).
\(r_0 = 22\) | \(r_1= 17\) | \(r_2=5\) | \(r_3=2\) | \(r_4=1\) |
---|---|---|---|---|
\(q_1=1\) | \(q_2=3\) | \(q_3=2\) | \(q_4=2\) | |
\(u_0=1\) | \(u_1=0\) | \(u_2=1\) | \(u_3=-3\) | \(u_4=7\) |
\(v_0=0\) | \(v_1=1\) | \(v_2=-1\) | \(v_3=4\) | \(v_4=-9\) |
Carl Friedrich Gauss, né le 30 avril 1777 à Brunswick (Saint-Empire romain germanique), mort le 23 février 1855 à Göttingen (Royaume de Hanovre)Mathématicien allemand. C’est un des plus grands mathématiciens de tous les temps. Certains l’ont même surnommé le prince des mathématiques . Alors âgé de trois ans, on raconte qu’il sut corriger son père dans un calcul de salaire. Il est remarqué par ses instituteurs qui le poussent à poursuivre ses études. Á dix-neuf ans, il résout un problème qui date d’Euclide, celui de la construction à la règle et au compas du polygône régulier à dix-sept côtés. Cette découverte fut à l’origine de sa décision de consacrer sa vie aux mathématiques. Il effectue sa thèse sous la direction de Johann Pfaff à l’université de Brunswick. Celle-ci porte sur une démonstration du théorème fondamental de l’algèbre page . Gauss s’intéressa à de nombreuses branches des mathématiques: l’arithmétique, la géométrie, les probabilités, etc. Il a permis des avancées énormes en théorie des nombres, en géométrie non-euclidienne, …Mais il s’est aussi intéressé, entre autres, à l’astronomie ou à la cartographie à chaque fois avec génie. Même si la portée de ses travaux ne fut pas complètement comprise par ses contemporains - Gauss ne publiant que très peu - ce fut la postérité qui comprit la profondeur et l’étendue de son travail à la lecture de son journal intime qui fut publié après sa mort. Il eut comme élèves Richard Dedekind et Bernhard Riemann.
(Théorème de Gauss). Soient trois entiers non nuls \((a, b, c) \in \left(\mathbb{Z}^*\right)^3\). \[\left[ a \mid bc \quad \textrm{ et} \quad a \wedge b = 1 \right] \Rightarrow a \mid
c\]
Si \(a\wedge b=1\) alors, d’après le théorème de Bézout [Theo_de_Bezout], il existe \(\left(u,v\right)\in\mathbb{Z}^{2}\) tel que \(au+bv=1\). On a donc aussi \(auc+bvc=c\). Mais comme \(a\) divise \(bc\) et que \(a\) divise \(auc\), \(a\) divise \(auc+bvc=c\).
(Caractérisation des diviseurs et des multiples). Soient deux entiers \((a, b) \in \mathbb{Z}^{2}\).
Soient deux entiers non nuls \((a, b) \in \left(\mathbb{Z}^*\right)^2\). Pour un entier \(k \in \mathbb{N}^*\), \(\begin{cases}
(ka) \wedge (kb) = k(a \wedge b) \newline
(ka) \vee (kb) = k(a \vee b)
\end{cases}\).
(Autres propriétés du PGCD). Soient trois entiers non nuls \((a, b, c) \in {\mathbb{Z}^*}^3\).
(Relation entre PGCD et PPCM). Soient deux entiers non nuls \((a, b) \in {\mathbb{Z}^*}^2\).
Nombres premiers
Nombres premiers
(Nombre premier, nombre composé). Un entier \(n \in \mathbb{N}\) est dit premier si \(n\geqslant 2\) et si ses seuls diviseurs dans \(\mathbb{N}\), sont \(1\) ou lui-même : \[\forall k \in \mathbb{N}^*,~ k | n \Rightarrow k \in \llbracket 1, n\rrbracket\] On note \(\mathbb{P}\) l’ensemble des nombres premiers.
Si un entier \(n \in \mathbb{N}\) n’est pas premier, on dit qu’il est composé.
Un entier positif est premier si et seulement si le cardinal de l’ensemble de ses diviseurs est égal à \(2\).
(Propriétés des nombres premiers).
Tout entier supérieur à \(2\) admet un diviseur premier.
Effectuons une récurrence forte. Si \(p=2\) alors \(p\) possède un diviseur premier: lui-même. Supposons la propriété vérifiée pour tout entier \(p\in \llbracket 2,n\rrbracket\) et montrons là pour \(p=n+1\). Soit \(\mathscr A\) l’ensemble des diviseurs de \(n+1\). On a \(\left|\mathscr A\right|\geqslant 2\). Si \(\left|\mathscr A\right|= 2\) alors \(n+1\) est premier et cela démontre la propriété sinon \(\mathscr A\) contient un entier \(q\in
\llbracket 2,n\rrbracket\) qui divise \(n+1\). On applique l’hypothèse de récurrence à \(q\) : \(q\) possède un diviseur premier. Ce diviseur premier divise nécessairement aussi \(n+1\) et donc \(n+1\) possède un diviseur premier. La propriété est donc démontrée par récurrence.
L’ensemble \(\mathbb{P}\) des nombres premiers est infini.
Supposons que ce ne soit pas le cas. L’ensemble \(\mathbb{P}\) est alors une partie finie de \(\mathbb{N}\). Mais \(\mathbb{P}\) possède alors un plus grand élément \(n\). Considérons le nombre entier \(N=n!+1\). On a: \(N>n\). D’après la proposition précédente, \(N\) possède un diviseur premier \(p\) différent de \(1\). Ce dernier est nécessairement élément de l’ensemble \(\llbracket 2,n\rrbracket\). \(p\) divise donc aussi \(n!\). Mais alors \(p\) divise \(1\) ce qui est impossible. L’ensemble \(\mathbb{P}\) des nombres premiers est donc infini.
Décomposition en facteurs premiers
Soit \(m\in\mathbb{N}^*\). On considère \(m\) nombre premiers \(p_1,\dots,p_m\in\mathbb{P}\) distincts deux à deux et des entiers naturels non nuls \(\alpha_1,\dots,\alpha_m\). On forme le nombre entier \(p_1^{\alpha_1}\dots p_m^{\alpha_m}\). Alors tout diviseur premier de \(n\) est l’un des \(p_i\) où \(i\in\llbracket 1,m\rrbracket\).
Considérons l’ensemble \(\mathscr A\) des entiers de la forme \(n=p_1^{\alpha_1}\dots p_m^{\alpha_m}\) avec \(m\in\mathbb{N}^*\), \(p_1,\dots,p_m\in\mathbb{P}\) distincts deux à deux et \(\alpha_1,\dots,\alpha_m\in\mathbb{N}^*\) qui admettent un diviseur premier différent de chacun des \(p_i\). La propriété sera prouvée si on montre que \(\mathscr A\) est vide. Supposons que ce n’est pas le cas. Alors comme \(\mathscr
A\) est une partie de \(\mathbb{N}\), \(\mathscr A\) admet un plus petit élément \(n_0=p_1^{\alpha_1}\dots p_m^{\alpha_m}\) et d’après la proposition [tout_entier_admet_diviseur_premier], \(n_0\) admet un diviseur premier \(p\) qui n’est, par définition de \(\mathscr A\), aucun des \(p_i\). L’entier \(p\) divise donc le produit \(p_1.p_1^{\alpha_1-1}\dots p_m^{\alpha_m}\). Les entiers \(p\) et \(p_1\) sont premiers entre eux car premiers. On en déduit, d’après le théorème de Gauss, que \(p\mid p_1^{\alpha_1-1}\dots p_m^{\alpha_m}\). Mais comme \(n_0\) est le plus petit élément de \(\mathscr A\), l’entier \(p_1^{\alpha_1-1}\dots p_m^{\alpha_m}\) n’est pas élément de \(\mathscr
A\) et \(p\) est l’un des \(p_i\) pour \(i\in\llbracket 1,m\rrbracket\) ce qui rentre en contradiction avec l’hypothèse faite sur \(p\). Le lemme est alors prouvé par l’absurde.
(Décomposition en facteurs premiers). Soit un entier \(n \in \mathbb{N}\setminus \{0, 1\}\). Cet entier \(n\) s’écrit de façon unique de la manière suivante : \[n=p_1^{\alpha_1} \dots p_{m}^{\alpha_m}\] où \(m \in\mathbb{N}^*\), \(p_1<\dots<p_m\) sont \(m\) nombres premiers et où \(\alpha_1,\dots,\alpha_m\in\mathbb{N}^*\). Ce résultat se formule aussi sous la forme suivante : \(n\) s’écrit de manière unique, à l’ordre des facteurs près, comme \[n = \prod_{p \in \mathbb{P}} p^{\nu_p(n)}\] où \(\nu_p(n) \in \mathbb{N}\) est appelé la p-valuation de l’entier \(n\).
Tout entier relatif \(n \in \mathbb{Z}\) non nul s’écrit de façon unique sous la forme : \[n = \pm \prod_{p \in \mathbb{P}} p^{\nu_p(\lvert n \rvert )}.\] Pour des entiers \(a, b\in \mathbb{N}^*\), et \(p \in \mathbb{P}\), \[\nu_p(a\times b) = \nu_p(a) + \nu_p(b) \quad \textrm{ et} \quad a \mid b \Rightarrow
\nu_p(a) \leqslant\nu_p(b).\]
(Expression du PGCD et du PPCM à l’aide des facteurs premiers). Soient deux entiers non-nuls \((a, b) \in {\mathbb{N}^*}^2\). Leur décomposition en facteurs premiers s’écrit : \[a = \prod_{p \in \mathbb{P}} p^{\nu_p(a)} \quad
b = \prod_{p \in \mathbb{P}} p^{\nu_p(b)}.\] Alors la décomposition de \(a\wedge b\) et de \(a \vee b\) en facteurs premiers s’écrit : \[a\wedge b = \prod_{p \in \mathbb{P}} p^{\min\{\nu_p(a), \nu_p(b)\}}
\quad a\vee b = \prod_{p \in \mathbb{P}} p^{\max\{\nu_p(a), \nu_p(b)\}}.\]
Posons \(\delta=\prod_{p \in \mathbb{P}} p^{\min\{\nu_p(a), \nu_p(b)\}}\) et montrons que \(\delta=a\wedge b\). Considérons \(a',b'\in\mathbb{N}\) tels que \(a=\delta a'\) et \(b=\delta b'\). D’après la proposition [autres_props_pgcd], on aura montré que \(\delta=a\wedge b\) si et seulement si \(a'\wedge b'=1\). Supposons que ce ne soit pas le cas alors il existe un diviseur \(d\neq 1\) commun à \(a'\) et \(b'\) qu’on peut supposer premier. On a donc : \[d \mid\dfrac{a}{\delta} = \prod_{p \in \mathbb{P}} p^{\nu_p(a) - \min\{\nu_p(a),
\nu_p(b)\} } \quad \textrm{ et} \quad d \mid\dfrac{b}{\delta} = \prod_{p \in \mathbb{P}} p^{\nu_p(b) -
\min\{\nu_p(a),
\nu_p(b)\} }.\] Il vient alors que \(d\) est un facteur de chacun des deux produits ci dessus et que \(\nu_d(a) - \min\{\nu_d(a),
\nu_d(b)\}\geqslant 1\) ainsi que \(\nu_d(b)- \min\{\nu_d(a),
\nu_d(b)\}\geqslant 1\) ce qui constitue une contradiction et prouve par l’absurde que \(a'\wedge b'=1\). La formule pour le pgcd est ainsi démontrée. On procède de même pour le ppcm.
Soit \(n \in \mathbb{N}\) non nul, \(n = \prod_{p \in \mathbb{P}} p^{\nu_p(\lvert n \rvert )}\). Les diviseurs positifs \(d\) de \(n\) s’écrivent \(d = \prod_{p \in \mathbb{P}, p\mid n} p^{\nu_p(\lvert d \rvert )}\), avec \(\forall p \in \mathbb{P}, \nu_p(\lvert d \rvert ) \leqslant\nu_p(\lvert n \rvert )\). Pour chaque \(p \in \mathbb{P}\) qui divise \(n\), on a \(\nu_p(\lvert n \rvert )+1\) choix pour \(\nu_p(\lvert d \rvert )\), à savoir \(0,1,\ldots,\nu_p(\lvert n \rvert )\). On obtient ainsi \[\prod_{p \in \mathbb{P}, p\mid n} (\nu_p(\lvert n \rvert )+1)\] diviseurs positifs de \(n\). Ces diviseurs de \(n\) sont distincts deux à deux à cause du théorème de décomposition en facteurs premiers.
Bibliographie
Barre utilisateur
[ID: 78] [Date de publication: 3 janvier 2022 14:45] [Catégorie(s): Le cours de SUP ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]Commentaires sur le cours
Documents à télécharger
L'article complet