Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger
[
Le forum
|
Le serveur d'exercices
|
Apprendre Latex en ligne
|
Le livre d'or
|
Le formulaire
|
Collaborateurs
|
Mathématiciens
|
Visiteurs
|
Sommaire
]

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
194 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 
La division euclidienne et ses conséquences next up previous contents
suivant: Congruences monter: bad précédent: Construction de à partir   Table des matières

La division euclidienne et ses conséquences


Lemme [division euclidienne] Soient $ a\in{\mbox{\bf Z}}$ et $ b\in{\mbox{\bf Z}}\setminus \{0\}$. Alors il existe $ q\in{\mbox{\bf Z}}$ et $ r\in\{0,1,\ldots, \vert b\vert-1\}$ tels que

$\displaystyle a=qb+r. $

En outre, $ q$ et $ r$ sont uniques.


Exemple 8   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.


Démonstration. On considère l'ensemble $ R$ formé des entiers $ a-p b$, où $ p\in{\mbox{\bf Z}}$. Puisque $ b$ est non nul, l'ensemble $ R$ contient des nombres positifs. Donc l'intersection $ R\cap {\mbox{\bf 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<\vert b\vert$. Soit $ \varepsilon $ le signe de $ b$ ( $ \varepsilon =1$ si $ b>0$ et $ \varepsilon =-1$ si $ b<0$). Si nous avions $ r>\vert b\vert$, nous pourrions enlever $ \varepsilon b$ des deux côtés de l'égalité $ a-q b=r$ pour trouver un nombre

$\displaystyle r-\varepsilon b=a-(q+\varepsilon )b $

qui appartiendrait encore a $ R\cap {\mbox{\bf N}}$ mais qui serait strictement inférieur à $ r$. Contradiction. On a donc bien $ r\in\{0,1,\ldots, \vert b\vert-1\}$.

Montrons l'unicité. Si nous avons

$\displaystyle q b+r= a = q' b+r', $

alors $ (q-q') b=r-r'$. Puisque $ r$ et $ r'$ sont positifs et strictement inférieurs à $ \vert b\vert$, il s'ensuit que $ \vert q-q'\vert \vert b\vert = \vert r-r'\vert< \vert b\vert$. Comme $ \vert b\vert\neq 0$, nous avons $ \vert q-q'\vert<1$. Or, $ \vert q-q'\vert$ est un entier positif et donc $ \vert q-q'\vert=0$ et $ q=q'$. Par conséquent, nous avons aussi $ r=a-q b=a-q' b=r'$. $ \surd$

Définition Soit $ (G,*)$ un groupe. Un sous-groupe de $ (G,*)$ est une partie $ H\subset G$ telle que

a)
L'élément neutre $ e$ de $ G$ appartient à $ H$.
b)
On a $ h * h'\in H$ quels que soient $ h,h'\in H$.
c)
On a $ h^{-1}\in H$ quel que soit $ h\in H$.

Exemple 9   Si $ H$ est une sous-groupe de $ (G,*)$, on définit une loi $ *_H: H \times H \rightarrow H$ par

$\displaystyle 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{\mbox{\bf Z}}$, la partie

$\displaystyle n{\mbox{\bf Z}}=\{ nx \; \vert \; x\in{\mbox{\bf Z}}\} $

est un sous-groupe de $ ({\mbox{\bf Z}},+)$. D'après le théorème ci-dessus, on obtient ainsi tous les sous-groupes de $ ({\mbox{\bf Z}},+)$.

Théorème Tout sous-groupe $ H$ de $ ({\mbox{\bf Z}},+)$ est de la forme $ H=n{\mbox{\bf Z}}$ pour un $ n\in{\mbox{\bf Z}}$ unique au signe près.


Démonstration. Si $ H=\{0\}$, alors $ H= 0{\mbox{\bf Z}}$ et il n'y a rien à démontrer. Supposons donc que $ H \neq \{0\}$. Alors l'ensemble des normes $ \vert x\vert>0$ d'éléments de $ H$ est non-vide. Soit $ n\in H$ tel que $ \vert n\vert$ est non nul et minimal. Je dis que $ H=n{\mbox{\bf Z}}$. En effet, puisque $ H$ est un sous-groupe qui contient $ n$, il contient $ n{\mbox{\bf 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{\mbox{\bf Z}}$.

Montrons l'unicité. En effet, si $ n{\mbox{\bf Z}}=n'{\mbox{\bf Z}}$, nous avons $ n= xn'$ pour un $ x\in{\mbox{\bf Z}}$ et $ n'=x'n$ pour un $ x'\in{\mbox{\bf Z}}$. Donc $ n=xx'n$. Nous avons soit $ n=0$, et alors $ n{\mbox{\bf Z}}=\{0\}$ et $ n'=0$, soit $ n\neq 0$ et alors $ 1=xx'$ et donc $ x=\pm 1$ et $ n'=\pm n$.$ \surd$

Remarque 10   Si $ H$ et $ H'$ sont deux sous-groupes de $ ({\mbox{\bf Z}},+)$, on pose

$\displaystyle H+H'=\{ x+x'\; \vert \; x\in H$    et $\displaystyle x'\in H'\}. $

On vérifie aussitôt que $ H+H'$ est encore un sous-groupe de $ ({\mbox{\bf 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

$\displaystyle a{\mbox{\bf Z}}+ b{\mbox{\bf Z}}= c{\mbox{\bf Z}}. $

Nous allons voir que $ c$ est en fait le plus grand commun diviseur de $ a$ et $ b$.

Définition Soient $ a,b\in{\mbox{\bf Z}}$. On dit que $ a$ est divisible par $ b$ s'il existe $ q\in{\mbox{\bf 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\vert b$.

Exemple 11   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/\vert b\vert$ 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.

Définition Soient $ a,b\in{\mbox{\bf Z}}$ tels que $ (a,b)\neq (0,0)$. Alors le module d'un diviseur commun à $ a$ et $ b$ est borné par $ \max(\vert a\vert,\vert b\vert)$ et il existe donc un plus grand diviseur commun à $ a$ et $ b$. On le note PGCD $ (a,b)$. Les nombres $ a$ et $ b$ sont premiers entre eux si PGCD $ (a,b)=1$. Si $ a=b=0$, on pose PGCD $ (a,b)=0$.

Lemme [Bézout] Soient $ a,b\in{\mbox{\bf Z}}$. Alors

$\displaystyle a {\mbox{\bf Z}}+ b {\mbox{\bf Z}}= \mbox{PGCD }(a,b) {\mbox{\bf Z}}. $

En particulier, on a équivalence entre
i)
Les entiers $ a$ et $ b$ sont premiers entre eux.
ii)
On a $ a{\mbox{\bf Z}}+ b{\mbox{\bf Z}}= {\mbox{\bf Z}}$.
iii)
L'équation $ ax + by =1$ admet une solution $ (x,y)\in{\mbox{\bf Z}}^2$.

Exemple 12   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{\mbox{\bf Q}}^2$ mais pas nécessairement dans $ {\mbox{\bf Z}}^2$. Il s'ensuit du lemme que tout diviseur commun $ c$ de $ a$ et $ b$ divise PGCD $ (a,b)$ (car il divise $ ax+by$ quels que soient $ x,y\in{\mbox{\bf Z}}$).


Démonstration. Supposons que $ a{\mbox{\bf Z}}+b{\mbox{\bf Z}}=c{\mbox{\bf Z}}$ avec $ c$ positif. Comme $ a\in c{\mbox{\bf Z}}$ et $ b\in c{\mbox{\bf Z}}$, le nombre $ c$ est un diviseur commun de $ a$ et $ b$. Donc $ c\leq$   PGCD $ (a,b)$. De l'autre côté, PGCD $ (a,b)$ divise $ a$ et $ b$ et donc tout élément de $ a{\mbox{\bf Z}}+ b{\mbox{\bf Z}}$. En particulier, PGCD $ (a,b)$ divise $ c$. Il s'ensuit que $ c=$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{\mbox{\bf Z}}$, il suffit de multiplier l'équation $ ax + by =1$ par $ z$ pour conclure que $ z=a(zx)+b(zy)$ appartient à $ a{\mbox{\bf Z}}+ b{\mbox{\bf Z}}$ et donc que $ {\mbox{\bf Z}}=a{\mbox{\bf Z}}+b{\mbox{\bf Z}}$.$ \surd$

Lemme [Gauss] Soient $ a,b,c\in{\mbox{\bf Z}}$. Si $ a$ divise $ bc$ et que $ a$ et $ b$ sont premiers entre eux, alors $ a$ divise $ c$.


Démonstration. D'après le lemme de Bézout, il existe $ x,y\in{\mbox{\bf Z}}$ tels que $ ax + by =1$. Nous multiplions cette galité par $ c$ pour obtenir

$\displaystyle acx+bcy=c. $

Puique $ a$ divise $ acx$ et $ bcy$, il doit diviser $ axc+bcy=c$.$ \surd$

Définition Un nombre premier est un entier $ >1$ dont les seuls diviseurs positifs sont $ 1$ et lui-même.

Exemple 13   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.

Lemme [Euclide] Soit $ p$ un nombre premier et $ a,b\in{\mbox{\bf Z}}$. Si $ p$ divise $ ab$ alors $ p$ divise $ a$ ou $ p$ divise $ b$.


Démonstration. 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$.$ \surd$

Exemple 14   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.

Théorème [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{\mbox{\bf N}}$ uniques et nuls sauf pour un nombre fini d'entre eux tels que

$\displaystyle n=p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots . $


Remarque 15   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.


Démonstration. 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

$\displaystyle n'$ $\displaystyle =$ $\displaystyle p_1^{m'_1} p_2^{m'_2} \cdots$  
$\displaystyle n''$ $\displaystyle =$ $\displaystyle p_1^{m''_1} p_2^{m''_2} \cdots .$  

En multipliant nous trouvons

$\displaystyle n = p_1^{m'_1+m''_1} p_2^{m'_2+m''_2} \cdots . $

Montrons l'unicité de l'écriture. Supposons donc que

$\displaystyle 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

$\displaystyle n = p_1^{m'_1} p_2^{m'_2} \cdots . $

Donc $ m'_1>0$. En divisant par $ p_1$ nous trouvons

$\displaystyle 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$. $ \surd$

Exemple 16   Ce théorème a des conséquences étonnantes. Par exemple, d'après l'unicité, l'application

$\displaystyle {\mbox{\bf N}}\times{\mbox{\bf N}}\times{\mbox{\bf N}}\rightarrow... ...ox{\bf 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 $ {\mbox{\bf N}}\times{\mbox{\bf N}}\times{\mbox{\bf N}}$ est inférieur à celui de $ {\mbox{\bf N}}$. (Bien sûr, on sait par ailleurs que ces deux cardinaux sont égaux).

Si nous avons

$\displaystyle 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

$\displaystyle n'=p_1^{m'_1} p_2^{m'_2} p_3^{m'_3} \cdots $

où $ 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
$\displaystyle n'$ $\displaystyle =$ $\displaystyle p_1^{m'_1} p_2^{m'_2} \cdots$  
$\displaystyle n''$ $\displaystyle =$ $\displaystyle p_1^{m''_1} p_2^{m''_2} \cdots .$  

En multipliant nous trouvons

$\displaystyle 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

$\displaystyle n$ $\displaystyle =$ $\displaystyle p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots$  
$\displaystyle n'$ $\displaystyle =$ $\displaystyle p_1^{m'_1} p_2^{m'_2} p_3^{m'_3} \cdots .$  

Alors il s'ensuit de b), que nous avons
PGCD $\displaystyle (n,n')$ $\displaystyle =$ $\displaystyle p_1^{\min(m_1, m'_1)} p_2^{\min(m_2, m'_2)} \cdots$  
PPCM $\displaystyle (n,n')$ $\displaystyle =$ $\displaystyle p_1^{\max(m_1, m'_1)} p_2^{\max(m_2, m'_2)} \cdots$  

où PPCM $ (n,n')$ désigne le plus petit commun multiple de $ n$ et $ n'$. On en déduit que

$\displaystyle n\times n' =$   PPCM $\displaystyle (n,n') \times$   PGCD $\displaystyle (n,n'). $

next up previous contents
suivant: Congruences monter: bad précédent: Construction de à partir   Table des matières
Bernhard_Keller
 
 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter
Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page