Arithmétique des entiers
L’arithmétique étudie les propriétés des nombres entiers :
- divisibilité ;
- nombres premiers ;
- plus grand commun diviseur ;
- congruences ;
- équations à solutions entières.
Elle intervient en cryptographie, en algorithmique, dans les systèmes de codage et dans de nombreux problèmes de périodicité.
Dans l’ensemble des nombres réels, on peut presque toujours diviser.
Dans l’ensemble des entiers, la question change :
“Le résultat de la division est-il encore un entier ?
Par exemple :
\[ 12=3\times 4, \]
donc \(3\) divise \(12\).
En revanche, il n’existe aucun entier \(k\) tel que :
\[ 10=3k. \]
Ainsi, \(3\) ne divise pas \(10\).
L’arithmétique consiste notamment à comprendre ces relations de divisibilité et à les exploiter efficacement.
Divisibilité dans \(\mathbb Z\)
Soient \(a\) et \(b\) deux entiers relatifs.
On dit que \(a\) divise \(b\) lorsqu’il existe un entier \(k\) tel que :
\[ b=ak. \]
On écrit alors :
\[ a\mid b. \]
Si \(a\) ne divise pas \(b\), on écrit :
\[ a\nmid b. \]
Comme :
\[ 42=6\times 7, \]
on a :
\[ 6\mid 42. \]
Comme :
\[ -36=9\times(-4), \]
on a également :
\[ 9\mid -36. \]
En revanche :
\[ 5\nmid 42. \]
Diviseurs et multiples
Si \(a\mid b\), alors :
- \(a\) est un diviseur de \(b\) ;
- \(b\) est un multiple de \(a\).
Par exemple, les diviseurs positifs de \(12\) sont :
\[ 1,\ 2,\ 3,\ 4,\ 6,\ 12. \]
Pour tous entiers \(a\), \(b\), \(c\), \(m\) et \(n\) :
1. \[ a\mid a; \]
2. \[ a\mid 0; \]
- si \(a\mid b\) et \(b\mid c\), alors :
\[ a\mid c; \]
- si \(a\mid b\) et \(a\mid c\), alors :
\[ a\mid mb+nc. \]
Supposons :
\[ a\mid b \qquad\text{et}\qquad a\mid c. \]
Il existe donc deux entiers \(p\) et \(q\) tels que :
\[ b=ap \qquad\text{et}\qquad c=aq. \]
Pour tous entiers \(m\) et \(n\) :
\[ mb+nc = map+naq = a(mp+nq). \]
Comme \(mp+nq\in\mathbb Z\), on obtient :
\[ a\mid mb+nc. \]
L’écriture :
\[ a\mid b \]
n’est pas une fraction.
Elle se lit :
“\(a\) divise \(b\).
Elle signifie que le quotient \(\frac ba\) est un entier.
Division euclidienne
Soient \(a\in\mathbb Z\) et \(b\in\mathbb N^*\).
Il existe un unique couple d’entiers \((q,r)\) tel que :
\[ a=bq+r \]
avec :
\[ 0\leq r<b. \]
L’entier \(q\) est le quotient et \(r\) est le reste.
On cherche \(q\) et \(r\) tels que :
\[ 157=12q+r \]
avec :
\[ 0\leq r<12. \]
Comme :
\[ 157=12\times 13+1, \]
le quotient est \(13\) et le reste est \(1\).
Effectuons la division euclidienne de \(-17\) par \(5\).
On doit avoir :
\[ -17=5q+r \]
avec :
\[ 0\leq r<5. \]
Or :
\[ -17=5\times(-4)+3. \]
Ainsi :
\[ q=-4 \qquad\text{et}\qquad r=3. \]
Critère de divisibilité par le reste
Dans la division euclidienne :
\[ a=bq+r, \]
on a :
\[ b\mid a \]
si et seulement si :
\[ r=0. \]
Plus grand commun diviseur
Soient \(a\) et \(b\) deux entiers non tous deux nuls.
Le plus grand entier naturel divisant à la fois \(a\) et \(b\) est appelé leur plus grand commun diviseur.
On le note :
\[ \operatorname{pgcd}(a,b). \]
Les diviseurs positifs de \(18\) sont :
\[ 1,\ 2,\ 3,\ 6,\ 9,\ 18. \]
Les diviseurs positifs de \(30\) sont :
\[ 1,\ 2,\ 3,\ 5,\ 6,\ 10,\ 15,\ 30. \]
Le plus grand diviseur commun est \(6\). Donc :
\[ \operatorname{pgcd}(18,30)=6. \]
Nombres premiers entre eux
Deux entiers \(a\) et \(b\) sont premiers entre eux lorsque :
\[ \operatorname{pgcd}(a,b)=1. \]
Par exemple :
\[ \operatorname{pgcd}(8,15)=1. \]
Les entiers \(8\) et \(15\) sont donc premiers entre eux.
Algorithme d’Euclide
Le calcul par liste des diviseurs devient inefficace pour de grands nombres.
L’algorithme d’Euclide utilise des divisions successives.
Si :
\[ a=bq+r, \]
alors :
\[ \operatorname{pgcd}(a,b) = \operatorname{pgcd}(b,r). \]
Pour calculer \(\operatorname{pgcd}(a,b)\), avec \(a>b>0\) :
- effectuer la division euclidienne de \(a\) par \(b\) ;
- remplacer le couple \((a,b)\) par \((b,r)\) ;
- recommencer tant que le reste est non nul ;
- le dernier reste non nul est le PGCD.
On effectue les divisions successives :
\[ 252=198\times 1+54, \]
\[ 198=54\times 3+36, \]
\[ 54=36\times 1+18, \]
\[ 36=18\times 2+0. \]
Le dernier reste non nul est \(18\). Donc :
\[ \boxed{\operatorname{pgcd}(252,198)=18}. \]
Chaque division remplace le couple étudié par le diviseur et le reste. Le dernier reste non nul est le PGCD.
Identité de Bézout
Soient \(a\) et \(b\) deux entiers non tous deux nuls.
Il existe deux entiers \(u\) et \(v\) tels que :
\[ au+bv = \operatorname{pgcd}(a,b). \]
Une telle égalité est appelée identité de Bézout.
Algorithme d’Euclide étendu
Pour déterminer \(u\) et \(v\), on remonte les divisions de l’algorithme d’Euclide.
Nous avons obtenu :
\[ 252=198+54, \]
\[ 198=3\times 54+36, \]
\[ 54=36+18. \]
On remonte :
\[ 18=54-36. \]
Or :
\[ 36=198-3\times 54. \]
Donc :
\[ 18 = 54-(198-3\times 54) = 4\times 54-198. \]
Comme :
\[ 54=252-198, \]
on obtient :
\[ 18 = 4(252-198)-198. \]
Ainsi :
\[ \boxed{18=4\times252-5\times198}. \]
Les coefficients de Bézout sont donc :
\[ u=4 \qquad\text{et}\qquad v=-5. \]
Les entiers \(a\) et \(b\) sont premiers entre eux si et seulement s’il existe deux entiers \(u\) et \(v\) tels que :
\[ au+bv=1. \]
Si \((u_0,v_0)\) vérifie :
\[ au_0+bv_0=d, \]
alors il existe généralement une infinité d’autres couples vérifiant la même égalité.
Théorème de Gauss
Soient \(a\), \(b\) et \(c\) trois entiers.
Si :
\[ a\mid bc \]
et si \(a\) et \(b\) sont premiers entre eux, alors :
\[ a\mid c. \]
Puisque \(a\) et \(b\) sont premiers entre eux, il existe \(u,v\in\mathbb Z\) tels que :
\[ au+bv=1. \]
En multipliant par \(c\) :
\[ acu+bcv=c. \]
Or :
\[ a\mid acu. \]
Par hypothèse :
\[ a\mid bc, \]
donc :
\[ a\mid bcv. \]
Ainsi, \(a\) divise la somme :
\[ acu+bcv=c. \]
Par conséquent :
\[ a\mid c. \]
Si :
\[ a\mid c, \qquad b\mid c \]
et si \(a\) et \(b\) sont premiers entre eux, alors :
\[ ab\mid c. \]
Supposons :
\[ 12\mid 35n. \]
Comme :
\[ \operatorname{pgcd}(12,35)=1, \]
le théorème de Gauss donne :
\[ 12\mid n. \]
Nombres premiers
Un entier naturel \(p\geq 2\) est premier lorsqu’il possède exactement deux diviseurs positifs :
\[ 1 \qquad\text{et}\qquad p. \]
Les premiers nombres premiers sont :
\[ 2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ldots \]
Le nombre \(1\) ne possède qu’un seul diviseur positif.
Il n’est donc pas premier.
Tester si un nombre est premier
Pour déterminer si un entier \(n\geq 2\) est premier, il suffit de vérifier qu’il n’est divisible par aucun nombre premier inférieur ou égal à :
\[ \sqrt n. \]
On a :
\[ \sqrt{97}\approx 9{,}85. \]
Il suffit donc de tester les nombres premiers :
\[ 2,\ 3,\ 5,\ 7. \]
Le nombre \(97\) n’est divisible par aucun d’eux.
Donc \(97\) est premier.
Décomposition en facteurs premiers
Tout entier naturel \(n\geq 2\) peut s’écrire de manière unique, à l’ordre des facteurs près, sous la forme :
\[ n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}, \]
où les \(p_i\) sont des nombres premiers distincts et les \(\alpha_i\) des entiers naturels non nuls.
On effectue les divisions successives :
\[ 756=2\times378, \]
\[ 378=2\times189, \]
\[ 189=3\times63, \]
\[ 63=3\times21, \]
\[ 21=3\times7. \]
Ainsi :
\[ \boxed{756=2^2\times3^3\times7}. \]
PGCD et décomposition première
Si :
\[ a = \prod p_i^{\alpha_i} \]
et :
\[ b = \prod p_i^{\beta_i}, \]
alors :
\[ \operatorname{pgcd}(a,b) = \prod p_i^{\min(\alpha_i,\beta_i)}. \]
On a :
\[ 360=2^3\times3^2\times5, \]
\[ 504=2^3\times3^2\times7. \]
Donc :
\[ \operatorname{pgcd}(360,504) = 2^3\times3^2 = 72. \]
Congruences
Les congruences permettent de raisonner directement sur les restes des divisions euclidiennes.
Soient \(a\), \(b\) deux entiers et \(n\geq 1\).
On dit que \(a\) est congru à \(b\) modulo \(n\) lorsque :
\[ n\mid(a-b). \]
On écrit :
\[ a\equiv b\pmod n. \]
On a :
\[ a\equiv b\pmod n \]
si et seulement si \(a\) et \(b\) ont le même reste dans leur division euclidienne par \(n\).
Comme :
\[ 38-3=35=5\times7, \]
on a :
\[ 38\equiv3\pmod5. \]
De même :
\[ -2\equiv5\pmod7, \]
car :
\[ -2-5=-7. \]
Deux entiers sont congrus modulo \(n\) lorsqu’ils occupent la même position sur une horloge comportant \(n\) graduations.
Opérations sur les congruences
Si :
\[ a\equiv b\pmod n \]
et :
\[ c\equiv d\pmod n, \]
alors :
\[ a+c\equiv b+d\pmod n, \]
\[ a-c\equiv b-d\pmod n, \]
\[ ac\equiv bd\pmod n. \]
Pour tout entier naturel \(k\) :
\[ a^k\equiv b^k\pmod n. \]
Calculons le reste de :
\[ 7^{2026} \]
dans la division par \(10\).
Les puissances de \(7\) modulo \(10\) suivent le cycle :
\[ 7^1\equiv7, \]
\[ 7^2\equiv9, \]
\[ 7^3\equiv3, \]
\[ 7^4\equiv1 \pmod{10}. \]
Le cycle est de longueur \(4\).
Or :
\[ 2026\equiv2\pmod4. \]
Donc :
\[ 7^{2026}\equiv7^2\equiv9\pmod{10}. \]
Le chiffre des unités de \(7^{2026}\) est donc \(9\).
Critères de divisibilité
Les congruences permettent de justifier plusieurs critères usuels.
Comme :
\[ 10\equiv1\pmod3, \]
on a également :
\[ 10^k\equiv1\pmod3. \]
Ainsi, un entier est congru modulo \(3\) à la somme de ses chiffres.
On obtient le même résultat modulo \(9\).
Diviseur | Critère de divisibilité |
|---|---|
\(2\) | Le chiffre des unités est pair. |
\(3\) | La somme des chiffres est divisible par \(3\). |
\(5\) | Le chiffre des unités est \(0\) ou \(5\). |
\(9\) | La somme des chiffres est divisible par \(9\). |
\(10\) | Le chiffre des unités est \(0\). |
Équations congruentielles
On cherche parfois les entiers \(x\) vérifiant :
\[ ax\equiv b\pmod n. \]
La congruence :
\[ ax\equiv b\pmod n \]
admet une solution si et seulement si :
\[ \operatorname{pgcd}(a,n)\mid b. \]
On calcule :
\[ \operatorname{pgcd}(14,20)=2. \]
Comme :
\[ 2\mid8, \]
la congruence admet des solutions.
On divise par \(2\) :
\[ 7x\equiv4\pmod{10}. \]
Or :
\[ 7\times3=21\equiv1\pmod{10}. \]
On multiplie donc par \(3\) :
\[ x\equiv12\pmod{10}. \]
Ainsi :
\[ x\equiv2\pmod{10}. \]
Modulo \(20\), cela donne deux classes de solutions :
\[ \boxed{x\equiv2\pmod{20}} \]
ou :
\[ \boxed{x\equiv12\pmod{20}}. \]
À partir de :
\[ ac\equiv bc\pmod n, \]
on ne peut pas toujours conclure :
\[ a\equiv b\pmod n. \]
La simplification est possible lorsque \(c\) est premier avec \(n\).
Équations diophantiennes linéaires
Une équation diophantienne est une équation dont on recherche les solutions entières.
Nous étudions les équations :
\[ ax+by=c. \]
L’équation :
\[ ax+by=c \]
admet des solutions entières si et seulement si :
\[ \operatorname{pgcd}(a,b)\mid c. \]
- Calculer :
\[ d=\operatorname{pgcd}(a,b). \]
- Vérifier que :
\[ d\mid c. \]
- Déterminer une identité de Bézout :
\[ au+bv=d. \]
- Multiplier par :
\[ \frac cd \]
pour obtenir une solution particulière.
- Écrire toutes les solutions.
Si \((x_0,y_0)\) est une solution particulière de :
\[ ax+by=c \]
et si :
\[ d=\operatorname{pgcd}(a,b), \]
alors toutes les solutions sont :
\[ x=x_0+\frac bd k, \]
\[ y=y_0-\frac ad k, \qquad k\in\mathbb Z. \]
On calcule :
\[ \operatorname{pgcd}(84,30)=6. \]
Comme :
\[ 6\mid6, \]
l’équation admet des solutions.
On simplifie :
\[ 14x+5y=1. \]
Or :
\[ 1=3\times5-14. \]
Ainsi, une solution particulière est :
\[ x_0=-1, \qquad y_0=3. \]
Toutes les solutions sont donc :
\[ \boxed{x=-1+5k} \]
et :
\[ \boxed{y=3-14k}, \qquad k\in\mathbb Z. \]
Exercices diagnostiques et progressifs
Diagnostic
Divisibilité et division euclidienne
- Indiquer si les affirmations suivantes sont vraies :
\[ 7\mid84, \qquad 9\mid145, \qquad 11\mid0, \qquad 6\mid(-42). \]
- Effectuer les divisions euclidiennes :
- de \(173\) par \(15\) ;
- de \(-23\) par \(7\).
Algorithme d’Euclide
PGCD et identité de Bézout
- Calculer :
\[ \operatorname{pgcd}(252,198). \]
- Déterminer deux entiers \(u\) et \(v\) tels que :
\[ 252u+198v = \operatorname{pgcd}(252,198). \]
Nombres premiers
Décomposition en facteurs premiers
Décomposer en facteurs premiers :
\[ 756 \qquad\text{et}\qquad 1386. \]
En déduire leur PGCD.
Théorème de Gauss
Exploiter des entiers premiers entre eux
Soit \(n\in\mathbb Z\).
On suppose que :
\[ 35n \]
est divisible par \(12\).
Démontrer que \(n\) est divisible par \(12\).
Puissances et congruences
Chiffre des unités d’une grande puissance
Déterminer le chiffre des unités de :
\[ 7^{2026}. \]
Équation congruentielle
Résoudre une congruence linéaire
Résoudre dans \(\mathbb Z\) :
\[ 14x\equiv8\pmod{20}. \]
Équation diophantienne
Répartition de matériels
Un service dispose de lots contenant respectivement \(84\) et \(30\) unités.
On souhaite résoudre l’équation :
\[ 84x+30y=6, \]
où \(x\) et \(y\) sont des entiers relatifs.
- Justifier que l’équation possède des solutions.
- Déterminer une solution particulière.
- Déterminer toutes les solutions entières.
Pont vers l’Université
À l’Université, les congruences sont interprétées comme des calculs dans des ensembles quotients :
\[ \mathbb Z/n\mathbb Z. \]
Les entiers y sont regroupés selon leur reste modulo \(n\).
Par exemple, modulo \(5\), tous les entiers appartiennent à l’une des cinq classes :
\[ \overline0,\ \overline1,\ \overline2,\ \overline3,\ \overline4. \]
L’arithmétique modulaire permet notamment :
- la construction de codes correcteurs ;
- le chiffrement des données ;
- la vérification de l’intégrité des messages ;
- la génération de clés cryptographiques ;
- la conception de protocoles sécurisés.
Le système RSA repose en particulier sur :
- les nombres premiers ;
- la décomposition en facteurs premiers ;
- les congruences ;
- l’identité de Bézout ;
- le calcul d’inverses modulo un entier.
L’algorithme d’Euclide étudié au lycée est donc déjà un véritable algorithme de cryptographie.
Divisibilité
\[ a\mid b \iff \exists k\in\mathbb Z,\quad b=ak. \]
Si :
\[ a\mid b \qquad\text{et}\qquad a\mid c, \]
alors, pour tous \(m,n\in\mathbb Z\) :
\[ a\mid mb+nc. \]
Division euclidienne
Pour \(b>0\) :
\[ a=bq+r, \qquad 0\leq r<b. \]
PGCD
L’algorithme d’Euclide repose sur :
\[ \operatorname{pgcd}(a,b) = \operatorname{pgcd}(b,r), \]
lorsque :
\[ a=bq+r. \]
Bézout
Il existe \(u,v\in\mathbb Z\) tels que :
\[ au+bv = \operatorname{pgcd}(a,b). \]
En particulier :
\[ \operatorname{pgcd}(a,b)=1 \iff \exists u,v\in\mathbb Z,\quad au+bv=1. \]
Gauss
Si :
\[ a\mid bc \]
et :
\[ \operatorname{pgcd}(a,b)=1, \]
alors :
\[ a\mid c. \]
Congruences
\[ a\equiv b\pmod n \iff n\mid(a-b). \]
Les congruences sont compatibles avec l’addition, la soustraction et la multiplication.
Équation diophantienne
L’équation :
\[ ax+by=c \]
admet des solutions entières si et seulement si :
\[ \operatorname{pgcd}(a,b)\mid c. \]
Si \((x_0,y_0)\) est une solution particulière et si :
\[ d=\operatorname{pgcd}(a,b), \]
alors :
\[ x=x_0+\frac bd k, \]
\[ y=y_0-\frac ad k, \qquad k\in\mathbb Z. \]