Image
Nous construisons maintenant la division euclidienne de deux entiers et établissons les premières propriétés de cette opération.

La division euclidienne et ses conséquences

(division euclidienne).
Soient \(a\in{ \mathbb Z}\) et \(b\in{ \mathbb Z}\setminus \{0\}\). Alors il existe \(q\in{ \mathbb Z}\) et \(r\in\{0,1,\ldots, |b|-1\}\) tels que \[a=qb+r.\] En outre, \(q\) et \(r\) sont uniques.
( ).
On a \(15=2\times 7 + 1\) ce qui est une division euclidienne. On a aussi \(-15=(-2)\times 7 + (-1)\) ce qui n’est pas une division euclidienne, car le reste d’une division euclidienne est positif, par définition. Par contre, \(-15=(-3)\times 7+6\) est bien une division euclidienne.
( ).
On considère l’ensemble \(R\) formé des entiers \(a-p\,b\), où \(p\in{ \mathbb Z}\). Puisque \(b\) est non nul, l’ensemble \(R\) contient des nombres positifs. Donc l’intersection \(R\cap {\mathbb N}\) est non vide. Elle admet donc un élément minimal. Appelons \(r\) cet élément et définissons \(q\) par l’égalité \(a-q\,b=r\). Montrons que \(r<|b|\). Soit \(\varepsilon\) le signe de \(b\) (\(\varepsilon=1\) si \(b>0\) et \(\varepsilon=-1\) si \(b<0\)). Si nous avions \(r>|b|\), nous pourrions enlever \(\varepsilon\,b\) des deux côtés de l’égalité \(a-q\,b=r\) pour trouver un nombre \[r-\varepsilon\,b=a-(q+\varepsilon)b\] qui appartiendrait encore a \(R\cap {\mathbb N}\) mais qui serait strictement inférieur à \(r\). Contradiction. On a donc bien \(r\in\{0,1,\ldots, |b|-1\}\). Montrons l’unicité. Si nous avons \[q\,b+r= a = q'\,b+r',\] alors \((q-q')\,b=r-r'\). Puisque \(r\) et \(r'\) sont positifs et strictement inférieurs à \(|b|\), il s’ensuit que \(|q-q'|\,|b| = |r-r'|< |b|\). Comme \(|b|\neq 0\), nous avons \(|q-q'|<1\). Or, \(|q-q'|\) est un entier positif et donc \(|q-q'|=0\) et \(q=q'\). Par conséquent, nous avons aussi \(r=a-q\,b=a-q'\,b=r'\).
(sous-groupe).
Soit \((G,*)\) un groupe. Un sous-groupe de \((G,*)\) est une partie \(H\subset G\) telle que
  • L’élément neutre \(e\) de \(G\) appartient à \(H\).

  • On a \(h * h'\in H\) quels que soient \(h,h'\in H\).

  • On a \(h^{-1}\in H\) quel que soit \(h\in H\).

( ).
  • Si \(H\) est une sous-groupe de \((G,*)\), on définit une loi \(_H: H \times H \rightarrow H\) par \[h *_H h' = h * h'.\] Il est clair que \((H, *_H)\) est un groupe.

  • Quel que soit le groupe \((G,*)\), les parties \(G\) et \(\{e\}\) sont toujours des sous-groupes.

  • Pour tout \(n\in{ \mathbb Z}\), la partie \[n{ \mathbb Z}=\{ nx \; | \; x\in{ \mathbb Z}\}\] est un sous-groupe de \(({ \mathbb Z},+)\). D’après le théorème ci-dessus, on obtient ainsi tous les sous-groupes de \(({ \mathbb Z},+)\).

( ).
Tout sous-groupe \(H\) de \(({ \mathbb Z}, +)\) est de la forme \(H=n{ \mathbb Z}\) pour un \(n\in{ \mathbb Z}\) unique au signe près.
( ).

Si \(H=\{0\}\), alors \(H= 0{ \mathbb Z}\) et il n’y a rien à démontrer. Supposons donc que \(H \neq \{0\}\). Alors l’ensemble des normes \(|x|>0\) d’éléments de \(H\) est non-vide. Soit \(n\in H\) tel que \(|n|\) est non nul et minimal. Je dis que \(H=n{ \mathbb Z}\). En effet, puisque \(H\) est un sous-groupe qui contient \(n\), il contient \(n{ \mathbb Z}\). Réciproquement, soit \(a\in H\) et soit \(a=qn+r\) la division euclidienne de \(a\) par \(n\) (rappelons que \(n\neq 0\)). Si on avait \(r\neq 0\), alors \(r=q-qn\) serait un élément de \(H\) non nul et de norme strictement inférieure à celle de \(n\). Donc nous avons \(r=0\) et \(a=qn\) appartient à \(n{ \mathbb Z}\).

Montrons l’unicité. En effet, si \(n{ \mathbb Z}=n'{ \mathbb Z}\), nous avons \(n= xn'\) pour un \(x\in{ \mathbb Z}\) et \(n'=x'n\) pour un \(x'\in{ \mathbb Z}\). Donc \(n=xx'n\). Nous avons soit \(n=0\), et alors \(n{ \mathbb Z}=\{0\}\) et \(n'=0\), soit \(n\neq 0\) et alors \(1=xx'\) et donc \(x=\pm 1\) et \(n'=\pm n\).
( ).
Si \(H\) et \(H'\) sont deux sous-groupes de \(({ \mathbb Z}, +)\), on pose \[H+H'=\{ x+x'\; | \; x\in H \mbox{ et } x'\in H'\}.\] On vérifie aussitôt que \(H+H'\) est encore un sous-groupe de \(({ \mathbb Z}, +)\). D’après le théorème, si \(a\) et \(b\) sont deux entiers, il existe un entier \(c\) unique au signe près tel que \[a{ \mathbb Z}+ b{ \mathbb Z}= c{ \mathbb Z}.\] Nous allons voir que \(c\) est en fait le plus grand commun diviseur de \(a\) et \(b\).
(divisible).
Soient \(a,b\in{ \mathbb Z}\). On dit que \(a\) est divisible par \(b\) s’il existe \(q\in{ \mathbb Z}\) tel que \(a=q\,b\). Dans ce cas, on dit aussi que \(a\) est multiple de \(b\), que \(b\) divise \(a\) ou que \(b\) est diviseur de \(a\). On écrit \(a|b\).
( ).
  • Le nombre \(15\) est divisible par \(1,3,5,15, -1,-3,-5\) et \(-15\) !

  • Le nombre \(0\) est divisible par tout entier. Par contre le nombre \(1\) n’est divisible que par \(1\) et \(-1\). En effet, si on a \(1=q b\), alors \(1/|b|\) est un entier non nul et \(\leq 1\). Donc \(b=\pm 1\).

  • Supposons \(b\neq 0\). Alors la division euclidienne de \(a\) par \(b\) est bien définie et \(a\) est divisible par \(b\) ssi le reste de la division euclidienne de \(a\) par \(b\) s’annule.

(plus grand diviseur commun).
Soient \(a,b\in{ \mathbb Z}\) tels que \((a,b)\neq (0,0)\). Alors le module d’un diviseur commun à \(a\) et \(b\) est borné par \(\max(|a|,|b|)\) et il existe donc un plus grand diviseur commun à \(a\) et \(b\). On le note \(\mbox{PGCD}(a,b)\). Les nombres \(a\) et \(b\) sont premiers entre eux si \(\mbox{PGCD}(a,b)=1\). Si \(a=b=0\), on pose \(\mbox{PGCD}(a,b)=0\).
(Bézout).
Soient \(a,b\in{ \mathbb Z}\). Alors \[a\,{ \mathbb Z}+ b\,{ \mathbb Z}= \mbox{PGCD}(a,b) \,{ \mathbb Z}.\] En particulier, on a équivalence entre
  • Les entiers \(a\) et \(b\) sont premiers entre eux.

  • On a \(a{ \mathbb Z}+ b{ \mathbb Z}= { \mathbb Z}\).

  • L’équation \(ax + by =1\) admet une solution \((x,y)\in{ \mathbb Z}^2\).

( ).
  • L’équation \(ax+by=1\) est dite équation de Bézout. Si \((a,b)\neq (0,0)\), elle admet toujours des solutions \((x,y)\in{\mathbb Q}^2\) mais pas nécessairement dans \({ \mathbb Z}^2\).

  • Il s’ensuit du lemme que tout diviseur commun \(c\) de \(a\) et \(b\) divise \(\mbox{PGCD}(a,b)\) (car il divise \(ax+by\) quels que soient \(x,y\in{ \mathbb Z}\)).

( ).

Supposons que \(a{ \mathbb Z}+b{ \mathbb Z}=c{ \mathbb Z}\) avec \(c\) positif. Comme \(a\in c{ \mathbb Z}\) et \(b\in c{ \mathbb Z}\), le nombre \(c\) est un diviseur commun de \(a\) et \(b\). Donc \(c\leq \mbox{PGCD}(a,b)\). De l’autre côté, \(\mbox{PGCD}(a,b)\) divise \(a\) et \(b\) et donc tout élément de \(a{ \mathbb Z}+ b{ \mathbb Z}\). En particulier, \(\mbox{PGCD}(a,b)\) divise \(c\). Il s’ensuit que \(c=\mbox{PGCD}(a,b)\).

Il est ainsi clair que i) est équivalent à ii). Il est aussi clair que i) implique iii). Réciproquement, si iii) est vérifié et \(z\in{ \mathbb Z}\), il suffit de multiplier l’équation \(ax+by=1\) par \(z\) pour conclure que \(z=a(zx)+b(zy)\) appartient à \(a{ \mathbb Z}+b{ \mathbb Z}\) et donc que \({ \mathbb Z}=a{ \mathbb Z}+b{ \mathbb Z}\).
(Gauss).
Soient \(a,b,c\in{ \mathbb Z}\). Si \(a\) divise \(bc\) et que \(a\) et \(b\) sont premiers entre eux, alors \(a\) divise \(c\).
( ).
D’après le lemme de Bézout, il existe \(x,y\in{ \mathbb Z}\) tels que \(ax+by=1\). Nous multiplions cette ǵalité par \(c\) pour obtenir \[acx+bcy=c.\] Puique \(a\) divise \(acx\) et \(bcy\), il doit diviser \(axc+bcy=c\).
( ).
Un nombre premier est un entier \(>1\) dont les seuls diviseurs positifs sont \(1\) et lui-même.
( ).
  • Le nombre \(1\) n’est pas premier.

  • Les nombres \(2,3,5 \ldots\) sont premiers.

  • Un nombre premier est un entier positif qui admet exactement deux diviseurs positifs.

(Euclide).
Soit \(p\) un nombre premier et \(a,b\in{ \mathbb Z}\). Si \(p\) divise \(ab\) alors \(p\) divise \(a\) ou \(p\) divise \(b\).
( ).
Si \(p\) ne divise pas \(a\), alors \(a\) et \(p\) sont premiers entre eux, car les seuls diviseurs de \(p\) sont \(1\) et lui-même. D’après le lemme de Gauss, \(p\) doit alors diviser \(b\). De même, si \(p\) ne divise pas \(b\), il doit diviser \(a\).
( ).
  • L’affirmation de ce lemme est fausse si on omet l’hypothèse que \(p\) est premier. Par exemple le nombre \(3\times 5\) divise le produit \((2\times 3)\times (5\times 7)\) mais il ne divise ni \(2\times 3\) ni \(5\times 7\).

  • Soient \(p\) et \(p_1, \ldots, p_r\) des nombres premiers. Montrons que si \(p\) divise \(p_1\cdots p_r\), alors \(p=p_i\) pour un \(i\). En effet, si \(r=1\), il n’y a rien a démontrer. Si \(r>1\), et que \(p\) divise le produit \(p_1\times (p_2\cdots p_r)\), alors d’après le lemme d’Euclide, \(p\) divise \(p_1\) ou \(p\) divise \(p_2\cdots p_r\). Dans le premier cas, nous avons \(p=p_1\) et dans le second \(p=p_i\) pour un \(i\geq 2\), d’après l’hypothèse de récurrence.

(Décomposition en facteurs premiers).
Soit \(n\geq 1\) un entier et soit \(p_1, p_2 \ldots\) la liste des nombres premiers (exhaustive et sans répétitions). Alors il existe des entiers \(m_i\in{\mathbb N}\) uniques et nuls sauf pour un nombre fini d’entre eux tels que \[n=p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots .\]
( ).
Comme presque tous les \(m_i\) sont nuls, presque tous les facteurs dans l’écriture \(p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots\) valent un. Il s’agit donc en effet d’un produit avec un nombre fini de facteurs.
( ).
Montrons l’existence de l’écriture par un raisonnement récursif : Si \(n=1\), on pose \(m_i=0\) pour tous les \(i\). Si \(n>1\) alors soit \(n\) est premier, soit \(n=n' n''\) pour deux nombres strictement inférieurs à \(n\). Dans le premier cas, il existe un nombre premier \(p_j\) dans la liste et un seul tel que \(n=p_j\). On pose \(m_i=0\) pour \(i\neq j\) et \(m_j=1\). Dans le second cas, l’hypothèse de récurrence nous donne les écritures \[\begin{aligned} n' & = & p_1^{m'_1} p_2^{m'_2} \cdots \newline n'' & = & p_1^{m''_1} p_2^{m''_2} \cdots .\end{aligned}\] En multipliant nous trouvons \[n = p_1^{m'_1+m''_1} p_2^{m'_2+m''_2} \cdots .\] Montrons l’unicité de l’écriture. Supposons donc que \[n = p_1^{m_1} p_2^{m_2} \cdots = p_1^{m'_1} p_2^{m'_2} \cdots .\] Montrons que \(m_1=m'_1\) (la démonstration pour les autres \(m_i\) est la même). Nous procédons par récurrence. Si \(m_1=0\), alors \(p\) ne divise pas \(n\) (sinon il serait égal à l’un des \(p_i\) d’après la remarque ci-dessus). Donc \(m'_1=0\). Si \(m_1>0\), alors \(p_1\) divise \(n\). D’après la remarque ci-dessus, \(p_1\) doit apparaı̂tre dans l’écriture \[n = p_1^{m'_1} p_2^{m'_2} \cdots .\] Donc \(m'_1>0\). En divisant par \(p_1\) nous trouvons \[p_1^{m_1-1} p_2^{m_2} \cdots = p_1^{m'_1-1} p_2^{m'_2} \cdots .\] et par l’hypothèse de récurrence, il s’ensuit que \(m_1-1=m'_1-1\). Donc \(m_1=m'_1\).
( ).
  • Ce théorème a des conséquences étonnantes. Par exemple, d’après l’unicité, l’application \[{\mathbb N}\times{\mathbb N}\times{\mathbb N}\rightarrow{\mathbb N}\: , \;(m_1, m_2, m_3) \mapsto 2^{m_1} \times 3^{m_2} \times 5^{m_3}\] est injective ! Donc le cardinal de \({\mathbb N}\times{\mathbb N}\times{\mathbb N}\) est inférieur à celui de \({\mathbb N}\). (Bien sûr, on sait par ailleurs que ces deux cardinaux sont égaux).

  • Si nous avons \[n=p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots .\] comme dans le théorème, alors les diviseurs positifs de \(n\) sont exactement les nombres \[n'=p_1^{m'_1} p_2^{m'_2} p_3^{m'_3} \cdots\]\(m'_i\leq m_i\) pour tout \(i\). En effet, il est clair que ces nombres divisent \(n\). Réciproquement supposons que \(n=n' n''\) et que nous avons les décompositions \[\begin{aligned} n' & = & p_1^{m'_1} p_2^{m'_2} \cdots \\ n'' & = & p_1^{m''_1} p_2^{m''_2} \cdots .\end{aligned}\] En multipliant nous trouvons \[n=p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots =p_1^{m'_1+m''_1} p_2^{m'_2+m''_2} \cdots .\ \] Par l’unicité, il s’ensuit que \(m_i=m'_i+m''_i\) pour tout \(i\). Donc on a bien \(m_i\geq m'_i\).

  • Nous déduisons de b) que le nombre de diviseurs de \(n\) est égal à \((m_1+1)\,(m_2+1)\cdots\).

  • Supposons que nous avons les décompositions \[\begin{aligned} n & = & p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots \\ n' & = & p_1^{m'_1} p_2^{m'_2} p_3^{m'_3} \cdots .\end{aligned}\] Alors il s’ensuit de b), que nous avons \[\begin{aligned} \mbox{PGCD}(n,n') & = & p_1^{\min(m_1, m'_1)} p_2^{\min(m_2, m'_2)} \cdots \\ \mbox{PPCM}(n,n') & = & p_1^{\max(m_1, m'_1)} p_2^{\max(m_2, m'_2)} \cdots\end{aligned}\]\(\mbox{PPCM}(n,n')\) désigne le plus petit commun multiple de \(n\) et \(n'\). On en déduit que \[n\times n' = \mbox{PPCM}(n,n') \times \mbox{PGCD}(n,n').\]

Bibliographie


    Barre utilisateur

    [ID: 10] [Date de publication: 25 novembre 2020 13:04] [Catégorie(s): Le cours d'arithmétique ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Bernhard Keller ]




    Commentaires sur le cours

    Documents à télécharger

    La division euclidienne et ses conséquences
    Télécharger Télécharger avec les commentaires

    L'article complet