Arithmétique - Cours et exercices corrigés | 2e 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. Organiser les calculs dans $\mathbb{Z}$, utiliser Euclide, Bézout et Gauss, résoudre des équations diophantiennes et des congruences, calculer dans $\mathbb{Z}/n\mathbb{Z}$, appliquer Fermat et travailler dans une base de numération. Les exemples de codage sont des applications mathématiques élémentaires.

Divisibilité, division euclidienne et nombres premiers

Pour $a,b\in\mathbb{Z}$, $a\mid b$ signifie qu’il existe $k\in\mathbb{Z}$ tel que $b=ak$. Si $a\mid b$ et $a\mid c$, alors $a\mid ub+vc$ pour tous entiers $u,v$. Les signes ne changent pas les diviseurs communs : on prend le PGCD positif.

Division euclidienne

Pour $a\in\mathbb{Z}$ et $b\ge1$, il existe un unique couple $(q,r)\in\mathbb{Z}\times\mathbb{N}$ tel que $$a=bq+r,\qquad0\le r<b.$$ Ainsi $-17=5\times(-4)+3$. Le reste est positif ou nul même lorsque le dividende est négatif.

L’unicité vient de $b(q-q')=r'-r$ : le seul multiple de $b$ strictement compris entre $-b$ et $b$ est $0$.

Premiers et décomposition

Un entier $p\ge2$ est premier si ses seuls diviseurs positifs sont $1$ et $p$. Le nombre $1$ n’est pas premier. Tout entier $N\ge2$ se décompose en produit de nombres premiers, de façon unique à l’ordre près : $$N=p_1^{\alpha_1}\cdots p_s^{\alpha_s},\qquad\alpha_i\ge1.$$ Pour tester la primalité de $N$, il suffit de chercher un diviseur premier au plus égal à $\sqrt N$ : si $N=ab$ avec $1<a\le b$, alors $a\le\sqrt N$.

Le crible d’Ératosthène

On écrit les entiers de $2$ à $N$, on conserve le plus petit non éliminé, puis on élimine ses multiples strictement plus grands. On recommence jusqu’aux candidats au plus égaux à $\sqrt N$. Les entiers restants sont les nombres premiers.

Figure disponible dans la version PDF ci-dessus.

Il existe une infinité de nombres premiers

Si la liste $p_1,\ldots,p_s$ contenait tous les nombres premiers, $N=p_1\cdots p_s+1>1$ aurait un diviseur premier. Aucun $p_i$ ne le divise, car le reste serait $1$. Cette contradiction prouve l’infinité. On n’affirme pas que $N$ lui-même est toujours premier.

Euclide, Bézout et Gauss

Le PGCD se conserve dans les divisions

Pour $a=bq+r$, les diviseurs communs à $a,b$ sont exactement ceux de $b,r$. L’algorithme d’Euclide répète cette opération ; les restes positifs décroissent, donc il s’arrête. Le dernier reste non nul est le PGCD.

Exemple - Calculer et remonter les divisions

$$252=198+54,\quad198=3\times54+36,\quad 54=36+18,\quad36=2\times18.$$ Donc $\operatorname{pgcd}(252,198)=18$. En remontant, $$18=54-36=4\times54-198=4\times252-5\times198.$$ On a obtenu en même temps des coefficients de Bézout.

Le théorème de Bézout

Une combinaison égale au PGCD

Pour $a,b\in\mathbb{Z}$ non tous deux nuls, il existe $u,v\in\mathbb{Z}$ tels que $$au+bv=d,\qquad d=\operatorname{pgcd}(a,b).$$ En particulier, $\operatorname{pgcd}(a,b)=1$ si et seulement s’il existe $u,v$ tels que $au+bv=1$.

L’algorithme d’Euclide étendu construit ces coefficients. Réciproquement, si $au+bv=1$, tout diviseur commun de $a,b$ divise $1$, donc le PGCD vaut $1$. Plus généralement, toute combinaison $au+bv$ est divisible par $d$.

Le théorème de Gauss

Si $a\mid bc$ et $\operatorname{pgcd}(a,b)=1$, alors $a\mid c$. En effet, Bézout donne $au+bv=1$. Après multiplication par $c$, $$c=auc+bvc,$$ et chacun des termes de droite est divisible par $a$.

Exemple - Une simplification autorisée

Si $15\mid4m$, alors $15\mid m$, car $\operatorname{pgcd}(15,4)=1$. En revanche, $6\mid2m$ n’impose pas $6\mid m$ : $m=3$ est un contre-exemple. La condition de coprimalité ne peut pas être supprimée.

Conséquence pour un facteur premier

Si un nombre premier $p$ divise $ab$, alors il divise $a$ ou $b$. S’il ne divise pas $a$, son PGCD avec $a$ vaut $1$, et Gauss impose $p\mid b$. Cette propriété permet notamment de justifier l’unicité de la décomposition en facteurs premiers.

Deux entiers premiers entre eux ne sont pas forcément premiers

$8$ et $15$ sont composés, mais leur PGCD vaut $1$. « Premiers entre eux » décrit une relation entre deux nombres ; « premier » décrit un nombre isolé.

Équations diophantiennes linéaires

On cherche ici des solutions entières de $ax+by=c$. Les solutions réelles d’une droite ne répondent pas à cette question.

Critère d’existence

Supposons $a,b$ non nuls et posons $d=\operatorname{pgcd}(a,b)>0$. Si une solution existe, $d\mid ax+by$, donc $d\mid c$. Réciproquement, si $c=kd$, une identité $au+bv=d$ donne la solution particulière $(ku,kv)$. Ainsi $$\boxed{ax+by=c\text{ possède une solution dans }\mathbb{Z}^2 \iff d\mid c}.$$

Toutes les solutions

À partir d’une solution particulière $(x_0,y_0)$, $$\boxed{x=x_0+\frac bd\,t,\qquad y=y_0-\frac ad\,t,\qquad t\in\mathbb{Z}}.$$ Ces couples vérifient l’équation. Réciproquement, soustraire les équations donne $(a/d)(x-x_0)=-(b/d)(y-y_0)$. Comme $a/d$ et $b/d$ sont premiers entre eux, Gauss montre que $b/d$ divise $x-x_0$, ce qui fournit la forme annoncée.

Exemple - Solutions entières puis contraintes positives

Pour $15x+21y=6$, le PGCD vaut $3$ et divise $6$. Le couple $(-1,1)$ convient. Toutes les solutions sont $$x=-1+7t,\qquad y=1-5t,\qquad t\in\mathbb{Z}.$$ Si l’on demande en plus $x,y\ge0$, la première condition impose $t\ge1$ et la seconde $t\le0$. Il n’y a donc aucune solution dans $\mathbb{N}^2$, malgré l’existence d’une infinité de solutions dans $\mathbb{Z}^2$.

Cas particuliers et méthode

Si $a=0$ et $b\ne0$, l’équation se réduit à $by=c$ : soit $b\mid c$ et $y=c/b$ avec $x$ libre, soit aucune solution. Le cas $b=0$ est analogue. Si $a=b=0$, tous les couples conviennent lorsque $c=0$, et aucun sinon.

Une démarche complète

Calculer le PGCD ; tester sa divisibilité dans $c$ ; trouver une solution particulière par Bézout ou par observation ; écrire toutes les solutions ; enfin traduire les contraintes supplémentaires sur le paramètre entier.

Des solutions distinctes restent distinctes

Lorsque $a,b$ sont non nuls, des valeurs différentes de $t$ donnent des couples différents. Une contrainte d’intervalle, de positivité ou de chiffre peut réduire l’ensemble infini à une liste finie, voire à l’ensemble vide. On termine alors en énumérant les entiers admissibles.

Congruences et calcul dans les classes

Reste commun modulo $n$

Pour $n\ge2$, $a\equiv b\pmod n$ signifie $n\mid(a-b)$. C’est équivalent à dire que $a$ et $b$ ont le même reste dans la division euclidienne par $n$. On peut additionner, soustraire, multiplier et élever à une puissance entière positive des congruences. $$a\equiv b\pmod n\Longrightarrow a^k\equiv b^k\pmod n \quad(k\ge1).$$ Par exemple, $17\equiv2\pmod5$, donc $17^3\equiv2^3\equiv3\pmod5$.

Inverse et simplification

Un entier $a$ possède un inverse modulo $n$ exactement lorsque $\operatorname{pgcd}(a,n)=1$. En effet, $au\equiv1\pmod n$ équivaut à $au+nv=1$ pour un entier $v$ : c’est Bézout. Dans ce cas, multiplier par l’inverse autorise une simplification.

Exemple - Un facteur non inversible

$2\times1\equiv2\times4\pmod6$, mais $1\not\equiv4\pmod6$. On ne peut pas annuler le facteur $2$, car il n’est pas premier avec $6$. La relation équivaut ici seulement à $1\equiv4\pmod3$.

Résoudre $ax\equiv b\pmod n$

Cette congruence équivaut à une équation $ax+ny=b$. Elle est soluble si et seulement si $d=\operatorname{pgcd}(a,n)$ divise $b$. On divise alors par $d$ en changeant aussi le module : $$\frac ad x\equiv\frac bd\pmod{n/d}.$$ Si $d<n$, le coefficient $a/d$ est inversible modulo $n/d$. On obtient une classe modulo $n/d$, donc exactement $d$ classes modulo $n$. Si $d=n$, le coefficient initial est nul modulo $n$ : toutes les $n$ classes conviennent lorsque $n\mid b$, et aucune sinon.

L’ensemble $\mathbb{Z}/n\mathbb{Z}$

La classe $\overline a$ regroupe les entiers congrus à $a$ modulo $n$. Il existe $n$ classes, représentées par $0,1,\ldots,n-1$. On définit $$\overline a+\overline b=\overline{a+b},\qquad \overline a\,\overline b=\overline{ab}.$$ Les règles des congruences garantissent que ces opérations ne dépendent pas des représentants choisis. Elles sont associatives et commutatives, et la multiplication est distributive sur l’addition. Les neutres sont $\overline0$ et $\overline1$ ; l’opposé de $\overline a$ est $\overline{-a}$.

Si $p$ est premier, chaque classe non nulle de $\mathbb{Z}/p\mathbb{Z}$ possède un inverse : cet ensemble est un corps. Pour un module composé, ce n’est pas le cas ; dans $\mathbb{Z}/4\mathbb{Z}$, $\overline2\ne\overline0$ mais $\overline2^2=\overline0$. La classe $\overline2$ n’est donc pas inversible.

Le petit théorème de Fermat

La primalité du module est une hypothèse

Si $p$ est premier et si $p\nmid a$, alors $$\boxed{a^{p-1}\equiv1\pmod p}.$$ Pour tout entier $a$, y compris les multiples de $p$, on a $a^p\equiv a\pmod p$.

Pourquoi la formule est vraie

Lorsque $a$ est inversible modulo $p$, multiplier les classes $1,2,\ldots,p-1$ par $a$ les permute : deux images égales auraient, après simplification, le même antécédent. Le produit des classes est donc inchangé : $$a^{p-1}(p-1)!\equiv(p-1)!\pmod p.$$ Aucun facteur de $(p-1)!$ n’est divisible par $p$, donc ce produit est inversible modulo $p$. La simplification donne Fermat. La formule $a^p\equiv a$ s’en déduit si $p\nmid a$ ; si $p\mid a$, les deux membres sont congrus à $0$.

Réduire un exposant

Pour calculer un reste, on écrit l’exposant comme multiple de $p-1$ plus un reste. Par exemple, $13$ est premier et ne divise pas $2$, donc $$2^{100}= (2^{12})^8\,2^4\equiv16\equiv3\pmod{13}.$$ La réduction de l’exposant modulo $p-1$ utilise ici le fait que la base est inversible. On ne remplace pas sans condition $a^0$ par un reste issu d’une base divisible par $p$.

La réciproque est fausse

La congruence $a^{m-1}\equiv1\pmod m$ pour une base particulière ne prouve pas que $m$ est premier. Par exemple, $341=11\times31$ est composé, mais $$2^{10}=1024=3\times341+1\quad\Longrightarrow\quad 2^{340}=(2^{10})^{34}\equiv1\pmod{341}.$$ Fermat fournit une conséquence de la primalité ; il ne constitue pas, sous cette seule forme, un critère réciproque de primalité.

Exemple - Associer Gauss et Fermat

Pour un premier $p$ et un entier $a$ non multiple de $p$, la classe $a^{p-2}$ est un inverse de $a$, puisque $a\,a^{p-2}=a^{p-1}\equiv1$. Cet inverse peut aussi être obtenu par Euclide étendu ; la méthode la plus courte dépend des nombres.

Rester dans le bon ensemble

Un inverse modulo $n$ est une classe d’entiers, pas la fraction réelle $1/a$. Écrire $a^{-1}$ dans $\mathbb{Z}/n\mathbb{Z}$ exige d’abord $\operatorname{pgcd}(a,n)=1$.

Écrire et calculer dans une base

La valeur d’une écriture positionnelle

En base entière $b\ge2$, les chiffres possibles sont $0,1,\ldots,b-1$. Une écriture de nombre naturel $$N=(a_ka_{k-1}\cdots a_0)_b$$ signifie $N=\sum_{i=0}^k a_ib^i$, avec $a_k\ne0$ si $N>0$. Ainsi $(101101)_2=32+8+4+1=45$ et $(234)_5=2\times25+3\times5+4=69$. Une écriture contenant le chiffre $7$ n’est pas valable en base $5$.

Les divisions successives produisent les chiffres

La division $N=bq_0+a_0$ donne le chiffre des unités. On divise ensuite $q_0$ par $b$ pour obtenir $a_1$, puis on continue jusqu’au quotient nul. Les restes se lisent du dernier au premier. L’unicité des divisions donne l’unicité de l’écriture.

Exemple - Convertir $83$ en base $5$

$$83=5\times16+3,\quad16=5\times3+1,\quad3=5\times0+3.$$ Donc $83=(313)_5$. Le contrôle inverse donne $3\times25+1\times5+3=83$.

Additionner avec des retenues de taille $b$

En base $5$, calculons $(243)_5+(134)_5$. Aux unités, $3+4=7=5+2$ : on écrit $2$ et retient $1$. À la colonne suivante, $4+3+1=8=5+3$ : on écrit $3$ et retient $1$. Enfin, $2+1+1=4$. Ainsi $$\begin{array}{r}243_5\\+\ 134_5\\\hline432_5\end{array}$$ Le contrôle décimal est $73+44=117=4\times25+3\times5+2$.

Multiplier en conservant les positions

Pour $(23)_5(14)_5$, on multiplie d’abord par $4$ : $4\times3=12=2\times5+2$, puis $4\times2+2=10=2\times5$. Le premier produit est $(202)_5$. Le produit par le chiffre $1$ placé dans la colonne des cinq est $(230)_5$. Leur somme donne $$(23)_5(14)_5=(202)_5+(230)_5=(432)_5.$$ On vérifie en base $10$ : $13\times9=117$.

Une base ne change pas le nombre

Les écritures $83$ et $(313)_5$ représentent le même entier. Les congruences, le PGCD et la divisibilité concernent cet entier ; la base concerne sa représentation.

Synthèse : PGCD, PPCM et codage simple

Utiliser les exposants premiers

Si $a$ et $b$ sont positifs, leur PGCD prend, pour chaque facteur premier, le plus petit des deux exposants ; leur PPCM prend le plus grand. Ainsi $$\operatorname{pgcd}(a,b)\operatorname{ppcm}(a,b)=ab.$$ Cette identité est valable pour deux entiers positifs ; elle ne se prolonge pas sous la même forme à trois entiers.

Exemple - Deux décompositions compatibles

$$756=2^2\,3^3\,7,\qquad360=2^3\,3^2\,5.$$ Donc le PGCD est $2^2\,3^2=36$, et le PPCM est $2^3\,3^3\,5\,7=7560$. Le produit $36\times7560$ égale bien $756\times360$.

Un codage affine sur les lettres

Associons aux lettres A à Z les entiers de $0$ à $25$. Le codage $$y\equiv5x+8\pmod{26}$$ associe à chaque lettre une autre lettre. Il est réversible parce que $\operatorname{pgcd}(5,26)=1$. Comme $5\times21\equiv1\pmod{26}$, le décodage est $$x\equiv21(y-8)\pmod{26}.$$ Par exemple, D correspond à $x=3$, donc $y=23$, soit X. Inversement, X donne $21(23-8)=315\equiv3\pmod{26}$, soit D.

Pourquoi la coprimalité est décisive

Si l’on utilisait $y\equiv13x+8\pmod{26}$, les valeurs $x=0$ et $x=2$ donneraient toutes deux $y=8$. Le codage ne serait pas injectif et une lettre codée ne déterminerait pas une lettre d’origine unique.

Décrire ce que l’on démontre

Bézout produit une combinaison ; Gauss autorise une divisibilité après simplification ; Fermat réduit certaines puissances ; les divisions euclidiennes donnent à la fois des PGCD et des chiffres dans une base. Choisir l’outil en fonction de la conclusion cherchée.

Une vérification indépendante

Après un calcul, remplacer les solutions dans l’équation initiale, reconstituer un entier depuis ses chiffres ou multiplier un inverse par son coefficient. Ces vérifications courtes ne remplacent pas la preuve de complétude, mais elles détectent efficacement les erreurs numériques.

Exercices corrigés

Exercice 1 - Euclide, Bézout et PPCM

Déterminer le PGCD de $391$ et $299$, des coefficients de Bézout et leur PPCM. Solution. Les divisions sont $$391=299+92,\quad299=3\times92+23,\quad92=4\times23.$$ Le PGCD vaut $23$. En remontant, $23=299-3\times92=4\times299-3\times391$. Les coefficients $(-3,4)$ conviennent. Le PPCM vaut $391\times299/23=391\times13=5083$.

Exercice 2 - Résoudre dans $\mathbb{Z}^2$, puis dans $\mathbb{N}^2$

Résoudre $7x+11y=100$. Solution. Le PGCD de $7$ et $11$ vaut $1$, donc des solutions existent. Le couple $(8,4)$ convient. Toutes les solutions entières sont $$x=8+11t,\qquad y=4-7t,\qquad t\in\mathbb{Z}.$$ Pour $x,y\ge0$, on exige $t\ge-8/11$ et $t\le4/7$. Le seul entier possible est $t=0$, donc l’unique solution naturelle est $(8,4)$.

Exercice 3 - Une divisibilité avec un paramètre

Déterminer les entiers $n\ge1$ tels que $n\mid(2n+1)(n+3)$. Solution. Tout diviseur commun de $n$ et $2n+1$ divise $(2n+1)-2n=1$. Leur PGCD vaut donc $1$. Gauss donne $n\mid n+3$, soit $n\mid3$. Les candidats sont $1$ et $3$. Réciproquement, chacun divise $n+3$, donc chacun satisfait la condition initiale. L’ensemble solution est $\{1,3\}$.

Exercice 4 - Une congruence non inversible au départ

Résoudre $6x\equiv9\pmod{15}$. Solution. Le PGCD de $6$ et $15$ vaut $3$, qui divise $9$. On réduit l’équation et le module : $2x\equiv3\pmod5$. L’inverse de $2$ modulo $5$ est $3$, donc $x\equiv9\equiv4\pmod5$. Il s’agit des trois classes $4$, $9$ et $14$ modulo $15$. On vérifie que $6$ fois chacun de ces représentants est congru à $9$ modulo $15$.

Exercice 5 - Une grande puissance

Déterminer le reste de $7^{222}$ dans la division par $11$. Solution. $11$ est premier et ne divise pas $7$. Fermat donne $7^{10}\equiv1\pmod{11}$. Comme $222=22\times10+2$, $$7^{222}\equiv7^2=49\equiv5\pmod{11}.$$ Le reste euclidien est donc $5$, qui appartient bien à $\{0,\ldots,10\}$.

Exercice 6 - Changer de base et y calculer

Écrire $173$ en base $5$. En base $4$, calculer $(132)_4+(23)_4$ et $(12)_4(13)_4$. Solution. Les divisions $173=5\times34+3$, $34=5\times6+4$, $6=5\times1+1$, $1=5\times0+1$ donnent $(1143)_5$. Le contrôle vaut $125+25+20+3=173$.

Pour l’addition en base $4$, $2+3=5=4+1$ donne le chiffre $1$ et une retenue. Puis $3+2+1=6=4+2$ donne $2$ et une retenue ; enfin $1+1=2$. Le résultat est $(221)_4$.

Pour le produit, multiplier $(12)_4$ par $3$ donne $(102)_4$, puis multiplier par le chiffre $1$ des quatre donne $(120)_4$. La somme est $(222)_4$. Les contrôles décimaux sont $30+11=41$ et $6\times7=42$.

Exercice 7 - Les inversibles modulo $12$

Déterminer toutes les classes inversibles de $\mathbb{Z}/12\mathbb{Z}$ et leurs inverses. Solution. Parmi $0,1,\ldots,11$, seuls $1,5,7,11$ sont premiers avec $12$. Ce sont les quatre classes inversibles. Chacune est son propre inverse, car $$1^2\equiv5^2\equiv7^2\equiv11^2\equiv1\pmod{12}.$$ Les autres classes ont un représentant ayant un diviseur commun non trivial avec $12$ ; Bézout interdit un inverse. Par exemple, $\overline2\,\overline6=\overline0$ avec deux classes non nulles.

Exercice 8 - Une propriété des nombres premiers

Montrer que, pour tout nombre premier $p>3$, $24\mid(p^2-1)$. Solution. $p$ est impair, donc $p-1$ et $p+1$ sont deux entiers pairs consécutifs parmi les pairs. L’un est divisible par $4$, l’autre par $2$ : leur produit est divisible par $8$. De plus, $p$ n’est pas divisible par $3$, donc son reste modulo $3$ est $1$ ou $2$ ; l’un de $p-1,p+1$ est divisible par $3$. Le produit est divisible par $3$ et par $8$. Ces nombres étant premiers entre eux, il est divisible par $24$.

Exercice 9 - Décoder et repérer un codage non injectif

Avec A$=0$, B$=1$, …, Z$=25$, on code par $y\equiv5x+8\pmod{26}$. Décoder les lettres X et F. Expliquer pourquoi remplacer $5$ par $13$ empêcherait un décodage unique. Solution. Puisque $5\times21=105\equiv1\pmod{26}$, on a $x\equiv21(y-8)\pmod{26}$. Pour X, $y=23$, donc $x\equiv315\equiv3$ : c’est D. Pour F, $y=5$, donc $x\equiv-63\equiv15$ : c’est P. Le contrôle de P donne $5\times15+8=83\equiv5$, soit F.

Avec le coefficient $13$, les valeurs $x=0$ et $x=2$ produisent toutes deux le reste $8$. Deux lettres distinctes auraient la même image. Le défaut est exactement $\operatorname{pgcd}(13,26)\ne1$.

Exercice 10 - Deux conditions sur les restes

Déterminer les entiers $x$ tels que $x\equiv2\pmod3$ et $x\equiv3\pmod5$, puis ceux situés dans $[0;100]$. Solution. La première condition donne $x=2+3k$, $k\in\mathbb{Z}$. La seconde devient $3k\equiv1\pmod5$. Comme l’inverse de $3$ modulo $5$ est $2$, on obtient $k\equiv2\pmod5$, soit $k=2+5t$. Ainsi $$x=8+15t,\qquad t\in\mathbb{Z}.$$ Réciproquement, tous ces nombres satisfont les deux congruences. Dans $[0;100]$, les entiers admissibles sont $t=0,1,\ldots,6$, donc $$8,\ 23,\ 38,\ 53,\ 68,\ 83,\ 98.$$ Le module $15$ apparaît parce qu’ajouter un multiple de $15$ préserve les deux restes ; la substitution a prouvé qu’aucune autre classe ne convient.

Rédiger la conclusion au bon niveau

Une solution modulo $n$ est une classe ; une solution dans un intervalle est une liste d’entiers ; une équation dans $\mathbb{Z}^2$ exige tous les couples paramétrés. Préciser l’ensemble recherché empêche de confondre ces trois types de réponses.