Lemme [division euclidienne] Soient
et
.
Alors il existe
et
tels
que
En outre, et sont uniques.
Exemple 8
On a
ce qui est une division euclidienne.
On a aussi
ce qui n'est pas
une division euclidienne, car le reste d'une division euclidienne
est positif, par définition.
Par contre,
est bien une division euclidienne.
Démonstration. On considère l'ensemble formé des
entiers , où
. Puisque est non nul, l'ensemble
contient des nombres positifs. Donc l'intersection
est non vide. Elle admet donc un élément minimal. Appelons
cet élément et définissons par l'égalité
. Montrons que . Soit
le signe de
(
si et
si ). Si nous avions
, nous pourrions enlever
des deux côtés
de l'égalité pour trouver un nombre
qui appartiendrait encore a
mais qui serait
strictement inférieur à . Contradiction. On a donc bien
.
Montrons l'unicité. Si nous avons
alors
. Puisque et sont positifs
et strictement inférieurs à , il s'ensuit que
. Comme , nous
avons . Or, est un entier positif et
donc et . Par conséquent, nous
avons aussi
.
Définition
Soit un groupe. Un sous-groupe de est
une partie
telle que
a)
L'élément neutre de appartient à .
b)
On a
quels que soient .
c)
On a
quel que soit .
Exemple 9
Si est une sous-groupe de , on définit
une loi
par
Il est clair que est un groupe.
Quel que soit le groupe , les parties
et sont toujours des sous-groupes.
Pour tout
, la partie
est un sous-groupe de
. D'après le théorème
ci-dessus, on obtient ainsi tous les sous-groupes de
.
Théorème
Tout sous-groupe de
est de la forme
pour un
unique au signe près.
Démonstration. Si , alors
et il n'y a rien à démontrer.
Supposons donc que
. Alors l'ensemble des
normes d'éléments de est non-vide.
Soit tel que est non nul et minimal.
Je dis que
. En effet, puisque est un
sous-groupe qui contient , il contient
.
Réciproquement, soit et soit
la division euclidienne de par
(rappelons que ). Si on avait ,
alors serait un élément de
non nul et de norme strictement inférieure
à celle de . Donc nous avons et
appartient à
.
Montrons l'unicité. En effet, si
,
nous avons pour un
et
pour un
. Donc .
Nous avons soit , et alors
et ,
soit et alors et donc
et .
Remarque 10
Si et sont deux sous-groupes
de
, on pose
et
On vérifie aussitôt que est encore un sous-groupe
de
. D'après le théorème, si et
sont deux entiers, il existe un entier unique au
signe près tel que
Nous allons voir que est en fait le plus grand commun
diviseur de et .
Définition
Soient
. On dit que est divisible par
s'il existe
tel que . Dans ce cas, on
dit aussi que est multiple de , que divise ou que est diviseur de . On écrit
.
Exemple 11
Le nombre est divisible par
et !
Le nombre 0 est divisible par tout entier. Par contre
le nombre n'est divisible que par et . En effet,
si on a , alors est un entier non nul et .
Donc .
Supposons . Alors la division euclidienne de
par est bien définie et est divisible par ssi
le reste de la division euclidienne de par s'annule.
Définition
Soient
tels que
. Alors le module
d'un diviseur commun à et est borné par
et il existe donc un plus grand diviseur
commun à et . On le note
PGCD . Les
nombres et sont premiers entre eux si
PGCD . Si , on pose
PGCD .
Lemme [Bézout]
Soient
. Alors
En particulier, on a équivalence entre
i)
Les entiers et sont premiers entre eux.
ii)
On a
.
iii)
L'équation
admet une solution
.
Exemple 12
L'équation est dite équation de Bézout.
Si
, elle admet toujours des solutions
mais pas nécessairement dans
.
Il s'ensuit du lemme que tout diviseur commun
de et divise
PGCD (car il divise
quels que soient
).
Démonstration. Supposons que
avec positif.
Comme
et
, le nombre
est un diviseur commun de et . Donc
PGCD . De l'autre côté,
PGCD divise et et donc
tout élément de
. En particulier,
PGCD divise . Il s'ensuit que
PGCD .
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
, il suffit de multiplier
l'équation par pour conclure que
appartient à
et donc que
.
Lemme [Gauss] Soient
. Si divise
et que et sont premiers entre eux, alors divise .
Démonstration. D'après le lemme de Bézout, il existe
tels que
. Nous multiplions cette galité par pour
obtenir
Puique divise et , il doit diviser .
Définition
Un nombre premier est un entier dont les seuls diviseurs
positifs sont et lui-même.
Exemple 13
Le nombre n'est pas premier.
Les nombres
sont premiers.
Un nombre premier est un entier positif qui admet exactement
deux diviseurs positifs.
Lemme [Euclide] Soit un nombre premier et
.
Si divise alors divise ou divise .
Démonstration. Si ne divise pas , alors
et sont premiers entre eux, car les seuls diviseurs
de sont et lui-même. D'après le lemme de Gauss,
doit alors diviser . De même, si ne divise pas ,
il doit diviser .
Exemple 14
L'affirmation de ce lemme est fausse
si on omet l'hypothèse que est premier. Par exemple
le nombre divise le produit
mais il ne divise ni ni .
Soient et
des nombres premiers.
Montrons que si divise
, alors
pour un . En effet, si , il n'y a rien a démontrer.
Si , et que divise le produit
,
alors d'après le lemme d'Euclide, divise ou
divise
. Dans le premier cas, nous avons
et dans le second pour un , d'après
l'hypothèse de récurrence.
Théorème [Décomposition en facteurs premiers]
Soit un entier et soit
la liste
des nombres premiers (exhaustive et sans répétitions).
Alors il existe des entiers
uniques et
nuls sauf pour un nombre fini d'entre eux tels que
Remarque 15
Comme presque tous les sont
nuls, presque tous les facteurs dans l'écriture
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 , on pose
pour tous les . Si alors soit
est premier, soit pour deux nombres strictement
inférieurs à . Dans le premier cas, il existe
un nombre premier dans la liste et un seul
tel que . On pose pour et .
Dans le second cas, l'hypothèse de récurrence nous
donne les écritures
En multipliant nous trouvons
Montrons l'unicité de l'écriture. Supposons donc que
Montrons que (la démonstration pour les autres
est la même). Nous procédons par récurrence.
Si , alors ne divise pas (sinon il serait
égal à l'un des d'après la remarque ci-dessus).
Donc . Si , alors divise . D'après
la remarque ci-dessus, doit apparaître dans
l'écriture
Donc . En divisant par nous trouvons
et par l'hypothèse de récurrence, il s'ensuit que
. Donc .
Exemple 16
Ce théorème a des conséquences étonnantes. Par exemple,
d'après l'unicité, l'application
est injective ! Donc le cardinal de
est
inférieur à celui de
. (Bien sûr, on sait par ailleurs
que ces deux cardinaux sont égaux).
Si nous avons
comme dans le théorème, alors les diviseurs positifs de
sont exactement les nombres
où
pour tout . En effet, il est clair
que ces nombres divisent . Réciproquement supposons que
et que nous avons les décompositions
En multipliant nous trouvons
Par l'unicité, il s'ensuit que
pour tout
. Donc on a bien
.
Nous déduisons de b) que le nombre de diviseurs de
est égal à
.
Supposons que nous avons les décompositions
Alors il s'ensuit de b), que nous avons
PGCD
PPCM
où
PPCM désigne le plus petit commun multiple de
et . On en déduit que