Terminale C · Leçon 1
Arithmétique
Ce que dit le programme officiel (35 points)
- Entiers relatifs et congruences : anneau ℤ des entiers relatifs
- Multiples d’un entier relatif : notation nℤ (n ∈ ℕ*)
- Sous-groupes de ℤ
- Division euclidienne dans ℕ et ℤ
- Numération décimale et binaire
- Congruence modulo n ; anneau ℤ/nℤ
- Définir un anneau
- Déterminer les multiples d’un entier relatif
- Déterminer les sous-groupes de ℤ
- Déterminer les diviseurs d’un entier relatif
- Écrire un entier dans le système de numération décimal, binaire
- Définir dans ℤ la relation de congruence modulo n (n ∈ ℕ*)
- Utiliser les propriétés de la relation de congruence modulo n (n ∈ ℕ*) pour résoudre des problèmes
- Déterminer l’anneau ℤ/nℤ pour n ∈ ℕ*
- PGCD et PPCM : algorithme d’Euclide
- Propriétés du PGCD et du PPCM
- Nombres premiers entre eux
- Identité de Bézout et théorème de Gauss
- Résolution d’équations du premier degré dans ℤ × ℤ et (ℤ/nℤ) × (ℤ/nℤ)
- Utiliser l’algorithme d’Euclide pour déterminer le PGCD
- Utiliser les propriétés du PGCD et du PPCM pour résoudre des problèmes
- Définir deux nombres premiers entre eux
- Reconnaître et utiliser les théorèmes de Bézout et de Gauss
- Résoudre dans ℤ² des équations du type ax + by = c où a, b et c sont des entiers relatifs
- Résoudre dans ℤ/pℤ des équations et des systèmes de 2 équations à 2 inconnues
- Limite : les théorèmes de Bézout et de Gauss sont énoncés sans démonstration
- Nombres premiers dans ℤ : définition
- Diviseurs premiers d’un entier naturel ; nombre premier et divisibilité
- Corps ℤ/pℤ lorsque p est premier
- Décomposition d’un entier en produit de facteurs premiers : existence et unicité
- Définir un nombre premier dans ℤ
- Utiliser les propriétés sur les nombres premiers pour résoudre des problèmes
- Établir que ℤ/pℤ est un corps lorsque p est premier
- Décomposer un entier en produit de facteurs premiers
- Limite : il s’agit de sortir la notion de corps sans faire de théorie ; la démonstration n’est pas exigible
Source : Programme de mathématiques, classe de Terminale C, ministère des Enseignements secondaires (Niger)
Congruences et restes
Les congruences sont une façon de travailler dans un « monde circulaire » : modulo \(n\), on identifie tous les entiers qui ont le même reste par \(n\). C'est le langage naturel des cycles, des calendriers et des codes.
Soit \(n \in \mathbb{N}^{*}\). On dit que \(a\) et \(b\) sont congrus modulo \(n\), noté \(a \equiv b\ [n]\), si \(n \mid (a - b)\). De façon équivalente, \(a\) et \(b\) ont le même reste dans la division euclidienne par \(n\).
Si \(a \equiv a'\ [n]\) et \(b \equiv b'\ [n]\), alors on peut additionner, soustraire et multiplier membre à membre :
\[ a + b \equiv a' + b'\ [n] \qquad a - b \equiv a' - b'\ [n] \qquad a \times b \equiv a' \times b'\ [n]. \]Par récurrence sur la propriété multiplicative, on obtient aussi la compatibilité avec les puissances entières :
\[ a \equiv a'\ [n] \implies a^k \equiv a'^k\ [n] \quad \text{pour tout } k \in \mathbb{N}. \]La division n'est pas compatible avec les congruences en général. Contre-exemple : \(4 \equiv 10\ [6]\) (car \(6 \mid -6\)), mais si on divise par \(2\), on obtiendrait \(2 \equiv 5\ [3]\), qui est faux (\(3 \nmid -3\)). On peut diviser une congruence par \(k\) uniquement si \(\text{pgcd}(k, n) = 1\), c'est-à-dire si \(k\) est premier avec le module.
Pour trouver le reste de \(a^n\) modulo \(m\), on cherche la période du cycle des restes de \(a^1, a^2, a^3, \ldots\) modulo \(m\). Le procédé : on réduit d'abord \(a\) modulo \(m\), on calcule les puissances successives jusqu'à retrouver \(1\) (ou la valeur de départ), puis on exprime \(n\) en fonction de cette période.
Exemple type Bac. Calculer le reste de \(7^{100}\) dans la division par \(5\).
Étape 1 — Réduction : \(7 \equiv 2\ [5]\), donc \(7^{100} \equiv 2^{100}\ [5]\).
Étape 2 — Cycle des restes de \(2^k\) modulo \(5\) :
\[ 2^1 \equiv 2,\quad 2^2 \equiv 4,\quad 2^3 \equiv 3,\quad 2^4 \equiv 1,\quad 2^5 \equiv 2,\ldots\ [5]. \]La période est \(4\). Étape 3 — Décomposition de l'exposant : \(100 = 4 \times 25\), donc \(2^{100} = (2^4)^{25} \equiv 1^{25} = 1\ [5]\).
Conclusion : le reste de \(7^{100}\) dans la division par \(5\) est \(\mathbf{1}\).
Critère de divisibilité par 9. Puisque \(10 \equiv 1\ [9]\), on a \(10^j \equiv 1\ [9]\) pour tout \(j \ge 0\). Tout entier \(N = a_k \cdot 10^k + \cdots + a_1 \cdot 10 + a_0\) vérifie donc \(N \equiv a_k + \cdots + a_1 + a_0\ [9]\). Ainsi \(9 \mid N\) si et seulement si la somme de ses chiffres est divisible par 9. Application : \(N = 2\,016\), somme des chiffres \(= 9\), donc \(9 \mid 2016\). Vérifié : \(2016 = 9 \times 224\).
Reste de \(3^{2025}\) modulo \(7\). Cycle de \(3^k\) mod 7 : \(3, 2, 6, 4, 5, 1\) (période 6). \(2025 = 6 \times 337 + 3\), donc \(3^{2025} \equiv 3^3 = 27 \equiv 6\ [7]\). Le reste est \(\mathbf{6}\).
Parité de \(n^2 + n\). Quel que soit \(n\), soit \(n \equiv 0\ [2]\) soit \(n \equiv 1\ [2]\). Dans les deux cas, \(n^2 + n = n(n+1)\) est le produit de deux entiers consécutifs, donc \(n^2 + n \equiv 0\ [2]\) : \(n^2 + n\) est toujours pair.
Figure interactive — Horloge modulaire
La roue montre les classes de congruence modulo \(n\). Chaque entier est placé sur la roue selon son reste par \(n\). Deux entiers se trouvent sur la même case si et seulement si ils sont congrus modulo \(n\).
Divisibilité et division euclidienne dans ℤ
Avant d'étudier les nombres premiers ou les congruences, il faut solidifier la notion la plus élémentaire : celle de diviseur. Toute l'arithmétique en découle.
Soit \(a, b \in \mathbb{Z}\). On dit que \(b\) divise \(a\), noté \(b \mid a\), s'il existe un entier \(k \in \mathbb{Z}\) tel que \(a = k b\). On dit alors que \(a\) est un multiple de \(b\).
Si \(b \mid a\) et \(b \mid a'\), alors pour tous entiers \(u, v\), on a \(b \mid (ua + va')\) : la divisibilité se conserve par combinaison linéaire à coefficients entiers. En particulier, elle se conserve par addition et soustraction.
Quelques cas particuliers à mémoriser : \(1\) divise tout entier ; tout entier divise \(0\) ; si \(b \mid a\) et \(a \ne 0\), alors \(|b| \le |a|\). L'ensemble des multiples de \(b\) dans \(\mathbb{Z}\) se note \(b\mathbb{Z}\).
Facile. On a \(3 \mid 12\) car \(12 = 3 \times 4\). On a aussi \(3 \mid (-12)\) car \(-12 = 3 \times (-4)\). En revanche, \(3 \nmid 10\) car il n'existe pas d'entier \(k\) tel que \(10 = 3k\).
Intermédiaire. Montrons que si \(5 \mid a\) et \(5 \mid b\), alors \(5 \mid (2a - 3b)\). On écrit \(a = 5k\) et \(b = 5m\), donc \(2a - 3b = 10k - 15m = 5(2k - 3m)\). C'est bien un multiple de \(5\).
Plus avancé. Montrons que si \(7 \mid (a + 2b)\) et \(7 \mid (3a - b)\), alors \(7 \mid a\) et \(7 \mid b\). On calcule \((a+2b) + 2(3a-b) = 7a\), donc \(7 \mid 7a\), ce qui donne \(7 \mid a\). De même, \(3(a+2b)-(3a-b)=7b\), donc \(7 \mid b\).
Pour tous \(a \in \mathbb{Z}\) et \(b \in \mathbb{Z}^{*}\), il existe un unique couple \((q, r) \in \mathbb{Z} \times \mathbb{N}\) tel que :
\[ a = bq + r \quad \text{avec} \quad 0 \le r < |b|. \]\(q\) est le quotient euclidien et \(r\) le reste euclidien de la division de \(a\) par \(b\).
Le piège classique concerne les entiers négatifs. La règle est simple : on cherche le plus grand multiple de \(b\) qui reste inférieur ou égal à \(a\), de sorte que le reste soit dans \(\{0, 1, \ldots, |b|-1\}\).
Pour diviser \(-37\) par \(5\), on cherche \(q\) tel que \(5q \le -37\) et \(-37 - 5q < 5\). On trouve \(q = -8\) (car \(5 \times (-8) = -40 \le -37\) et \(5 \times (-7) = -35 > -37\)). Alors \(r = -37 - 5\times(-8) = 3\).
\[ -37 = 5 \times (-8) + 3 \quad (0 \le 3 < 5). \]\(127 = 9 \times 14 + 1\) : quotient \(14\), reste \(1\).
\(-100 = 7 \times (-15) + 5\), car \(7 \times (-15) = -105\) et \(-105 + 5 = -100\), avec \(0 \le 5 < 7\). Le quotient est \(-15\), le reste \(5\).
\(28 = 4 \times 7 + 0\) : le reste est \(0\), donc \(4 \mid 28\).
Ne jamais écrire \(-37 = 5 \times (-7) + (-2)\), même si le calcul est juste arithmétiquement. La condition \(r \ge 0\) est violée : \(-2 < 0\). Ce couple \((q, r)\) n'est pas le résultat de la division euclidienne.
Figure interactive — Division euclidienne
La droite des entiers montre graphiquement comment le dividende \(a\) se positionne entre deux multiples consécutifs de \(b\). Le reste \(r\) est la distance entre \(a\) et le multiple inférieur \(bq\).
Sous-groupes de ℤ et notion d'anneau
L'arithmétique étudie l'ensemble \(\mathbb{Z}\) des entiers relatifs muni de ses deux opérations, l'addition et la multiplication. Avant de parler de diviseurs et de congruences, on précise les règles de calcul que ces opérations vérifient : elles font de \(\mathbb{Z}\) un anneau. On décrit ensuite ses sous-groupes, qui sont exactement les ensembles de multiples.
Le groupe \((\mathbb{Z},+)\). L'addition des entiers relatifs possède quatre propriétés : elle est associative, \((a+b)+c=a+(b+c)\) ; elle est commutative, \(a+b=b+a\) ; elle admet un élément neutre, 0, car \(a+0=a\) ; tout entier \(a\) a un opposé \(-a\), tel que \(a+(-a)=0\). On dit que \((\mathbb{Z},+)\) est un groupe commutatif.
Anneau. Un ensemble \(A\) muni d'une addition et d'une multiplication est un anneau lorsque : \((A,+)\) est un groupe commutatif ; la multiplication est associative et possède un élément neutre, noté 1 ; la multiplication est distributive par rapport à l'addition, \(a(b+c)=ab+ac\) et \((b+c)a=ba+ca\). Si de plus \(ab=ba\) pour tous \(a\) et \(b\), l'anneau est dit commutatif.
L'anneau \(\mathbb{Z}\). L'ensemble \(\mathbb{Z}\), muni de l'addition et de la multiplication usuelles, est un anneau commutatif. Il possède deux propriétés particulières :
- il est intègre : si \(ab=0\), alors \(a=0\) ou \(b=0\) ;
- ses seuls éléments inversibles (ceux qui ont un inverse dans \(\mathbb{Z}\) pour la multiplication) sont \(1\) et \(-1\).
Par comparaison, \(\mathbb{N}\) n'est pas un anneau (un entier naturel non nul n'a pas d'opposé dans \(\mathbb{N}\)), tandis que \(\mathbb{Q}\) et \(\mathbb{R}\) en sont, dans lesquels tout élément non nul est inversible.
Multiples. Soit \(n\) un entier relatif. L'ensemble des multiples de \(n\) est noté \(n\mathbb{Z}\) :
\[n\mathbb{Z}=\{nk\ ;\ k\in\mathbb{Z}\}=\{\ldots,-2n,\,-n,\,0,\,n,\,2n,\ldots\}.\]Ainsi \(0\mathbb{Z}=\{0\}\), \(1\mathbb{Z}=\mathbb{Z}\), et \(2\mathbb{Z}\) est l'ensemble des entiers pairs. Comme \(n\) et \(-n\) ont les mêmes multiples, \((-n)\mathbb{Z}=n\mathbb{Z}\) : on peut toujours prendre \(n\) dans \(\mathbb{N}\).
Sous-groupe. Une partie \(H\) de \(\mathbb{Z}\) est un sous-groupe de \((\mathbb{Z},+)\) lorsque :
- \(0\in H\) ;
- si \(x\in H\) et \(y\in H\), alors \(x+y\in H\) (stabilité par addition) ;
- si \(x\in H\), alors \(-x\in H\) (stabilité par passage à l'opposé).
Les deux dernières conditions se résument en une seule : si \(x\in H\) et \(y\in H\), alors \(x-y\in H\).
Exemple fondamental. Pour tout entier \(n\), \(n\mathbb{Z}\) est un sous-groupe de \(\mathbb{Z}\) : \(0=n\times 0\) ; \(nk+nk'=n(k+k')\) ; \(-(nk)=n(-k)\).
Théorème. Les sous-groupes de \((\mathbb{Z},+)\) sont exactement les ensembles \(n\mathbb{Z}\), où \(n\) est un entier naturel. Plus précisément, si \(H\) est un sous-groupe de \(\mathbb{Z}\) différent de \(\{0\}\), alors \(H=n\mathbb{Z}\) où \(n\) est le plus petit élément strictement positif de \(H\).
Démonstration. Soit \(H\) un sous-groupe différent de \(\{0\}\). Il contient un entier \(x\neq 0\), donc aussi \(-x\) : il contient un entier strictement positif. Toute partie non vide de \(\mathbb{N}\) a un plus petit élément ; soit \(n\) le plus petit élément strictement positif de \(H\).
\(n\mathbb{Z}\subset H\). Comme \(n\in H\) et que \(H\) est stable par addition et par passage à l'opposé, tous les multiples de \(n\) sont dans \(H\).
\(H\subset n\mathbb{Z}\). Soit \(x\in H\). La division euclidienne de \(x\) par \(n\) donne \(x=nq+r\) avec \(0\leq r\lt n\). Alors \(r=x-nq\) est la différence de deux éléments de \(H\), donc \(r\in H\). Si \(r\) était strictement positif, ce serait un élément strictement positif de \(H\) plus petit que \(n\), ce qui est impossible. Donc \(r=0\) et \(x=nq\in n\mathbb{Z}\).
Conséquences. Pour deux entiers naturels non nuls \(m\) et \(n\) : \(n\mathbb{Z}\subset m\mathbb{Z}\) si et seulement si \(m\) divise \(n\). L'intersection de deux sous-groupes est un sous-groupe : \(a\mathbb{Z}\cap b\mathbb{Z}\) est l'ensemble des multiples communs à \(a\) et \(b\) ; c'est \(m\mathbb{Z}\), où \(m\) est le plus petit multiple commun strictement positif.
1. Vérifier les trois conditions : \(0\) appartient à \(H\) ; la somme de deux éléments de \(H\) est dans \(H\) ; l'opposé d'un élément de \(H\) est dans \(H\). (Ou : la différence de deux éléments de \(H\) est dans \(H\).)
2. Chercher le plus petit élément strictement positif \(n\) de \(H\). Pour cela, on montre d'une part que \(n\) appartient à \(H\) (en l'écrivant sous la forme voulue), d'autre part que tous les éléments de \(H\) sont des multiples de \(n\).
3. Conclure par le théorème : \(H=n\mathbb{Z}\).
Pour montrer qu'une partie n'est pas un sous-groupe, il suffit d'un contre-exemple : \(0\) absent, ou deux éléments dont la somme sort de la partie, ou un élément dont l'opposé n'y est pas.
Énoncé. Soit \(H=\{6x+10y\ ;\ x\in\mathbb{Z},\ y\in\mathbb{Z}\}\). Montrer que \(H\) est un sous-groupe de \(\mathbb{Z}\), puis le déterminer.
Solution : \(0=6\times 0+10\times 0\in H\). Si \(u=6x+10y\) et \(u'=6x'+10y'\) sont dans \(H\), alors \(u-u'=6(x-x')+10(y-y')\) est encore de cette forme, donc dans \(H\). Ainsi \(H\) est un sous-groupe de \(\mathbb{Z}\) : il existe un entier naturel \(n\) tel que \(H=n\mathbb{Z}\).
Tout élément de \(H\) est pair, car \(6x+10y=2(3x+5y)\) : donc \(H\subset 2\mathbb{Z}\). Par ailleurs \(2=6\times 2+10\times(-1)\) appartient à \(H\), donc tous les multiples de 2 aussi : \(2\mathbb{Z}\subset H\).
Conclusion : \(H=2\mathbb{Z}\). Le plus petit élément strictement positif de \(H\) est 2 : c'est le plus grand diviseur commun à 6 et 10, comme on le verra dans l'étude du PGCD.
Énoncé. a) Déterminer \(4\mathbb{Z}\cap 6\mathbb{Z}\). b) L'ensemble \(4\mathbb{Z}\cup 6\mathbb{Z}\) est-il un sous-groupe de \(\mathbb{Z}\) ? c) Même question pour \(\mathbb{N}\) et pour l'ensemble des entiers impairs. d) A-t-on \(12\mathbb{Z}\subset 4\mathbb{Z}\) ? \(4\mathbb{Z}\subset 12\mathbb{Z}\) ?
Solution : a) Un entier est dans \(4\mathbb{Z}\cap 6\mathbb{Z}\) s'il est multiple à la fois de 4 et de 6. Le plus petit multiple commun strictement positif est 12 (les multiples de 6 sont 6, 12, 18… et 6 n'est pas multiple de 4). Donc \(4\mathbb{Z}\cap 6\mathbb{Z}=12\mathbb{Z}\).
b) Non : 4 et 6 sont dans la réunion, mais leur somme 10 n'est multiple ni de 4 ni de 6. La réunion n'est pas stable par addition.
c) \(\mathbb{N}\) n'est pas un sous-groupe : 3 y est, son opposé \(-3\) n'y est pas. L'ensemble des entiers impairs non plus : il ne contient pas 0, et \(3+5=8\) est pair.
d) 4 divise 12, donc tout multiple de 12 est multiple de 4 : \(12\mathbb{Z}\subset 4\mathbb{Z}\). L'inclusion inverse est fausse : 4 n'est pas multiple de 12.
Figure — Les multiples de 4, de 6 et de 12 sur la droite des entiers
Sur la droite graduée de \(-24\) à 24 : en bleu (ligne du haut) les éléments de \(4\mathbb{Z}\), en or (ligne du milieu) ceux de \(6\mathbb{Z}\), en marine (ligne du bas) les entiers qui sont dans les deux, c'est-à-dire ceux de \(12\mathbb{Z}\). Chaque sous-groupe est formé de points régulièrement espacés et symétriques par rapport à 0 ; l'intersection de deux sous-groupes est encore un sous-groupe.
Énoncé. a) Résoudre dans \(\mathbb{Z}\) l'équation \((x-3)(x+5)=0\), en précisant la propriété utilisée. b) Quels sont les entiers relatifs \(a\) pour lesquels il existe un entier \(b\) tel que \(ab=1\) ? c) L'équation \(2x=1\) a-t-elle une solution dans \(\mathbb{Z}\) ? Que peut-on en déduire ?
Solution : a) L'anneau \(\mathbb{Z}\) est intègre : un produit est nul seulement si l'un des facteurs est nul. Donc \(x-3=0\) ou \(x+5=0\) : les solutions sont \(3\) et \(-5\).
b) Si \(ab=1\), alors \(|a|\times|b|=1\) avec \(|a|\) et \(|b|\) entiers naturels non nuls, donc au moins égaux à 1 ; leur produit ne vaut 1 que si \(|a|=|b|=1\). Les seuls éléments inversibles de \(\mathbb{Z}\) sont donc \(1\) (inverse 1) et \(-1\) (inverse \(-1\)).
c) Non : \(2x\) est pair pour tout entier \(x\), et 1 est impair. L'entier 2 n'a donc pas d'inverse dans \(\mathbb{Z}\) : dans cet anneau, on ne peut pas toujours diviser. C'est précisément ce qui rend l'arithmétique intéressante.
La réunion de deux sous-groupes n'est pas un sous-groupe en général : \(4\mathbb{Z}\cup 6\mathbb{Z}\) contient 4 et 6 mais pas 10. C'est l'intersection qui est toujours un sous-groupe.
Le sens des inclusions. Plus \(n\) est grand, plus \(n\mathbb{Z}\) est petit : \(12\mathbb{Z}\subset 4\mathbb{Z}\) parce que 4 divise 12. L'inclusion des ensembles de multiples va dans le sens contraire de la divisibilité.
Simplifier n'est pas diviser. Dans \(\mathbb{Z}\), de \(ab=ac\) avec \(a\neq 0\) on peut déduire \(b=c\) (par intégrité, car \(a(b-c)=0\)), mais on ne peut pas écrire \(b=\dfrac{c}{a}\) en général : \(\mathbb{Z}\) est un anneau, pas un corps.
Numération décimale et binaire
Nous écrivons les nombres avec dix chiffres parce que nous comptons par paquets de dix. Un ordinateur, lui, ne distingue que deux états et compte par paquets de deux : il écrit tous les entiers avec les seuls chiffres 0 et 1. Les deux écritures reposent sur le même principe, et l'on passe de l'une à l'autre par des divisions euclidiennes.
Base dix (système décimal). Tout entier naturel non nul \(n\) s'écrit d'une seule façon sous la forme
\[n=a_p\times 10^p+a_{p-1}\times 10^{p-1}+\cdots+a_1\times 10+a_0,\]où \(a_0,a_1,\ldots,a_p\) sont des entiers compris entre 0 et 9, avec \(a_p\neq 0\). Ce sont les chiffres de \(n\) : \(a_0\) est le chiffre des unités, \(a_1\) celui des dizaines, etc. Par exemple \(2037=2\times 10^3+0\times 10^2+3\times 10+7\).
Base deux (système binaire). De même, tout entier naturel non nul \(n\) s'écrit d'une seule façon sous la forme
\[n=b_q\times 2^q+b_{q-1}\times 2^{q-1}+\cdots+b_1\times 2+b_0,\]où chaque \(b_i\) vaut 0 ou 1, avec \(b_q=1\). On note alors \(n=\overline{b_q b_{q-1}\ldots b_1 b_0}^{\,2}\). Par exemple \(\overline{1101}^{\,2}=1\times 8+1\times 4+0\times 2+1=13\).
Puissances de 2 à connaître. 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. En base deux, elles s'écrivent 1, 10, 100, 1000… : un 1 suivi de zéros.
Pourquoi l'écriture est unique. Le dernier chiffre \(b_0\) est le reste de la division euclidienne de \(n\) par 2, et les chiffres précédents forment l'écriture du quotient. Le reste et le quotient étant uniques, tous les chiffres le sont.
De la base dix à la base deux : divisions successives par 2. On divise \(n\) par 2 et l'on note le reste (0 ou 1) ; on divise le quotient par 2, et ainsi de suite, jusqu'à obtenir un quotient nul. L'écriture binaire de \(n\) est la suite des restes lus du dernier au premier.
Variante : soustraire des puissances de 2. On retire de \(n\) la plus grande puissance de 2 possible, puis on recommence avec ce qui reste. Les puissances utilisées donnent les chiffres 1, les autres les chiffres 0.
De la base deux à la base dix. On additionne les puissances de 2 qui correspondent aux chiffres 1, le chiffre de droite ayant le rang 0. On peut aussi lire les chiffres de gauche à droite en partant de 0 et en répétant « multiplier par 2, puis ajouter le chiffre ».
Contrôle. Un entier qui s'écrit avec \(k\) chiffres en base deux est compris entre \(2^{k-1}\) et \(2^k-1\).
Figure — Les divisions successives de 45 par 2
À gauche, la suite des quotients : 45, 22, 11, 5, 2, 1, puis 0, où l'on s'arrête. À droite, en or, le reste de chaque division. La flèche bleue indique le sens de lecture : du dernier reste au premier. On lit 1, 0, 1, 1, 0, 1, donc 45 s'écrit 101101 en base deux.
Énoncé. Écrire en base deux les entiers 45 et 100.
Solution : Pour 45, on effectue les divisions successives par 2 : \(45=2\times 22+1\) ; \(22=2\times 11+0\) ; \(11=2\times 5+1\) ; \(5=2\times 2+1\) ; \(2=2\times 1+0\) ; \(1=2\times 0+1\). Les restes, lus du dernier au premier, sont 1, 0, 1, 1, 0, 1 : \(45=\overline{101101}^{\,2}\). Vérification : \(32+8+4+1=45\).
Pour 100, on utilise les puissances de 2 : la plus grande qui ne dépasse pas 100 est 64, et \(100-64=36\) ; puis 32, et \(36-32=4\) ; puis 4, et il ne reste rien. Donc \(100=64+32+4=2^6+2^5+2^2\). Les rangs 6, 5 et 2 portent un 1, les rangs 4, 3, 1 et 0 un 0 : \(100=\overline{1100100}^{\,2}\).
Énoncé. Écrire en base dix les entiers \(\overline{110111}^{\,2}\) et \(\overline{11111111}^{\,2}\).
Solution : \(\overline{110111}^{\,2}=2^5+2^4+0+2^2+2+1=32+16+4+2+1=55\). Autre calcul, de gauche à droite, en multipliant par 2 puis en ajoutant le chiffre suivant : on obtient successivement 1, 3, 6, 13, 27, 55.
\(\overline{11111111}^{\,2}\) est la somme \(1+2+4+\cdots+2^7\) des huit premiers termes d'une suite géométrique de raison 2 : elle vaut \(2^8-1=255\). On peut aussi remarquer que l'entier suivant est \(\overline{100000000}^{\,2}=2^8=256\).
En base deux. Soit \(n\) un entier naturel non nul.
- \(n\) est pair si et seulement si son écriture binaire se termine par 0 ; il est multiple de 4 si elle se termine par 00, multiple de \(2^k\) si elle se termine par \(k\) zéros.
- Multiplier par 2 revient à écrire un 0 à droite ; le quotient de la division euclidienne par 2 s'obtient en effaçant le dernier chiffre.
- L'écriture binaire de \(n\) compte \(k\) chiffres si et seulement si \(2^{k-1}\leq n\lt 2^k\).
En base dix, par les congruences. Comme \(10\equiv 1\;[9]\), on a \(10^k\equiv 1\;[9]\) pour tout \(k\), donc
\[n\equiv a_p+a_{p-1}+\cdots+a_1+a_0\;[9].\]Un entier est congru modulo 9 (et donc modulo 3) à la somme de ses chiffres : il est divisible par 9, ou par 3, si et seulement si cette somme l'est. De même \(10\equiv -1\;[11]\), donc \(10^k\equiv(-1)^k\;[11]\) et
\[n\equiv a_0-a_1+a_2-a_3+\cdots\;[11].\]Un entier est divisible par 11 si et seulement si la somme alternée de ses chiffres, en partant des unités, l'est.
Énoncé. a) Calculer en base deux la somme \(\overline{1011}^{\,2}+\overline{110}^{\,2}\), puis le double de \(\overline{1011}^{\,2}\). b) Combien de chiffres l'écriture binaire de 1000 comporte-t-elle ? L'écrire. c) Sans effectuer de division, donner le reste de 4725 dans la division par 9, puis celui de 2918 dans la division par 11.
Solution : a) On pose l'addition comme en base dix, avec la règle \(1+1=\overline{10}^{\,2}\) (on écrit 0 et l'on retient 1). On trouve \(\overline{1011}^{\,2}+\overline{110}^{\,2}=\overline{10001}^{\,2}\). Vérification en base dix : \(11+6=17\). Le double de \(\overline{1011}^{\,2}\) s'obtient en écrivant un 0 à droite : \(\overline{10110}^{\,2}\), soit 22.
b) \(2^9=512\leq 1000\lt 1024=2^{10}\) : l'écriture binaire de 1000 a 10 chiffres. Comme \(1000=512+256+128+64+32+8\), on obtient \(1000=\overline{1111101000}^{\,2}\). Elle se termine par trois zéros : 1000 est multiple de 8 (et pas de 16).
c) \(4+7+2+5=18\equiv 0\;[9]\) : le reste de 4725 dans la division par 9 est 0, ce nombre est divisible par 9. Pour 2918, la somme alternée à partir des unités est \(8-1+9-2=14\equiv 3\;[11]\) : le reste dans la division par 11 est 3.
Lire les restes dans le mauvais sens. Le premier reste obtenu est le chiffre des unités, donc le chiffre de droite. Pour 45, écrire les restes dans l'ordre où on les trouve donnerait 101101 par hasard (cette écriture se lit de la même façon dans les deux sens) ; pour 100, on obtiendrait 0010011, qui est faux.
Oublier la base. L'écriture « 10 » désigne dix en base dix et deux en base deux ; « 101 » désigne cent un ou cinq. On indique toujours la base lorsqu'elle n'est pas dix.
Utiliser un chiffre interdit. En base deux, les seuls chiffres sont 0 et 1. Une écriture comme \(1021\) ne peut pas être une écriture binaire.
PGCD, PPCM et algorithme d'Euclide
Lorsqu'on veut simplifier une fraction ou savoir si deux entiers partagent un facteur commun, on cherche leur plus grand commun diviseur. L'algorithme d'Euclide est la méthode efficace pour le calculer, quel que soit l'ordre de grandeur des entiers.
Pour \(a, b \in \mathbb{Z}\) non tous nuls, le plus grand commun diviseur \(\text{pgcd}(a, b)\) est le plus grand entier naturel qui divise à la fois \(a\) et \(b\). Le plus petit commun multiple \(\text{ppcm}(a, b)\) est le plus petit entier naturel non nul qui est divisible à la fois par \(a\) et par \(b\).
On dit que \(a\) et \(b\) sont premiers entre eux (ou copremiers) si \(\text{pgcd}(a,b) = 1\). C'est la condition clé pour appliquer le théorème de Gauss et Bézout.
Si \(d = \text{pgcd}(a, b)\), alors \(a/d\) et \(b/d\) sont premiers entre eux. Par ailleurs, \(\text{pgcd}(ka, kb) = k \cdot \text{pgcd}(a, b)\) pour tout entier \(k > 0\).
Si \(a = bq + r\) est la division euclidienne de \(a\) par \(b\), alors :
\[\text{pgcd}(a, b) = \text{pgcd}(b, r).\]En répétant le procédé (on remplace \((a, b)\) par \((b, r)\) à chaque étape), la suite des restes est strictement décroissante et positive, donc elle atteint nécessairement \(0\). Le dernier reste non nul est le PGCD.
On présente les divisions successives en colonnes. À chaque ligne on écrit \(a_k = b_k q_k + r_k\) avec \(0 \le r_k < b_k\), puis on passe à \((a_{k+1}, b_{k+1}) = (b_k, r_k)\). On s'arrête quand \(r_k = 0\).
Calcul de \(\text{pgcd}(252, 198)\) :
\[ \begin{aligned} 252 &= 198 \times 1 + 54 \\ 198 &= 54 \times 3 + 36 \\ 54 &= 36 \times 1 + 18 \\ 36 &= 18 \times 2 + 0 \quad \leftarrow \text{reste nul} \end{aligned} \]Dernier reste non nul : \(\mathbf{18}\). Donc \(\text{pgcd}(252, 198) = 18\). Et \(\text{ppcm}(252, 198) = \dfrac{252 \times 198}{18} = 2772\).
Rapide. \(\text{pgcd}(48, 18)\) : \(48 = 18 \times 2 + 12\) ; \(18 = 12 \times 1 + 6\) ; \(12 = 6 \times 2 + 0\). Donc \(\text{pgcd}(48,18) = 6\).
Intermédiaire. \(\text{pgcd}(1071, 462)\) : \(1071 = 462 \times 2 + 147\) ; \(462 = 147 \times 3 + 21\) ; \(147 = 21 \times 7 + 0\). Donc \(\text{pgcd}(1071, 462) = 21\).
Astuce de vérification. On vérifie que le PGCD trouvé divise bien les deux nombres. Ici : \(252 / 18 = 14\) et \(198 / 18 = 11\). De plus, \(\text{pgcd}(14, 11) = 1\) : les quotients sont bien premiers entre eux.
Figure interactive — Algorithme d'Euclide pas à pas
Choisissez deux entiers et observez la suite des divisions euclidiennes. Chaque barre représente un reste successif. La convergence vers \(0\) révèle le PGCD.
Nombres premiers et décomposition
Les nombres premiers sont les atomes de l'arithmétique : tout entier supérieur à \(1\) se décompose de façon unique en produit de nombres premiers. Cette décomposition éclaire d'un seul coup le PGCD, le PPCM et le nombre de diviseurs.
Un entier \(p \ge 2\) est dit premier s'il admet exactement deux diviseurs positifs : \(1\) et \(p\) lui-même. Un entier \(n \ge 2\) non premier est dit composé.
Pour tester si \(n\) est premier, il suffit de vérifier qu'aucun entier premier \(p \le \sqrt{n}\) ne divise \(n\). En effet, si \(n = ab\) avec \(a \le b\), alors \(a^2 \le ab = n\), donc \(a \le \sqrt{n}\).
Exemple. \(\sqrt{197} \approx 14{,}03\). On teste les premiers \(2, 3, 5, 7, 11, 13\) : aucun ne divise \(197\). Donc \(\mathbf{197}\) est premier.
Contre-exemple. \(221 = 13 \times 17\). \(\sqrt{221} \approx 14{,}9\), et \(13 \le 14{,}9\) divise \(221\) : \(221\) est composé.
On divise successivement par les premiers dans l'ordre croissant (\(2, 3, 5, 7, \ldots\)) jusqu'à ce que le quotient soit \(1\).
\(360 \div 2 = 180\) ; \(180 \div 2 = 90\) ; \(90 \div 2 = 45\) ; \(45 \div 3 = 15\) ; \(15 \div 3 = 5\) ; \(5 \div 5 = 1\). Donc \(360 = 2^3 \times 3^2 \times 5\).
Nombre de diviseurs positifs de \(360\) : \(\tau(360) = (3+1)(2+1)(1+1) = 4 \times 3 \times 2 = \mathbf{24}\).
Il existe une infinité de nombres premiers.
Esquisse de la démonstration d'Euclide. Supposons par l'absurde qu'il n'en existe qu'un nombre fini \(p_1, \ldots, p_k\). Considérons \(N = p_1 p_2 \cdots p_k + 1\). Alors \(N \ge 2\) admet un diviseur premier \(p\). Mais \(p\) ne peut être aucun des \(p_i\) car \(N \equiv 1\ [p_i]\) pour tout \(i\). Contradiction : l'ensemble des premiers ne peut être fini.
Tout entier \(n \ge 2\) s'écrit de façon unique (à l'ordre des facteurs près) comme produit de nombres premiers :
\[ n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r} \qquad (p_1 < p_2 < \cdots < p_r \text{ premiers},\ \alpha_i \ge 1). \]Pour \(a = \prod p_i^{\alpha_i}\) et \(b = \prod p_i^{\beta_i}\) (en complétant par des exposants nuls si nécessaire) :
\[ \text{pgcd}(a,b) = \prod p_i^{\min(\alpha_i,\beta_i)} \qquad \text{ppcm}(a,b) = \prod p_i^{\max(\alpha_i,\beta_i)}. \]Exemple : \(360 = 2^3 \times 3^2 \times 5\) et \(126 = 2 \times 3^2 \times 7\). Alors \(\text{pgcd}(360, 126) = 2^1 \times 3^2 = 18\) et \(\text{ppcm}(360, 126) = 2^3 \times 3^2 \times 5 \times 7 = 2520\).
Crible d'Ératosthène (manuel). Pour lister les premiers jusqu'à 30 : on barre les multiples de \(2, 3, 5\) (car \(\sqrt{30} < 6\)). Il reste : \(2, 3, 5, 7, 11, 13, 17, 19, 23, 29\) — dix nombres premiers.
Nombre de diviseurs. \(n = 2^4 \times 3 \times 5^2\) a \((4+1)(1+1)(2+1) = 30\) diviseurs positifs.
Condition de divisibilité par \(p\) premier. Si \(p\) est premier et \(p \mid ab\), alors \(p \mid a\) ou \(p \mid b\) : c'est une version forte de Gauss, spécifique aux nombres premiers.
Figure interactive — Crible d'Ératosthène
Le crible filtre les nombres composés un premier à la fois. Sélectionnez un premier pour voir ses multiples barrés. Les cases restantes non barrées sont des nombres premiers.
Bézout, Gauss et équations diophantiennes
Pour tous \(a, b \in \mathbb{Z}\), il existe des entiers \(u, v \in \mathbb{Z}\) tels que \(au + bv = \text{pgcd}(a, b)\). En particulier :
\[ \text{pgcd}(a, b) = 1 \iff \exists\, u, v \in \mathbb{Z},\quad au + bv = 1. \]Ce couple \((u, v)\) n'est pas unique : si \((u_0, v_0)\) est une solution, toutes les solutions sont de la forme \(\left(u_0 + \tfrac{b}{d}k,\ v_0 - \tfrac{a}{d}k\right)\) avec \(d = \text{pgcd}(a,b)\) et \(k \in \mathbb{Z}\).
Pour trouver \(u, v\) tels que \(23u + 17v = 1\), on applique d'abord l'algorithme d'Euclide (en notant chaque étape), puis on remonte en sens inverse en exprimant les restes successifs comme combinaisons de \(23\) et \(17\).
Étape 1 — Descente :
\[ \begin{aligned} 23 &= 17 \times 1 + 6 \\ 17 &= 6 \times 2 + 5 \\ 6 &= 5 \times 1 + 1 \\ 5 &= 1 \times 5 + 0 \end{aligned} \]Étape 2 — Remontée :
\[ \begin{aligned} 1 &= 6 - 5 \times 1 \\ &= 6 - (17 - 6 \times 2) \times 1 = 3 \times 6 - 17 \\ &= 3 \times (23 - 17 \times 1) - 17 = 3 \times 23 - 4 \times 17. \end{aligned} \]Donc \(23 \times 3 + 17 \times (-4) = 1\) : un couple de Bézout est \((u, v) = (3, -4)\).
Toujours vérifier le résultat en recalculant \(au + bv\) : \(23 \times 3 + 17 \times (-4) = 69 - 68 = 1\). Cela prend dix secondes et évite les erreurs de signe dans la remontée.
Si \(a \mid bc\) et \(\text{pgcd}(a, b) = 1\), alors \(a \mid c\).
Corollaire : si \(a \mid n\), \(b \mid n\) et \(\text{pgcd}(a, b) = 1\), alors \(ab \mid n\).
Une équation diophantienne est une équation de la forme \(ax + by = c\) cherchée dans \(\mathbb{Z}^2\). Elle admet des solutions si et seulement si \(\text{pgcd}(a, b) \mid c\).
Exemple. Résoudre dans \(\mathbb{Z}^{2}\) : \(5x - 3y = 1\).
Étape 1 — Existence : \(\text{pgcd}(5, 3) = 1\), qui divise \(1\) : des solutions existent.
Étape 2 — Solution particulière : par inspection (ou Euclide), \(5 \times 2 - 3 \times 3 = 10 - 9 = 1\). Donc \((x_0, y_0) = (2, 3)\).
Étape 3 — Solution générale : si \((x, y)\) est solution, alors \(5(x - 2) = 3(y - 3)\). Donc \(3 \mid 5(x-2)\) ; comme \(\text{pgcd}(3,5) = 1\), Gauss donne \(3 \mid (x - 2)\), soit \(x = 2 + 3k\) pour \(k \in \mathbb{Z}\). On substitue : \(y = \dfrac{5x - 1}{3} = \dfrac{5(2+3k)-1}{3} = \dfrac{9+15k}{3} = 3 + 5k\).
\[ \mathcal{S} = \{(2 + 3k,\ 3 + 5k),\ k \in \mathbb{Z}\} \]Application de Gauss. Sachant que \(7 \mid 3n\) et \(\text{pgcd}(7,3)=1\), on conclut par Gauss que \(7 \mid n\). Simple mais puissant.
Équation sans solution. \(6x + 4y = 3\) : \(\text{pgcd}(6, 4) = 2\) et \(2 \nmid 3\), donc cette équation n'a aucune solution entière.
Équation avec second membre non unitaire. Résoudre \(7x + 5y = 11\). Bézout donne \(7 \times 3 + 5 \times (-4) = 1\), donc en multipliant par 11 : \(7 \times 33 + 5 \times (-44) = 11\). Solution particulière \((33, -44)\). Solution générale : \(x = 33 + 5k\), \(y = -44 - 7k\), \(k \in \mathbb{Z}\).
Systèmes linéaires de deux équations à deux inconnues
Rappel de SecondeRéservé aux abonnés Premium et Élève-Classe.
Voir les offresUn système de deux équations linéaires à deux inconnues \(x, y\) s'écrit :
\[ \begin{cases} ax + by = e \\ cx + dy = f \end{cases} \]Résoudre le système, c'est trouver tous les couples \((x,y)\) qui vérifient simultanément les deux équations.
Réservé aux abonnés Premium et Élève-Classe.
Voir les offresRéservé aux abonnés Premium et Élève-Classe.
Voir les offresRésumé
Addition et multiplication associatives et commutatives, 0 et 1 neutres, opposé pour tout entier, distributivité.
\(\mathbb{Z}\) est intègre (\(ab=0\) entraîne \(a=0\) ou \(b=0\)) ; ses seuls inversibles sont \(1\) et \(-1\).
Partie contenant 0, stable par addition et par passage à l'opposé (ou : stable par différence).
Les sous-groupes de \(\mathbb{Z}\) sont les \(n\mathbb{Z}\) ; \(n\) est le plus petit élément strictement positif.
\(n\mathbb{Z}\subset m\mathbb{Z}\) si et seulement si \(m\) divise \(n\).
En base dix, on décompose suivant les puissances de 10 avec des chiffres de 0 à 9 ; en base deux, suivant les puissances de 2 avec les chiffres 0 et 1.
Divisions successives par 2 ; on lit les restes du dernier au premier.
On additionne les puissances de 2 placées sous les chiffres 1 (rang 0 à droite).
\(k\) chiffres en base deux si et seulement si \(2^{k-1}\leq n\lt 2^k\).
\(n\) est congru à la somme de ses chiffres modulo 9 et modulo 3, et à leur somme alternée modulo 11.
\(a = bq + r\) avec \(0 \le r < |b|\). Le reste est toujours positif ou nul, y compris quand \(a < 0\).
Compatibles avec \(+\), \(-\), \(\times\) et les puissances. Pour les grands exposants : chercher la période du cycle des restes. La division ne se simplifie que si \(\text{pgcd}(k, n) = 1\).
\(\text{pgcd}(a,b) = \text{pgcd}(b, r)\). Répéter jusqu'au reste nul. \(\text{pgcd} \times \text{ppcm} = |ab|\).
\(\text{pgcd}(a,b) = 1 \iff \exists\, u, v,\ au + bv = 1\). Si \(a \mid bc\) et \(\text{pgcd}(a,b)=1\), alors \(a \mid c\). Clés des équations diophantiennes.
Tester les premiers jusqu'à \(\sqrt{n}\). Décomposition unique. \(\tau(n) = \prod (\alpha_i + 1)\) diviseurs. \(\text{pgcd}\) et \(\text{ppcm}\) via \(\min\)/\(\max\) des exposants.
Sujet type Bac
On considère les entiers \(a = 357\) et \(b = 231\). Les cinq questions suivantes sont progressives : chaque résultat sert à la suivante.
Question 1 — Division euclidienne. Effectuer la division euclidienne de \(a\) par \(b\). Vérifier le résultat.
On cherche \(q\) et \(r\) tels que \(357 = 231q + r\) avec \(0 \le r < 231\). Le quotient est \(q = 1\) (car \(231 \times 1 = 231 \le 357 < 231 \times 2 = 462\)). Donc \(r = 357 - 231 = 126\).
\[357 = 231 \times 1 + 126 \quad (0 \le 126 < 231)\]Vérification : \(231 + 126 = 357\). Correct.
Question 2 — Algorithme d'Euclide. Calculer \(\text{pgcd}(357, 231)\) par l'algorithme d'Euclide. En déduire \(\text{ppcm}(357, 231)\).
On reprend le reste de la question 1 et on continue :
\[ \begin{aligned} 357 &= 231 \times 1 + 126 \\ 231 &= 126 \times 1 + 105 \\ 126 &= 105 \times 1 + 21 \\ 105 &= 21 \times 5 + 0 \end{aligned} \]Le dernier reste non nul est \(21\), donc \(\text{pgcd}(357, 231) = \mathbf{21}\).
On en déduit :
\[ \text{ppcm}(357, 231) = \frac{357 \times 231}{21} = \frac{82467}{21} = \mathbf{3927}. \]Question 3 — Identité de Bézout. Trouver des entiers \(u, v\) tels que \(357u + 231v = 21\).
Puisque \(\text{pgcd}(357, 231) = 21\), Bézout assure l'existence de \(u, v\). On remonte l'algorithme. On commence par exprimer chaque reste en fonction des précédents :
\[ \begin{aligned} 21 &= 126 - 105 \times 1 \\ &= 126 - (231 - 126) = 2 \times 126 - 231 \\ &= 2(357 - 231) - 231 = 2 \times 357 - 3 \times 231. \end{aligned} \]Donc \(357 \times 2 + 231 \times (-3) = 21\) : un couple de Bézout est \((u, v) = (2, -3)\).
Vérification : \(357 \times 2 - 231 \times 3 = 714 - 693 = 21\). Correct.
Question 4 — Équation diophantienne. Résoudre dans \(\mathbb{Z}^{2}\) l'équation \(357x + 231y = 42\).
Le membre de droite est \(42 = 2 \times 21\). Comme \(\text{pgcd}(357, 231) = 21\) divise \(42\), l'équation admet des solutions.
En multipliant par \(2\) la relation de Bézout \(357 \times 2 + 231 \times (-3) = 21\) : \(357 \times 4 + 231 \times (-6) = 42\). Une solution particulière est \((x_0, y_0) = (4, -6)\).
Solution générale : si \((x, y)\) est solution, \(357(x - 4) + 231(y + 6) = 0\), soit \(357(x-4) = -231(y+6)\). En divisant par \(\text{pgcd}(357,231) = 21\) : \(17(x-4) = -11(y+6)\). Comme \(\text{pgcd}(17, 11) = 1\), Gauss donne \(11 \mid (x-4)\), soit \(x - 4 = 11k\), d'où \(x = 4 + 11k\). Alors \(y + 6 = -17k\), soit \(y = -6 - 17k\).
\[ \mathcal{S} = \{(4 + 11k,\ -6 - 17k),\ k \in \mathbb{Z}\} \]Question 5 — Congruences et grand exposant. Calculer le reste de \(231^{50}\) dans la division par \(17\).
Étape 1 — On réduit \(231\) modulo \(17\) : \(231 = 17 \times 13 + 10\), donc \(231 \equiv 10\ [17]\). Ainsi \(231^{50} \equiv 10^{50}\ [17]\).
Étape 2 — On note que \(10 \equiv -7\ [17]\), donc \(10^{50} \equiv (-7)^{50} = 7^{50}\ [17]\) (l'exposant est pair).
Étape 3 — Cycle de \(7^k\) modulo \(17\) (le théorème de Fermat donne la période divisant \(16\)) : \(7^1 \equiv 7\), \(7^2 \equiv 49 \equiv 15 \equiv -2\), \(7^4 \equiv (-2)^2 = 4\), \(7^8 \equiv 16 \equiv -1\), \(7^{16} \equiv 1\ [17]\). La période est \(16\).
Étape 4 — Décomposition : \(50 = 16 \times 3 + 2\), donc \(7^{50} = (7^{16})^3 \times 7^2 \equiv 1^3 \times (-2) = -2 \equiv 15\ [17]\).
Conclusion : le reste de \(231^{50}\) dans la division par \(17\) est \(\mathbf{15}\).