9
2ᵉ Bac · Sciences Maths · Chapitre 9
Arithmétique dans ℤ
1 · Résumé du cours
L'arithmétique est un chapitre emblématique de la filière Sciences Maths : elle demande moins de calcul que de raisonnement. Chaque théorème y a des conditions d'application précises, qu'il faut citer explicitement — c'est là que se gagnent (ou se perdent) les points.
1.1 Divisibilité & division euclidienne
Divisibilité
\(a\) divise \(b\) (noté \(a\mid b\)) s'il existe \(k\in\mathbb{Z}\) tel que \(b=ka\) ; \(b\) est alors un multiple de \(a\). Règles : \(a\mid a\), \(1\mid a\), \(a\mid 0\) ; transitivité (\(a\mid b\) et \(b\mid c\Rightarrow a\mid c\)) ; \(a\mid b\) et \(a\mid c\Rightarrow a\mid(bu+cv)\) ; \(a\mid b\) et \(b\mid a\Rightarrow a=\pm b\).
Division euclidienne
Pour tout \(a\in\mathbb{Z}\) et tout \(b\neq0\), il existe un unique couple \((q,r)\) tel que \(\boxed{\,a=bq+r,\ \ 0\le r<|b|\,}\). \(q\) est le quotient, \(r\) le reste.
L'unicité est la clé
Ce n'est pas l'existence qui rend la division euclidienne utile, mais l'unicité de \((q,r)\). C'est elle qui autorise à raisonner « le reste vaut nécessairement… » et qui fonde toute la théorie des congruences.
1.2 PGCD & algorithme d'Euclide
PGCD & premiers entre eux
Le PGCD de \(a,b\) (non tous deux nuls) est leur plus grand diviseur commun, noté \(\operatorname{pgcd}(a,b)\) ou \(a\wedge b\). Ils sont premiers entre eux lorsque \(a\wedge b=1\).
Algorithme d'Euclide
Si \(r\) est le reste de \(a\) par \(b\ (b\neq0)\), alors \(\boxed{\,\operatorname{pgcd}(a,b)=\operatorname{pgcd}(b,r)\,}\). On répète jusqu'à un reste nul : le dernier reste non nul est le PGCD. Si \(d=a\wedge b\), alors \(a=da'\), \(b=db'\) avec \(a'\wedge b'=1\).
Exemple
\(252=2\times105+42\), \(105=2\times42+21\), \(42=2\times21+0\). Dernier reste non nul : \(\operatorname{pgcd}(252,105)=21\).
1.3 Le PPCM
PPCM
Le PPCM de \(a,b\) non nuls est le plus petit de leurs multiples communs strictement positifs, noté \(\operatorname{ppcm}(a,b)\) ou \(a\vee b\).
Relation fondamentale & décompositions
\(\boxed{\,\operatorname{pgcd}(a,b)\times\operatorname{ppcm}(a,b)=|ab|\,}\) (donc si \(a\wedge b=1\), \(\operatorname{ppcm}=|ab|\)). Sur les décompositions : \(\operatorname{pgcd}=\prod p_i^{\min(\alpha_i,\beta_i)}\), \(\operatorname{ppcm}=\prod p_i^{\max(\alpha_i,\beta_i)}\). De plus \(m\) est multiple commun \(\iff\operatorname{ppcm}(a,b)\mid m\).
min et max
Le PGCD prend les plus petits exposants, le PPCM les plus grands. Comme \(\min(\alpha,\beta)+\max(\alpha,\beta)=\alpha+\beta\), la relation \(\operatorname{pgcd}\times\operatorname{ppcm}=|ab|\) en découle. Exemple : \(\operatorname{ppcm}(252,105)=\frac{252\times105}{21}=1260\).
Piège — plusieurs entiers
Pour \(n\ge3\) entiers : « premiers entre eux dans leur ensemble » (\(\operatorname{pgcd}(a_1,\dots,a_n)=1\)) est plus faible que « deux à deux » (\(\operatorname{pgcd}(a_i,a_j)=1\)). Ex : \(6,10,15\) : \(\operatorname{pgcd}=1\) mais \(\operatorname{pgcd}(6,10)=2\). PGCD/PPCM se calculent de proche en proche : \(\operatorname{pgcd}(a_1,\dots,a_n)=\operatorname{pgcd}\big(\operatorname{pgcd}(a_1,\dots,a_{n-1}),a_n\big)\). La relation \(\operatorname{pgcd}\times\operatorname{ppcm}=|ab|\) ne se généralise PAS à trois entiers.
1.4 Bézout & Gauss
Identité de Bézout
\(a\wedge b=1\iff\) il existe \(u,v\in\mathbb{Z}\) tels que \(\boxed{\,au+bv=1\,}\). Plus généralement, il existe toujours \(u,v\) tels que \(au+bv=\operatorname{pgcd}(a,b)\). Bézout généralisé : \(\operatorname{pgcd}(a_1,\dots,a_n)=1\iff\exists\,u_i,\ \sum a_i u_i=1\).
Théorème de Gauss
Si \(a\mid bc\) et \(a\wedge b=1\), alors \(\boxed{\,a\mid c\,}\).
La condition oubliée (erreur nº1)
Gauss n'est vrai qu'à condition que \(a\) soit premier avec \(b\). Sans elle, faux : \(6\mid 4\times3\) mais \(6\) ne divise ni \(4\) ni \(3\). Citez toujours cette condition.
Méthodes
- Prouver \(a\wedge b=1\) : exhiber une combinaison de Bézout \(au+bv=1\) (plus rapide que calculer le PGCD).
- Couple de Bézout : écrire les divisions d'Euclide, puis remonter en isolant le PGCD et en remplaçant les restes ligne après ligne.
1.5 Équations diophantiennes \(ax+by=c\)
Existence & structure
Soit \(d=a\wedge b\). \((E):ax+by=c\) admet des solutions dans \(\mathbb{Z}^{2}\) \(\iff\boxed{\,d\mid c\,}\). Si \((x_0,y_0)\) est une solution particulière et \(a=da'\), \(b=db'\) (\(a'\wedge b'=1\)), l'ensemble des solutions est
\[\boxed{\,\{(x_0+kb',\ y_0-ka')\ :\ k\in\mathbb{Z}\}\,}\]
Méthode — résoudre \(ax+by=c\)
① Calculer \(d=a\wedge b\), tester \(d\mid c\) (sinon aucune solution). ② Simplifier par \(d\) : \(a'x+b'y=c'\), \(a'\wedge b'=1\). ③ Solution particulière (à vue ou par remontée d'Euclide). ④ Solution générale \((x_0+kb',\,y_0-ka')\). ⑤ Vérifier (les \(k\) disparaissent).
Les deux fautes d'examen
Oublier de tester \(d\mid c\) avant de calculer ; et intervertir \(a'\) et \(b'\) dans la solution générale. Retenez : le coefficient de \(k\) dans \(x\) est celui de l'autre inconnue (\(b'\)), avec changement de signe pour \(y\). La vérification lève tout doute.
1.6 Nombres premiers
Définition & décomposition
\(p\ge2\) est premier s'il n'a que deux diviseurs positifs : \(1\) et lui-même. Tout \(n\ge2\) se décompose de manière unique (à l'ordre près) : \(n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}\). Si \(p\) premier et \(p\mid ab\), alors \(p\mid a\) ou \(p\mid b\). Pour tester \(n\), il suffit de vérifier qu'aucun premier \(p\le\sqrt n\) ne le divise.
Nombre de diviseurs
Si \(n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}\), les diviseurs positifs sont les \(p_1^{\beta_1}\cdots p_k^{\beta_k}\) avec \(0\le\beta_i\le\alpha_i\), et leur nombre est \(\boxed{\,\tau(n)=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)\,}\).
Pourquoi ce produit — & infinité des premiers
Choisir un diviseur = choisir indépendamment chaque exposant \(\beta_i\) parmi \(\alpha_i+1\) valeurs ; d'où le produit. Ex : \(360=2^{3}\times3^{2}\times5\), \(\tau(360)=4\times3\times2=24\). — Il existe une infinité de premiers : sinon, \(N=p_1\cdots p_k+1\) aurait un diviseur premier \(p_i\) qui diviserait \(N\) et \(p_1\cdots p_k\), donc \(1\) : impossible.
Petit théorème de Fermat
Soit \(p\) premier. Si \(p\nmid a\) : \(\boxed{\,a^{\,p-1}\equiv1\ [p]\,}\). Pour tout \(a\) : \(\boxed{\,a^{\,p}\equiv a\ [p]\,}\).
Deux conditions à surveiller
\(p\) doit être premier, et la première forme exige \(p\nmid a\). La seconde forme (\(a^{p}\equiv a\)) est valable sans restriction — celle qu'on utilise quand on ignore si \(p\mid a\).
1.7 Les congruences
Définition
Pour \(n\ge1\) : \(a\equiv b\ [n]\) lorsque \(n\mid(a-b)\), c'est-à-dire lorsque \(a\) et \(b\) ont le même reste dans la division par \(n\).
Compatibilité avec les opérations
Si \(a\equiv b\ [n]\) et \(c\equiv d\ [n]\), alors \(a+c\equiv b+d\), \(ac\equiv bd\), \(a^{k}\equiv b^{k}\ [n]\).
À quoi servent les congruences
Elles remplacent un nombre par son reste — souvent minuscule. Pour \(2^{100}\) modulo \(7\), on cherche un petit exposant où \(2^{k}\equiv1\), puis on exploite la périodicité. Des calculs gigantesques deviennent de l'arithmétique de poche.
Simplifier avec précaution
\(ac\equiv bc\ [n]\) et \(c\wedge n=1\ \Rightarrow\ a\equiv b\ [n]\). Sans \(c\wedge n=1\), faux : \(2\times3\equiv2\times0\ [6]\) mais \(3\not\equiv0\ [6]\).
Critères de divisibilité (en 3 lignes)
Avec \(N=\sum a_k 10^{k}\) : \(10\equiv1\ [9]\Rightarrow N\equiv\sum a_k\) (div. par \(9\) ou \(3\) \(\iff\) somme des chiffres) ; \(10\equiv-1\ [11]\Rightarrow N\equiv\sum(-1)^{k}a_k\) (div. par \(11\) \(\iff\) somme alternée) ; \(10^{k}\equiv0\ [4]\) si \(k\ge2\) (div. par \(4\) \(\iff\) deux derniers chiffres).
1.8 L'anneau \(\mathbb{Z}/n\mathbb{Z}\)
Classes de congruence
La classe de \(a\) modulo \(n\) est \(\bar a=\{x\in\mathbb{Z}:x\equiv a\ [n]\}=\{a+kn:k\in\mathbb{Z}\}\). On a \(\bar a=\bar b\iff a\equiv b\ [n]\) : deux classes sont égales ou disjointes (elles partitionnent \(\mathbb{Z}\)). Il y a exactement \(n\) classes : \(\boxed{\,\mathbb{Z}/n\mathbb{Z}=\{\bar0,\bar1,\dots,\overline{n-1}\}\,}\).
Structure d'anneau
On pose \(\bar a+\bar b=\overline{a+b}\) et \(\bar a\times\bar b=\overline{ab}\). Ces opérations sont bien définies (indépendantes des représentants — c'est la compatibilité des congruences), et \((\mathbb{Z}/n\mathbb{Z},+,\times)\) est un anneau commutatif unitaire, de zéro \(\bar0\), d'unité \(\bar1\).
Table de \(\mathbb{Z}/5\mathbb{Z}\) (×)
\[\begin{array}{c|ccccc}
\times & \bar0 & \bar1 & \bar2 & \bar3 & \bar4\\\hline
\bar0 & \bar0 & \bar0 & \bar0 & \bar0 & \bar0\\
\bar1 & \bar0 & \bar1 & \bar2 & \bar3 & \bar4\\
\bar2 & \bar0 & \bar2 & \bar4 & \bar1 & \bar3\\
\bar3 & \bar0 & \bar3 & \bar1 & \bar4 & \bar2\\
\bar4 & \bar0 & \bar4 & \bar3 & \bar2 & \bar1
\end{array}\]
Chaque ligne non nulle contient un \(\bar1\) : tout élément non nul est inversible (ex. \(\bar2\times\bar3=\bar1\), donc \(\bar2^{-1}=\bar3\)).
Inversibles & corps
\(\bar a\) est inversible (pour \(\times\)) \(\iff\boxed{\,a\wedge n=1\,}\) (Bézout : \(au+nv=1\Rightarrow\bar a^{-1}=\bar u\)). Et \((\mathbb{Z}/n\mathbb{Z},+,\times)\) est un corps \(\iff n\) est premier : pour \(p\) premier, tous les éléments non nuls de \(\mathbb{Z}/p\mathbb{Z}\) sont inversibles.
Corps \(\iff\) premier — le contraste
Dans \(\mathbb{Z}/6\mathbb{Z}\) : \(\bar2\times\bar3=\bar0\) avec \(\bar2,\bar3\neq\bar0\) — des diviseurs de zéro, donc pas un corps (\(6\) non premier). Dans \(\mathbb{Z}/5\mathbb{Z}\) : aucun produit de non-nuls n'est nul, tout non-nul est inversible — un corps (\(5\) premier). C'est l'exemple fondamental de corps fini, et il éclaire Fermat : les \(p-1\) classes non nulles forment un groupe multiplicatif, d'où \(\bar a^{\,p-1}=\bar1\).
1.9 Systèmes de numération
Écriture en base \(b\)
Soit \(b\ge2\). Tout \(N\ge1\) s'écrit de manière unique \(N=a_n b^{n}+\dots+a_1 b+a_0\), \(0\le a_i<b\), \(a_n\neq0\) ; on note \(N=\overline{a_n\dots a_0}^{\,b}\). En base \(b>10\), on utilise \(A=10,\dots,F=15\) (hexadécimal, \(b=16\) ; binaire, \(b=2\)).
Méthode — changer de base
Base \(b\to\)base \(10\) : développer \(\sum a_i b^{i}\). Base \(10\to\)base \(b\) : divisions euclidiennes successives par \(b\) ; les restes, lus du dernier au premier (de bas en haut), donnent les chiffres. Un entier est divisible par \(b\) \(\iff\) son dernier chiffre est nul (\(N\equiv a_0\ [b]\)).
Calculer en base \(b\)
On pose l'opération comme en base \(10\), mais on retient dès que l'on atteint \(b\) : à chaque colonne, si le total vaut \(s\), on écrit \(s\bmod b\) et on reporte \(\lfloor s/b\rfloor\). Ex : \(45=\overline{101101}^{\,2}\) (car \(32+8+4+1=45\)) ; \(\overline{34}^{\,5}+\overline{23}^{\,5}=\overline{112}^{\,5}\) (car \(19+13=32\)).
2 · Feuille de route
L'ordre conseillé pour maîtriser le chapitre.
1
Division euclidienne
\(a=bq+r\), \(0\le r<|b|\) : unicité de \((q,r)\).
2
PGCD / PPCM
Euclide ; \(\operatorname{pgcd}\times\operatorname{ppcm}=|ab|\) (2 entiers).
3
Bézout & Gauss
\(au+bv=1\) ; Gauss (condition \(a\wedge b=1\)).
4
Diophantiennes
\(ax+by=c\) : \(d\mid c\), puis \((x_0+kb',y_0-ka')\).
5
Premiers & Fermat
\(\tau(n)=\prod(\alpha_i+1)\) ; \(a^{p-1}\equiv1\ [p]\).
6
Congruences
Remplacer par le reste ; périodicité ; critères.
7
\(\mathbb{Z}/n\mathbb{Z}\)
Anneau ; inversible \(\iff a\wedge n=1\) ; corps \(\iff n\) premier.
8
Bases
Divisions par \(b\), restes lus de bas en haut.
3 · Exercices choisis
Une sélection couvrant chaque compétence clé, avec correction guidée.
Bézout · premiers entre eux
Exercice 1
Montrer que pour tout entier \(n\), les entiers \(2n+1\) et \(3n+1\) sont premiers entre eux.
Voir la correction
On cherche une combinaison de Bézout : \(3(2n+1)-2(3n+1)=6n+3-6n-2=1\). On a donc \((2n+1)\times3+(3n+1)\times(-2)=1\). D'après Bézout, \(2n+1\) et \(3n+1\) sont premiers entre eux, et ce pour tout \(n\). ∎
Euclide · remontée de Bézout
Exercice 2
Déterminer \(\operatorname{pgcd}(252,105)\), puis un couple \((u,v)\) tel que \(252u+105v=\operatorname{pgcd}(252,105)\).
Voir la correction
PGCD : Euclide donne \(252=2\times105+42\), \(105=2\times42+21\), \(42=2\times21+0\), donc \(\operatorname{pgcd}=21\).
Bézout (remontée) : ligne 2 : \(21=105-2\times42\). Ligne 1 : \(42=252-2\times105\). On remplace : \[21=105-2(252-2\times105)=5\times105-2\times252.\] Donc \(252\times(-2)+105\times5=21\), soit \(\boxed{(u,v)=(-2,5)}\). ∎
Congruences · périodicité
Exercice 3
Déterminer le reste de la division de \(2^{100}\) par \(7\).
Voir la correction
Périodicité de \(2^{k}\) modulo \(7\) : \(2^{1}\equiv2\), \(2^{2}\equiv4\), \(2^{3}\equiv8\equiv1\ [7]\). Période \(3\). Or \(100=3\times33+1\), donc \[2^{100}=\big(2^{3}\big)^{33}\times2\equiv1^{33}\times2\equiv2\ [7].\] Le reste est \(\boxed{2}\). ∎
Équation diophantienne
Exercice 4
Résoudre dans \(\mathbb{Z}^{2}\) l'équation \((E):24x+18y=30\).
Voir la correction
① \(\operatorname{pgcd}(24,18)=6\) et \(6\mid30\) : il y a des solutions. ② On divise par \(6\) : \(4x+3y=5\), avec \(4\wedge3=1\). ③ Solution particulière : \(4\times(-1)+3\times3=5\), donc \((x_0,y_0)=(-1,3)\). ④ Avec \(a'=4,\ b'=3\) : \[\boxed{(x,y)=(-1+3k,\ 3-4k),\quad k\in\mathbb{Z}}.\] ⑤ Vérif. : \(4(-1+3k)+3(3-4k)=-4+12k+9-12k=5\) ✓ ∎
Fermat · grande puissance
Exercice 5
Déterminer le reste de \(5^{2026}\) modulo \(13\).
Voir la correction
\(13\) est premier et \(13\nmid5\), donc par Fermat \(5^{12}\equiv1\ [13]\). Or \(2026=12\times168+10\), d'où \[5^{2026}=\big(5^{12}\big)^{168}\times5^{10}\equiv5^{10}\ [13].\] Puis \(5^{2}=25\equiv-1\ [13]\), donc \(5^{10}=\big(5^{2}\big)^{5}\equiv(-1)^{5}=-1\equiv12\ [13]\). Le reste est \(\boxed{12}\). ∎
\(\mathbb{Z}/n\mathbb{Z}\) · inverse & équation
Exercice 6
Dans \(\mathbb{Z}/7\mathbb{Z}\) : a) justifier que \(\bar4\) est inversible et donner son inverse ; b) résoudre \(\bar4\,\bar x=\bar5\).
Voir la correction
a) \(7\) est premier, donc \(\mathbb{Z}/7\mathbb{Z}\) est un corps et toute classe non nulle est inversible. Comme \(4\times2=8\equiv1\ [7]\), on a \(\boxed{\bar4^{-1}=\bar2}\).
b) On multiplie par \(\bar2\) : \(\bar2\times\bar4\,\bar x=\bar2\times\bar5\Rightarrow\bar1\,\bar x=\overline{10}=\bar3\). Donc \(\bar x=\bar3\). Vérif. : \(\bar4\times\bar3=\overline{12}=\bar5\) (car \(12=7+5\)) ✓ ∎
Besoin de plus d'exercices sur un point précis ? Demande à ton professeur en cours.
4 · Astuces & pièges à éviter
Astuce La division euclidienne est unique : c'est ce qui fait marcher tout le reste.
Astuce « Premiers entre eux » se prouve en exhibant une combinaison \(au+bv=1\).
Astuce Couple de Bézout : algorithme d'Euclide, puis remontée ligne par ligne.
Astuce Grandes puissances ⇒ congruences (périodicité) ou Fermat \(a^{p-1}\equiv1\ [p]\).
Astuce \(\tau(n)=\prod(\alpha_i+1)\) pour le nombre de diviseurs.
Astuce \(\mathbb{Z}/n\mathbb{Z}\) corps \(\iff n\) premier ; \(\bar a\) inversible \(\iff a\wedge n=1\) (par Bézout).
Piège Gauss exige \(a\wedge b=1\) : sans cette condition, \(a\mid bc\) n'entraîne pas \(a\mid c\).
Piège Diophantienne : tester \(d\mid c\) avant tout, et ne pas intervertir \(a'\) et \(b'\).
Piège Simplifier une congruence par \(c\) n'est licite que si \(c\wedge n=1\).
Piège \(\operatorname{pgcd}\times\operatorname{ppcm}=|ab|\) ne vaut que pour deux entiers, pas trois.
Piège « Premiers entre eux deux à deux » est plus fort que « dans leur ensemble ».
Formulaire à retenir
Divisibilité \(a\mid b\iff\exists k,\ b=ka\) ; \(a\mid b,c\Rightarrow a\mid(bu+cv)\)
Division euclidienne \(a=bq+r\), \(0\le r<|b|\), couple \((q,r)\) unique
Algorithme d'Euclide \(\operatorname{pgcd}(a,b)=\operatorname{pgcd}(b,r)\) ; dernier reste non nul
Relation PGCD–PPCM \(\operatorname{pgcd}(a,b)\times\operatorname{ppcm}(a,b)=|ab|\) (deux entiers)
Décompositions \(\operatorname{pgcd}=\prod p_i^{\min}\), \(\operatorname{ppcm}=\prod p_i^{\max}\)
Proche en proche \(\operatorname{pgcd}(a_1,\dots,a_n)=\operatorname{pgcd}(\operatorname{pgcd}(a_1,\dots,a_{n-1}),a_n)\)
Bézout \(a\wedge b=1\iff\exists u,v,\ au+bv=1\)
Bézout généralisé \(\operatorname{pgcd}(a_1,\dots,a_n)=1\iff\exists u_i,\ \sum a_i u_i=1\)
Gauss \(a\mid bc\) et \(a\wedge b=1\Rightarrow a\mid c\)
Diophantienne — existence \(ax+by=c\) a des solutions \(\iff(a\wedge b)\mid c\)
Diophantienne — solutions \((x_0+kb',\,y_0-ka')\), \(k\in\mathbb{Z}\), \(a=da'\), \(b=db'\)
Nombre de diviseurs \(n=\prod p_i^{\alpha_i}\Rightarrow\tau(n)=\prod(\alpha_i+1)\)
Test de primalité \(n\) premier \(\iff\) aucun premier \(p\le\sqrt n\) ne divise \(n\)
Petit théorème de Fermat \(p\) premier, \(p\nmid a\Rightarrow a^{p-1}\equiv1\ [p]\) ; \(a^{p}\equiv a\ [p]\)
Congruence \(a\equiv b\ [n]\iff n\mid(a-b)\) (même reste)
Compatibilité \(a+c\equiv b+d\), \(ac\equiv bd\), \(a^{k}\equiv b^{k}\ [n]\)
Simplification \(ac\equiv bc\ [n]\) et \(c\wedge n=1\Rightarrow a\equiv b\ [n]\)
Critères \(9,3\) : somme des chiffres ; \(11\) : somme alternée ; \(4\) : 2 derniers chiffres
Classes \(\mathbb{Z}/n\mathbb{Z}=\{\bar0,\bar1,\dots,\overline{n-1}\}\), \(\bar a+\bar b=\overline{a+b}\), \(\bar a\bar b=\overline{ab}\)
Inversibles \(\bar a\) inversible \(\iff a\wedge n=1\) ; par Bézout \(\bar a^{-1}=\bar u\)
Corps \(\mathbb{Z}/n\mathbb{Z}\) est un corps \(\iff n\) premier
Base \(b\) \(N=\sum a_i b^{i}\), \(0\le a_i<b\) ; base 10→\(b\) : divisions successives, restes de bas en haut
© Anass Shimi — Sciences Excellence · anassmaths.com