Arithmétique dans Z - Cours et exercices corrigés | 1re Bac sciences mathématiques

KORASATI · MATHÉMATIQUES

Retrouvez le cours intégral ci-dessous et sa version A4 mise en page, avec toutes les figures et les exercices corrigés.

Ouvrir et télécharger le cours en PDF

Sur téléphone, utilisez le bouton ci-dessus pour agrandir le document. La lecture est accessible sans inscription.

---

Objectifs. Utiliser la division euclidienne dans les entiers relatifs, décomposer un entier en facteurs premiers, calculer PGCD et PPCM, puis travailler avec les congruences et les classes modulo un entier.

Parcours. Ce chapitre appartient aux sciences mathématiques. Il développe les techniques élémentaires de divisibilité et le calcul dans $\mathbb{Z}/n\mathbb{Z}$. Les notions de nombres premiers entre eux et les théorèmes de Bézout et de Gauss ne sont pas nécessaires à ce parcours.

Divisibilité dans les entiers relatifs

Pour $a,b\in\mathbb{Z}$, on écrit $a\mid b$ et on dit que $a$ divise $b$ s’il existe $k\in\mathbb{Z}$ tel que $b=ak$. Le nombre $b$ est alors un multiple de $a$. Cette définition porte sur l’existence d’un quotient entier, pas seulement d’un quotient réel.

Par exemple, $7\mid(-35)$ car $-35=7(-5)$, et $-7\mid35$. Pour un diviseur non nul, changer son signe ne modifie pas la divisibilité. Tout entier divise $0$ puisque $0=a\cdot0$. Le nombre $0$ ne divise que $0$ : l’égalité $b=0k$ impose $b=0$.

Propriétés de base

Pour tous les entiers concernés :

• si $a\mid b$ et $b\mid c$, alors $a\mid c$ ;

• si $d\mid a$ et $d\mid b$, alors $d\mid(ua+vb)$ pour tous $u,v\in\mathbb{Z}$ ;

• si $a\mid b$ et $b\ne0$, alors $|a|\le|b|$ ;

• si $a\mid b$ et $b\mid a$, alors $|a|=|b|$.

La propriété de combinaison se démontre en écrivant $a=dp$ et $b=dq$ : $ua+vb=d(up+vq)$. Elle permet de simplifier une recherche de diviseurs communs sans changer les contraintes.

Exemple - Une condition nécessaire utile

Si un entier $d$ divise $3n+2$ et $5n+1$, alors il divise $5(3n+2)-3(5n+1)=7$. Ses valeurs possibles sont donc parmi $\pm1,\pm7$. On a obtenu une condition nécessaire ; il reste à vérifier quels candidats divisent effectivement les deux expressions pour la valeur de $n$ étudiée.

Division euclidienne, y compris pour un entier négatif

Théorème

Pour $a\in\mathbb{Z}$ et $b\in\mathbb{N}$ avec $b>0$, il existe un unique couple d’entiers $(q,r)$ tel que $$\boxed{a=bq+r,\qquad 0\le r<b.}$$ Le nombre $q$ est le quotient et $r$ le reste de la division euclidienne de $a$ par $b$. Le reste est toujours positif ou nul, même lorsque $a$ est négatif.

L’existence revient à choisir l’unique multiple $bq$ tel que $bq\le a<b(q+1)$, puis à poser $r=a-bq$. Pour l’unicité, si $bq+r=bq'+r'$ avec $0\le r,r'<b$, alors $b(q-q')=r'-r$. Le membre de droite est strictement compris entre $-b$ et $b$ ; le seul multiple de $b$ dans cet intervalle est $0$. Ainsi $r=r'$ et $q=q'$.

Exemple - Ne pas garder un reste négatif

On a $47=7\cdot6+5$. Pour $-47$, l’écriture $-47=7(-6)-5$ est vraie mais ne constitue pas une division euclidienne : le reste $-5$ est interdit. L’écriture correcte est $$-47=7(-7)+2,\qquad 0\le2<7.$$ Le quotient vaut $-7$ et le reste $2$. Enfin, $b\mid a$ si et seulement si le reste de cette division est $0$.

Des restes qui organisent une preuve

La division par $b$ classe tous les entiers en $b$ cas, correspondant aux restes $0,1,\ldots,b-1$. Par exemple, tout entier est pair ou impair, car son reste modulo $2$ est $0$ ou $1$. Une preuve par disjonction des cas doit traiter tous les restes possibles, y compris pour les entiers négatifs.

Nombres premiers et factorisation

Un entier naturel $p\ge2$ est premier si ses seuls diviseurs positifs sont $1$ et $p$. Les nombres $0$ et $1$ ne sont pas premiers. Dans cette convention, les nombres premiers sont positifs ; pour factoriser un entier négatif, on sépare le signe et on factorise sa valeur absolue.

Tester la primalité

Si $n\ge2$ n’est pas premier, il s’écrit $n=ab$ avec $2\le a\le b$. Alors $a^2\le n$, donc $a\le\sqrt n$ ; un diviseur premier de $a$ est aussi un diviseur de $n$. Il suffit donc de tester les diviseurs premiers inférieurs ou égaux à $\sqrt n$.

Ainsi, pour $97$, on teste $2,3,5,7$, les seuls nombres premiers ne dépassant pas $\sqrt{97}<10$. Aucun ne divise $97$ : le nombre est premier. Pour $91$, le diviseur $7$ donne $91=7\cdot13$ : le nombre n’est pas premier.

Décomposition en facteurs premiers

Tout entier naturel $n\ge2$ s’écrit comme un produit de nombres premiers. Cette décomposition est unique à l’ordre des facteurs près. On rassemble généralement les facteurs égaux en puissances : $$n=p_1^{\alpha_1}\cdots p_k^{\alpha_k},\qquad \alpha_i\ge1.$$ L’existence peut se montrer par récurrence forte : un entier est soit premier, soit produit de deux entiers plus petits déjà décomposables. L’unicité est admise ici.

Exemple - Décomposer et lire les diviseurs

On obtient $360=2^3\cdot3^2\cdot5$. Un diviseur positif de $360$ a exactement la forme $2^a3^b5^c$ avec $0\le a\le3$, $0\le b\le2$, $0\le c\le1$. Il existe donc $4\cdot3\cdot2=24$ diviseurs positifs. Les diviseurs négatifs sont leurs opposés.

Un carré parfait positif a tous ses exposants premiers pairs. En effet, élever une décomposition au carré double chaque exposant ; réciproquement, on peut diviser des exposants pairs par $2$ pour construire une racine entière. Cette observation est utile pour compléter un produit afin d’en faire un carré.

PGCD, PPCM et algorithme d’Euclide

Définitions et calcul par factorisation

Pour deux entiers $a,b$ non simultanément nuls, le PGCD est leur plus grand diviseur commun positif, noté $\operatorname{PGCD}(a,b)$ ou $a\wedge b$. Il est inchangé si l’on remplace les entiers par leurs valeurs absolues ; $\operatorname{PGCD}(a,0)=|a|$ pour $a\ne0$.

Pour $a,b$ non nuls, le PPCM est leur plus petit multiple commun strictement positif, noté $\operatorname{PPCM}(a,b)$ ou $a\vee b$. On utilise également leurs valeurs absolues. Si l’un est nul, on adopte $\operatorname{PPCM}(a,0)=0$ ; ce cas se traite séparément de la définition par un multiple positif.

À partir des décompositions en nombres premiers, le PGCD prend le minimum des deux exposants de chaque premier, tandis que le PPCM prend leur maximum. Un premier absent d’une décomposition a l’exposant $0$.

Pour $360=2^3\cdot3^2\cdot5$ et $252=2^2\cdot3^2\cdot7$, $$\operatorname{PGCD}(360,252)=2^2\cdot3^2=36, \qquad \operatorname{PPCM}(360,252)=2^3\cdot3^2\cdot5\cdot7=2520.$$ Les diviseurs communs sont exactement les diviseurs du PGCD ; les multiples communs sont exactement les multiples du PPCM. Pour $a,b\ne0$, $$\boxed{\operatorname{PGCD}(a,b)\,\operatorname{PPCM}(a,b)=|ab|.}$$ Cette identité vient de $\min(\alpha,\beta)+\max(\alpha,\beta)=\alpha+\beta$ pour chaque facteur premier.

Pourquoi l’algorithme d’Euclide fonctionne

Si $a=bq+r$, les diviseurs communs de $a,b$ sont ceux de $b,r$. En effet, un diviseur de $a,b$ divise $r=a-bq$ ; un diviseur de $b,r$ divise $a=bq+r$. Ainsi $$\operatorname{PGCD}(a,b)=\operatorname{PGCD}(b,r).$$ On répète les divisions avec des restes strictement décroissants et positifs jusqu’au reste nul. Le dernier reste non nul est le PGCD. Cette méthode évite une factorisation parfois longue.

Exemple - Calculer $\operatorname{PGCD}(252,198)$

$252$	$=$	$198\cdot1+54$
$198$	$=$	$54\cdot3+36$
$54$	$=$	$36\cdot1+18$
$36$	$=$	$18\cdot2+0$

Le dernier reste non nul est $18$. Donc $\operatorname{PGCD}(252,198)=18$ et $\operatorname{PPCM}(252,198)=252\cdot198/18=2772$. Il ne faut pas choisir l’avant-dernier quotient ni le dernier reste, qui est $0$.

Congruences modulo un entier

Fixons un entier $n\ge2$. Pour $a,b\in\mathbb{Z}$, on dit que $a$ est congru à $b$ modulo $n$, et on écrit $a\equiv b\pmod n$, lorsque $n\mid(a-b)$.

Les deux entiers ont alors le même reste dans la division euclidienne par $n$. En effet, si $a=nq+r$ et $b=nq'+r'$ avec $0\le r,r'<n$, la divisibilité de $a-b$ par $n$ impose $r=r'$. Réciproquement, un reste identique donne $a-b=n(q-q')$.

Par exemple, $-47\equiv2\pmod7$ et $23\equiv2\pmod7$. On peut remplacer un entier par son reste pour simplifier un calcul, sans affirmer que les deux entiers sont égaux dans $\mathbb{Z}$.

Règles de calcul

Si $a\equiv b\pmod n$ et $c\equiv d\pmod n$, alors $$a+c\equiv b+d,\qquad a-c\equiv b-d,\qquad ac\equiv bd\pmod n.$$ On en déduit $a^k\equiv b^k\pmod n$ pour tout entier $k\ge0$. Les règles se justifient par la divisibilité ; par exemple $ac-bd=c(a-b)+b(c-d)$ est un multiple de $n$. La congruence est aussi réflexive, symétrique et transitive, ce qui permet d’enchaîner les calculs.

On ne divise pas librement une congruence

De $2\cdot1\equiv2\cdot4\pmod6$, on ne peut pas conclure $1\equiv4\pmod6$ : $6$ divise $2-8=-6$, mais ne divise pas $1-4=-3$. Les règles sûres présentées ici concernent addition, soustraction, multiplication et puissances entières naturelles.

Exemple - Réduire une grande puissance

Comme $10\equiv-1\pmod{11}$, on a $10^{2026}\equiv1$ et $10^{2027}\equiv-1\pmod{11}$. Le reste de $10^{2027}+4$ dans la division par $11$ est donc $3$ : le nombre obtenu doit être remis dans la liste $0,1,\ldots,10$.

Divisibilité et écritures décimales

Si $N=\sum_{k=0}^m a_k10^k$, avec $a_k$ ses chiffres, alors $10\equiv1\pmod9$ et modulo $3$. Donc $N$ est congru à la somme de ses chiffres modulo $9$ ou $3$. Avec $10\equiv-1\pmod{11}$, on obtient une somme alternée des chiffres. Ces critères sont des conséquences des règles de congruence, et non des recettes indépendantes.

Les classes de $\mathbb{Z}/n\mathbb{Z}$ et leurs opérations

La classe de $a$ modulo $n$ est l’ensemble $$\overline a=a+n\mathbb{Z}=\{a+nk\mid k\in\mathbb{Z}\}.$$ Deux entiers ont la même classe si et seulement s’ils sont congrus. Toute classe possède un unique représentant dans $\{0,1,\ldots,n-1\}$ : son reste. L’ensemble des classes, noté $\mathbb{Z}/n\mathbb{Z}$, contient donc exactement $n$ éléments, $$\mathbb{Z}/n\mathbb{Z}=\{\overline0,\overline1,\ldots,\overline{n-1}\}.$$ Une classe est un ensemble infini d’entiers, tandis que l’ensemble des classes est fini. Pour $n=5$, les entiers $-3,2,7,12$ représentent tous la classe $\overline2$.

Figure disponible dans la version PDF ci-dessus.

Addition, multiplication et opposé

On définit $\overline a+\overline b=\overline{a+b}$ et $\overline a\,\overline b=\overline{ab}$. Ces définitions ne dépendent pas des représentants choisis, précisément grâce aux règles de calcul des congruences. L’opposé de $\overline a$ est $\overline{-a}$.

L’addition et la multiplication sont associatives et commutatives, et la multiplication est distributive par rapport à l’addition. Les classes $\overline0$ et $\overline1$ jouent les rôles habituels de neutres. On calcule avec des représentants puis on réduit le résultat modulo $n$.

Par exemple, dans $\mathbb{Z}/5\mathbb{Z}$, $\overline3+\overline4=\overline7=\overline2$ et $\overline3\,\overline4=\overline{12}=\overline2$. L’opposé de $\overline3$ est $\overline2$, car leur somme est $\overline0$.

Une table ne ressemble pas toujours au calcul dans $\mathbb{R}$

Voici la table de multiplication de $\mathbb{Z}/4\mathbb{Z}$ :

$\times$	$\overline0$	$\overline1$	$\overline2$	$\overline3$
$\overline0$	$\overline0$	$\overline0$	$\overline0$	$\overline0$
$\overline1$	$\overline0$	$\overline1$	$\overline2$	$\overline3$
$\overline2$	$\overline0$	$\overline2$	$\overline0$	$\overline2$
$\overline3$	$\overline0$	$\overline3$	$\overline2$	$\overline1$

On voit que $\overline2^2=\overline0$ alors que $\overline2\ne\overline0$. On ne transpose donc pas sans preuve les règles de simplification ou du produit nul connues dans $\mathbb{R}$. Pour résoudre une congruence simple, tester les $n$ classes donne une méthode complète et sûre.

Exercices corrigés

Exercice 1 - Deux divisions euclidiennes

Effectuer les divisions euclidiennes de $785$ et de $-785$ par $23$.

Correction. Comme $23\cdot34=782$, on a $785=23\cdot34+3$, avec $0\le3<23$. Pour l’entier négatif, diminuer le quotient d’une unité afin de rendre le reste positif : $$-785=23(-35)+20,\qquad 0\le20<23.$$ Les couples $(q,r)$ sont donc $(34,3)$ et $(-35,20)$. L’écriture $-785=23(-34)-3$ ne satisfait pas la condition du reste.

Exercice 2 - Un PGCD par divisions successives

Calculer $\operatorname{PGCD}(1071,462)$ puis $\operatorname{PPCM}(1071,462)$.

Correction. Les divisions donnent $$1071=462\cdot2+147,\quad462=147\cdot3+21,\quad147=21\cdot7+0.$$ Le PGCD est donc $21$. L’identité produit donne $\operatorname{PPCM}(1071,462)=1071\cdot462/21=23562$. On peut vérifier que $23562=1071\cdot22=462\cdot51$, ce qui confirme qu’il s’agit d’un multiple commun ; le calcul par PGCD garantit son caractère minimal positif.

Exercice 3 - Factorisation et carré parfait

Décomposer $540$ en facteurs premiers. Calculer son nombre de diviseurs positifs et le plus petit entier naturel non nul $k$ tel que $540k$ soit un carré parfait.

Correction. On a $540=2^2\cdot3^3\cdot5$. Les exposants des diviseurs positifs varient de $0$ à $2$, de $0$ à $3$ et de $0$ à $1$ : leur nombre est $3\cdot4\cdot2=24$. Pour obtenir un carré, il faut rendre pairs les exposants de $3$ et de $5$ ; la plus petite correction est $k=3\cdot5=15$. En effet, $540\cdot15=2^2\cdot3^4\cdot5^2=90^2=8100$. Tout autre choix doit contenir au moins ces facteurs et peut ajouter des facteurs de carré.

Exercice 4 - Divisibilité d’un produit de trois entiers

Montrer que $6$ divise $n(n+1)(n+2)$ pour tout $n\in\mathbb{Z}$, en utilisant les restes modulo $6$.

Correction. Tout entier a un unique reste $r\in\{0,1,2,3,4,5\}$ modulo $6$, et le produit est congru à $r(r+1)(r+2)$. Pour ces six valeurs, les produits valent respectivement $$0,\quad6,\quad24,\quad60,\quad120,\quad210.$$ Ils sont tous multiples de $6$. Par les règles de congruence, le produit initial est donc congru à $0$ modulo $6$, ce qui prouve la divisibilité pour tous les entiers, positifs ou négatifs.

Exercice 5 - Une grande puissance

Déterminer le reste de $7^{2026}$ dans la division euclidienne par $5$.

Correction. Modulo $5$, $7\equiv2$, $2^2\equiv4$ et $2^4\equiv1$. Comme $2026=4\cdot506+2$, $$7^{2026}\equiv(2^4)^{506}\,2^2\equiv1^{506}\cdot4\equiv4\pmod5.$$ Le représentant $4$ appartient à $\{0,1,2,3,4\}$ : c’est bien le reste euclidien. La périodicité des puissances a été établie par un calcul, pas supposée à partir des derniers chiffres de l’exposant.

Exercice 6 - Construire un nombre divisible

Déterminer le chiffre $a$ pour que le nombre décimal $3a42$ soit divisible par $9$. Vérifier ensuite sa divisibilité par $11$.

Correction. La somme des chiffres vaut $3+a+4+2=9+a$. Pour $a\in\{0,\ldots,9\}$, la divisibilité par $9$ impose $a=0$ ou $a=9$. Pour $11$, la somme alternée calculée depuis les unités vaut $2-4+a-3=a-5$. Elle vaut $-5$ si $a=0$ et $4$ si $a=9$ ; aucun de ces nombres n’est multiple de $11$. Les nombres $3042$ et $3942$ sont donc divisibles par $9$, mais aucun n’est divisible par $11$.

Exercice 7 - Calculer dans un ensemble de classes

Dans $\mathbb{Z}/7\mathbb{Z}$, calculer $\overline{15}+\overline{-9}$, $\overline{15}\,\overline{-9}$ et l’opposé de $\overline{15}$. Expliquer pourquoi on peut réduire avant ou après l’opération.

Correction. On a $\overline{15}=\overline1$ et $\overline{-9}=\overline5$. La somme vaut donc $\overline6$, le produit $\overline5$, et l’opposé de $\overline{15}$ est $\overline6$. Directement, $15-9=6$ et $15(-9)=-135=7(-20)+5$ redonnent les mêmes résultats. Les opérations sur les classes sont bien définies : des représentants congrus donnent une somme et un produit congrus.

Exercice 8 - Résoudre sans simplification abusive

Résoudre $2x\equiv2\pmod6$ dans $\mathbb{Z}$, puis $2x\equiv1\pmod6$.

Correction. Pour les six restes $0,1,2,3,4,5$ de $x$, les restes de $2x$ sont $0,2,4,0,2,4$. La première congruence admet exactement les classes $\overline1$ et $\overline4$. Ses solutions sont donc $$x=6k+1\quad\text{ou}\quad x=6k+4,\qquad k\in\mathbb{Z}.$$ Ces deux familles peuvent aussi s’écrire $x=3k+1$. La seconde congruence n’a aucune solution, car le reste $1$ n’apparaît jamais. Diviser la première par $2$ en conservant le module $6$ aurait perdu toute la classe $\overline4$.

Exercice 9 - Répartir et synchroniser

On veut former le plus grand nombre de lots identiques avec $84$ objets d’un type et $126$ d’un autre, en utilisant tous les objets. Combien de lots obtient-on et que contient chacun ? Deux signaux se répètent ensuite toutes les $84$ et $126$ secondes ; après un départ commun, quand coïncident-ils de nouveau ?

Correction. Le nombre de lots doit diviser $84$ et $126$. Leur PGCD vaut $42$, car $126=84+42$ et $84=2\cdot42$. On peut donc former $42$ lots de $2$ objets du premier type et de $3$ du second. Pour les signaux, on cherche au contraire le plus petit multiple positif commun : $$\operatorname{PPCM}(84,126)=\frac{84\cdot126}{42}=252.$$ Ils coïncident après $252$ secondes, soit $4$ minutes $12$ secondes. Le premier problème utilise une division commune maximale, le second une répétition commune minimale.

Fin du cours et des exercices corrigés