3. Rappels sur la structure de \(\Z\)#
3.1. Axiomatique de \(\N\)#
L’ensemble des entiers naturels, bien qu’utilisé assez anturellement depuis longtemps a été plus complexe qu’on ne le pensait à formaliser. Il a fallu attendre les travaux de mathématiciens et de logiciens comme Gottlob Fregge et Guiesppe Péano pour voir se développer une théorie complète permettant de construire les entiers naturels, de façon à pouvoir démontrer formellement des propriétés avec.
Ces constructions ne sont plus celles nécessairement utilisées par les mathématiciens de nos jours qui leur préfèrent des conséquences de l’axiomatique de Zermelo et Fraenkel (ZF), mais dont l’accès est plus complexe.
On peut donc retenir la série d’axiome suivant :
L’ensemble des entiers naturels existe
L’ensemble des entiers naturels contient 0
Il existe une fonction strictement croissante \(s\) tel que pour tout élément de \(\N\), \(s(n) \in \N\) (\(s\) est la fonction successeur. Généralement, on prend \(s\colon n \mapsto n+1\))
0 n’a pas de successeur
Toute partie finie non vide de \(\N\) admet une borne supérieure
Si une partie \(A\) de \(\N\) contient \(0\), et si pour \(n \in A\), \(s(n) \in A\), alors \(A = \N\) (principe de récurrence)
Definition 3.1
Soient \(a\) et \(b\) deux entiers naturels, \(b ≠ 0\).
On dit que \(b\) divise \(a\), noté \(b|a\), si et seulement s’il existe \(c \in \N\) tel que \(a = b×c\)
Note
On peut aussi dire que \(a\) est un multiple de \(b\), ou que \(a\) est divisible par \(b\).
Exercise 3.1
\(15\) est-il divisible par \(3\) ?
\(-45\) est-il divisible par \(5\) ?
\(16\) est-il divisible par \(6\) ?
\(15\) est-il divisible par \(3\) ?
Proposition 3.1
\(1\) est diviseur universel, car il divise tout entier.
Si \(a\) est un multiple de \(b\), alors \(\varabs{a} ≥ \varabs{b}\)
Si \(a\) divise \(b\) et \(b\) divise \(a\) alors \(a = ± b\).
Proposition 3.2
Soient \((a,b,c) \in \Z^3\). Si \(a | b\) et \(a | c\), alors \(a\) divise toute combinaison linéaire de \(b\) et \(c\).
Exercise 3.2
Soit \(k \in \Z\). On pose \(a = 9 k +2\) et \(b = 12 k + 1\).
Déterminer les valeurs \(a\) et \(b\) pour \(k \in \{-2,-1,0,1,2,3\}\).
Quels sont les diviseurs communs à \(a\) et \(b\) ?
On cherche à trouver les diviseurs communs potentiels de \(a\) et \(b\). En particulier, un tel diviseur doit aussi diviser une combinaison linéaire.
Donner un multiple commun à 12 et 9.
Utiliser cette information pour écrire une combinaison linéaire permettant d’éliminer \(k\).
En déduire les potentiels multiples communs à \(a\) et \(b\).
Theorem 3.1
Soient \(a \in \Z\) et \(b\in \N*\) deux entiers. Alors il existe un unique couple \((q,r)\) tel que \(a = bq + r,\ 0≤ r < b\).
Proof. *
Soit \(a \in \N\), on peut alors construire \(E = \ensemble{e \in \N} {be > a}\).
Cet ensemble existe et est non vide, car, comme \(b > 0\), on peut prendre \(b = 1\) et \(ba > a\).
Comme \(E\) est non vide, il admet un plus petit élément, qu’on peut noter \(m\). On a donc \(mb > a\) (c’est un élement de \(E\)) et \((m-1)b ≤ a\) cat \(m - 1 \not\in E\) (\(m\) est le plus petit élément).
On a donc \((m-1) b ≤ a < mb\) et on peut poser \(q = m+1\). L’inégalité s’écrit donc $\(q b ≤ a < qb + b\)\( et \)q$ existe.
On en déduit ensuite que \(0 ≤ \underbrace{a - qb}_{r} < b\) et donc \(r\) existe et vérifie l’inégalité \(0 ≤ r < b\).
Soit \(a \in \Z\setminus\N\). On pose alors \(a' = a(1 - b)\) et comme \(b ≥ 1\), on a \(1 - b ≤ 0\). On a alors \(a'\) positif et donc \(a' = bq' + r,\ 0≤ r < b\) d’apèrs ce qui précède.
On a alors \(a(1 - b) = bq' + r,\ 0≤ r < b \implies a = b\underbrace{(q' + a)}_{q} + r,\ 0≤ r < b\) et donc le résultat attendu.
On veut enfin démontrer que le couple \((q,r)\) est unique. Supposons qu’il existe un second couple \((q',r')\) tel que \(a = bq + r,\ 0≤ r < b\) et \(a = bq' + r',\ 0 ≤ r' < b\). On a donc \(b(q - q') = r' - r\).
On a \(0 ≤ r' < b\) et \(-b < -r ≤ 0\), d’où \(-b < r' - r < b\), ce qui s’écrit \(\varabs{ r' - r} < b\).
Or \(b (q - q') = r' -r\) signifie que \(r' - r\) est un multiple de \(b\), ou encore que \(r' - r\) est divisible par \(b\), ce qui n’est pas possible, car les diviseurs d’un nombre doivent être plus petits. On en déduit que \(r' - r = 0\) et donc \(r = r'\), puis, comme \(b ≠ 0\), \(q - q' = 0\) et donc \(q = q'\).
Le couple \((q,r)\) est donc unique.
◻
Definition 3.2
L’écriture \(a = bq + r\) s’appelle division euclidienne de \(a\) par \(b\).
\(a\) est le dividende
\(b\) est le diviseur
\(q\) est le quotient
\(r\) est le reste.
Exercise 3.3
Donner le quotient et le reste de la division de 114 par 8.
Donner le quotient et le reste de la division de -114 par 8.
Solution to Exercise 3.3
On peut donc écrire \(114 = 8×14 + 2\)
On est tenté d’écrire \(-114 = 8×(-14) - 2\), mais cela rompt la contrainte d’avoir un reste positif.
Écrivons \(-2 = 6 - 8\). On a alors \(-114 = 8×(-14) + 6 - 8 = 8×(-15) + 6\). Cette fois, on a bien un reste compris entre \(0\) et \(8\).
Definition 3.3
Soit \(n\) un entier supérieur ou égal à 2 et \(a\) et \(b\) deux entiers relatifs. On dit que \(a\) est congru à \(b\) si et seulement si \(a - b\) est divisible par \(n\). On note alors \(a \equiv b \mod 7\) ou encore \(a \equiv b (n)\) ou encore \(a \equiv b [n]\).
Example 3.1
\(57 \equiv 15 \mod 7\) \(41 \equiv -4 \mod 9\)
Proposition 3.3
Un nombre est congru à son reste modulo le diviseur.
Proof. Soient \(a\) et \(n\) deux entiers, \(n ≠ 0\). On peut écrire la division de \(a\) par \(n\) : \(a = nq + r\), ce qui donne \(a - r = nq\). \(n\) divise donc \(a -r\), donc \(a \equiv r \mod n\). ◻
Proposition 3.4
Soient \(a, b\) et \(c\) trois entiers relatifs. On a
réflexivité \(a \equiv a \mod n\)
symétrie \(a \equiv b \mod n \iff b \equiv a \mod n\)
transitivité \(a \equiv b \mod n\) et \(b \equiv c \mod n \implies a \equiv c \mod n\).
Proof. 1. Évident
Évident
Évident
◻
Exercise 3.4
Soient \(f\) et \(g\) deux fonctions dérivables sur \(I\). On définit la relation \(f \sim g\) par $\(\forall x \in I,\ f'(x) = g'(x) .\)\( Montrer que \)\sim$ est une relation d’équivalence.
Theorem 3.2
La relation \(⋅ \equiv ⋅ \mod n\) est compatible avec l’addition et la soustraction.
Proof. Soit \(a, b, c\) et \(d\) quatre nombres entiers relatifs tels que \(a \equiv b \mod n\) et \(c \equiv d \mod n\).
On a alors \(a - b = qn\) et \(c - d = q'n\) et donc \(a + c - (b + d) = (q + q')n\), ce qui s’écrit \(a + c \equiv b + d \mod n\). ◻
Corollary 3.1
\(a \equiv b \mod n \iff a - b \equiv 0 \mod n\)
Proof. Une conséquence immédiate du théorème précédent. ◻
Proposition 3.5
Dire que \(a \equiv b \mod n\) revient à dire qu’ils ont le même reste dans la division par \(n\).
Proof. Notons \(r_{a,n}\) le reste de la division de \(a\) par \(n\) et \(r_{b,n}\) le reste de la division de \(b\) par \(n\).
\(a \equiv r_{a,n} \mod n\) et \(b \equiv r_{b,n} \mod n\), avec \(0 ≤ r_{a,n} < n\) et \(0 ≤ r_{b,n} < n\). On a donc \(r_{a,n} \equiv r_{b,n} \mod n\), autrement dit \(r_{a,n} - r_{b,n}\) est divisible par \(n\). Or \(\varabs{r_{a,n} - r_{b,n}} < n\), donc \(\varabs{r_{a,n} - r_{b,n}} = 0\) et \(r_{a,n} = r_{b,n}\). ◻
Exercise 3.5
Démontrer la remarque
Theorem 3.3
La relation \(⋅ \equiv ⋅ \mod n\) est compatible avec la multiplication.
Proof. Soit \(n\) un entier naturel supérieur ou égal à 2. Soient \(a, b, c\) et \(d\) quatre entiers relatifs tels que \(a \equiv b \mod n\) et \(c \equiv d \mod n\).
\(a \equiv b \mod n \iff a - b = nq\)
\(c \equiv d \mod n \iff c - d = nq'\)
\(ac - bd = ac - bc + bc - bd = (a - b)c + b(c - d) = nqc + bnq' = n(qc + bq')\), donc \(ac \equiv bd \mod n\). ◻
Corollary 3.2
Soit \(n ≥ 2\) un entier naturel, \(a\) et \(b\) deux entiers relatifs et \(k\) un entier naturel.
\(a \equiv b \mod n \implies a^k \equiv b^k \mod n\)
Proof. Par récurrence sur \(k\) en utilisant le théorème précédent. ◻
Definition 3.4
On note \(\sfrac{\Z}{n\Z}\) l’ensemble des restes de la division par \(n\).
Proposition 3.6
L’ensemble \(\sfrac{\Z}{n\Z}\) est un groupe pour l’addition.
L’ensemble \(\sfrac{\Z}{n\Z}\) est un groupe pour la multiplication.
4. PGCD, théorèmes de Bézout et Gauss#
4.1. PGCD et PPCM#
Definition 4.1
Soient deux nombres entiers relatifs \(a\) et \(b\). On appelle plus grand commun divisiseur et note \(\pgcd{a b}\) l’unique nombre tel que \(d\Z = a\Z + b\Z\). On note aussi \(a \wedge b\).
Proof. existence et unicité. Existence
\(a\Z\) est l’ensemble des multiples de \(a\), c’est à dire les nombres qui s’écrivent sous la forme \(k a,\ k \in \Z\).
L’ensemble \(a\Z + b\Z\) est l’ensemble des nombres de la forme \(ka + k'b, k \in \Z,\ k' \in \Z\). On remarque que \(a\Z + b\Z \subset\Z\) et \(a\Z + b\Z ≠ ø\) car \(0 \in a\Z + b\Z\).
Les ensembles \(a\Z\) et \(b\Z\) sont des sous groupes de \(\Z\), essentiellement car stable pour l’opération d’addition.
Soient \(A\) et \(B\) deux éléments de \(a\Z + b\Z\). \(A\) s’écrit par exemple \(A = k_Aa + b_Ab\) et \(B = k_Ba + k_Bb\). \(B - A = k_B a + k_B b - k_A a - k_a B = (k_B - k_A) a + (k_B - k_A)b \in a\Z + b\Z\), donc l’ensemble \(a\Z + b\Z\) est stable et, avec les propriétés précédentes, c’est un (sous) groupe de \(\Z\).
Comme \(a\Z + b\Z\) est un sous groupe de \(\Z\), on peut étudier plus précisément.
\(a\Z + b\Z = \{0\} = 0\Z\) est un sous groupe de la forme \(d\Z\).
\(a\Z + b\Z ≠ \{0\}\), alors prenons \(h \in a\Z + b\Z\), et supposons \(h > 0\) (quitte à prendre \(-h\) sinon).
Prenons \(d\) le plus petit élément positif de \(a\Z + b\Z\), qui existe, en vertu des axiomes. On a alors \(h = d q + r,\ 0 ≤r<d\). Mais \(h \in a\Z + b\Z\) et \(d \in a\Z + b\Z \implies dq \in a\Z + b\Z\) et donc \(r = 0\). Donc \(h\) s’écrit \(dq\) et on a bien \(a\Z + b\Z \subset d\Z\). Comme \(d \in a\Z + b\Z\), on a aussi \(d\Z \subset a\Z + b\Z\) et donc l’égalité.
On a donc montré l’existence de \(d\) tel que \(d\Z = a\Z + b\Z\).
Unicité
On suppose que \(d \Z = d'\Z\). Dans ce cas, \(d \mid d'\) \(d' \mid d\) et donc \(d = d'\). ◻
Proposition 4.1
\(\forall (a,b) \in \Z^2,\ a\wedge b = b \wedge a\).
\(\forall a \in \Z,\ a\wedge 0 = \abs{a}\)
Si \(d = a \wedge b\), alors \(d \mid a\) et \(d \mid b\). Et \(d\) est le plus grand diviseur.