Arithmétique et applications

Arithmétique et applications#

Systèmes numériques#

Nombres et notation positionnelle#

Les nombres sont l’un des objets mathématiques les plus élémentaires, avec lesquels nous interagissons quotidiennement : nous les utilisons pour compter, ordonner, étiqueter, coder.

Tout au long de l’histoire, les nombres ont été représentés de diverses manières, par exemple :

$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
	I	II	III	IV	V	VI	VII	VIII	IX	X
੦	੧	੨	੩	੪	੫	੬	੭	੮	੯	੧੦
	Α	Β	Γ	Δ	Ε	Ϝ	Ζ	Η	Θ	Ι

Parmi ceux-ci, le plus répandu est, le système numéral indo-arabe, inventé entre le 1er et le 4e siècle par des mathématiciens indiens, puis adopté par la suite par des mathématiciens arabes et persans au cours du 9e siècle. Ce système s’est ensuite répandu en Europe au cours du 13e siècle, où il n’a pas été largement adopté avant le 15e siècle.

Le système numéral indo-arabe fonctionne comme suit :

Un nombre naturel s’écrit sous la forme d’une séquence de symboles tirés de l’alphabet $0,1,2,3,4,5,6,7,8,9$, qui correspondent aux 10 premiers nombres naturels.
La valeur représentée par une telle séquence est la somme de la valeur de chaque chiffre multipliée par une puissance de $10$ : en lisant un numéral de droite à gauche, le $n$-ième chiffre est multiplié par $10^{n-1}$.

Par exemple, le chiffre $123$ représente le nombre $1 \cdot 10^2 + 2 \cdot 10^1

3 \cdot 10^1 = 100 + 20 + 3$. Nous pouvons généraliser le système numéral indo-arabe pour obtenir des systèmes qui utilisent la notation positionnelle :

Les nombres sont représentés par des séquences de symboles, appelés chiffres, tirés d’un alphabet fini.
La valeur représentée par un numéral (une séquence de symboles) est la valeur représentée par le symbole

multipliée par un facteur déterminé par la position du symbole dans la séquence.

Le facteur est généralement la puissance d’un nombre fixe $b$, appelé la base du système.

Par exemple, le système numéral indo-arabe est un système de notation positionnelle en base 10 qui utilise les chiffres habituels de $0$ à $9$.

D’autres bases historiquement significatives sont 8, 12, 20, 60, qui ont été largement utilisées par diverses cultures, des Babyloniens aux Mayas.

Pour qu’un nombre ait une représentation unique dans un tel système, il faut que le nombre de chiffres soit $b-1$. Pour les bases $b \leq 10$, les chiffres sont dessinés en utilisant les mêmes symboles $0, 1, \dots 9$ que ceux utilisés pour la base 10.

Pour les bases $b \geq 10$, nous devons inventer de nouveaux symboles pour représenter les valeurs supérieures à 9. Par exemple, dans un système en base 16, nous ajoutons à l’alphabet des chiffres les lettres $A, B, C, D, E, F$ qui correspondent à $10, 11, 12, 13, 14, 15$ en base-10.

En informatique, on utilise souvent les systèmes binaire (base 2) et hexadécimal (base 16). Par exemple, le nombre vingt a les représentations suivantes en base 2, 10, 16 :

En base 2 : $(10100)_2 = 1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 0 \cdot 2^0$,
En base 10 : $(20)_{10} = 2 \cdot 10^1 + 0 \cdot 10^0$,
En base 16 : $(14)_{16} = 1 \cdot 16^1 + 4 \cdot 16^0$,

où la notation $(\cdot)_{b}$ signifie que le chiffre entre parenthèses doit être interprété en base $b$.

De même, le nombre 29 s’écrit $(11101)_2, (1D)_{16}$ en binaire et en hexadécimal. Plus généralement, on peut décomposer un nombre $N$ dans n’importe quelle base $b$ comme suit :

\[ N = \sum\limits_{i=0}^n N_i b^i \]

où $n \in \mathbb{N}$, $N_i$ sont les coefficients dans $[0,b-1]$ et $N_n$ est non nul. Ces coefficients $N_i$ sont appelés « bits » dans le cas binaire (base-2). Les nombres Les nombres $n, b, N$ sont liés par la formule suivante :

\[ n = \left\lfloor \frac{log(N)}{log(b)} \right\rfloor = \left\lfloor \log_b(N) \right\rfloor.\]

où $\lfloor \cdot \rfloor$ est la fonction de la partie entière, $\log$ est le logarithme en base 10, et $\log_b$ est le logarithme en base $b$.

Conversion des bases#

Comme nous l’avons vu, tout nombre peut être représenté dans différentes bases. Comment convertir convertir entre ces différentes représentations ? La réponse est donnée par la division euclidienne répétée, mais il y a un problème : quelle base devons-nous utiliser pour effectuer nos calculs ?

Supposons que nous rencontrions un membre d’une civilisation extraterrestre qui ne sait faire que del’arithmétique en base 4, notamment la division euclidienne, et qui veut convertir $(32)_4$ en son équivalent en base 8.

Pour aider notre ami extraterrestre, nous devons d’abord construire une table de recherche de base $T$ qui contient les huit premiers chiffres écrits dans les deux bases.

1	2	3	10	11	12	13	20
1	2	3	4	5	6	7	10

Nous pourrions alors procéder comme suit :

Calculer le quotient $q$ et le reste $r$ de la division euclidienne de $(32)_4$ par $(20)_4$ (rappelons que nous travaillons en base 4) : $q = (1)_4, r = (12)_4$.
Convertir $(12)_4$ en $(6)_8$ à l’aide de notre table de correspondance.
Répéter cette procédure en divisant $(1)_4$ par $(20)_4$ donne $q = 0, r = 1$.
Convertir $(1)_4$ en $(1)_8$ à l’aide de notre table de correspondance.
Concaténer les deux nombres (de droite à gauche) pour obtenir le résultat souhaité $(16)_8$.

Nous avons donc calculé que $(32)_4$ est $(16)_8$. Une telle procédure peut être assez lourde car :

Elle nous oblige à créer une table de correspondance pour convertir les chiffres des deux bases.
Elle nous oblige à faire de l’arithmétique dans des bases autres que 10, ce qui n’est pas toujours intuitif !

En pratique, nous convertissons donc généralement entre deux bases $b$ et $b'$ en convertissant d’abord en base $10$, puis de là en base $10$, en profitant de notre familiarité avec la division en en base 10.

Enfin, il existe diverses astuces pour passer rapidement d’une base à l’autre. Pour les informaticiens, particulièrement utile est l’astuce suivante pour passer du binaire à l’hexadécimal et inversement et vice-versa :

Soit $N$ un nombre écrit en base-2.
Diviser $N$ en groupes de $4$, en ajoutant 0 au début si nécessaire.
Convertir les groupes de $4$ bits en leur valeur équivalente en hexadécimal (à l’aide d’une table de correspondance par exemple).
Concaténer les résultats de la conversion pour obtenir le chiffre hexadécimal équivalent.

Inversement :

Soit $N$ un nombre écrit en base 16.
Convertir chaque chiffre de $N$ en son équivalent binaire de 4 bits (en le complétant si nécessaire).
Concaténer les résultats (de droite à gauche) pour obtenir le chiffre binaire équivalent.

La justification mathématique de ce qui précède découle du fait que $16 = 2^4$ (des astuces similaires pour convertir une base $b$ en une base $b' = b^k$ pour un certain $k \geq 2$).

Par exemple, pour $N = (1010110101010110011110111)_2$, nous remarquons d’abord qu’il y a 25 chiffres et donc nous ajoutons trois zéros pour obtenir un numéral équivalent $N = (0001010110101010110011110111)_2$ avec $28$ chiffres qui (ce qui est divisible par $4$). Nous avons alors les 7 paquets suivants et leurs hexadécimales correspondantes (de droite à gauche) :

$(0111)_2 = (7)_{16}$,
$(1111)_2 = (F)_{16}$,
$(1100)_2 = (C)_{16}$,
$(1010)_2 = (A)_{16}$,
$(1010)_2 = (A)_{16}$,
$(0101)_2 = (5)_{16}$,
$(0001)_2 = (1)_{16}$.

On a donc $(1010110101010110011110111)_2 = (15AACF7)_{16}$.

Pour un exemple de l’opération inverse, supposons que l’on nous donne $(4D2)_{16}$ et que nous voulions le convertir en binaire :

$(2)_{16} = (0010)_2$.
$(D)_{16} = (1101)_2$.
$(4)_{16} = (0100)_2$.

On a donc $(4D2)_{16} = (010011010010)_2 = (10011010010)_2$, où dans la dernière égalité nous avons simplement supprimé le zéro initial.

Éléments de la structure multiplicative de $\mathbb{N}$#

Divisibilité, nombres premiers, décomposition en nombres premiers#

La structure multiplicative des entiers naturels $\mathbb{N}$ et des entiers $\mathbb{Z}$, c’est-à-dire la manière dont les nombres sont liés les uns aux autres par les opérations de multiplication et de division, revêt une importance particulière.

Définissons l’une des notions les plus fondamentales, celle de divisibilité.

Definition 18

Soit $a, b \in \mathbb{N}$. On dit que $a$ divise $b$ et on écrit $a \mid b$ si il existe un entier $k$ tel que $b = ka$.

Si $a \mid b$ on dit aussi que $a$ est un multiple de $b$. Si $a$ ne divise pas $b$, on écrit alors $a \not\mid b$. La définition ci-dessus a d’autres énoncés équivalents :

$a \mid b$ si le résultat de $a / b$ est un entier,
$a \mid b$ si le reste de la division euclidienne de $b$ par $a$ est zéro.

Il est clair que nous avons toujours $1 \mid n$ et $n \mid n$ pour tout $n \in \mathbb{N}$. Une classe de nombres particulièrement importante est celle pour laquelle les deux relations de division ci-dessus sont les seules possibles :

Definition 19

Un nombre $n \in \mathbb{N} \setminus \{1\}$ est prime s’il n’est divisible que par 1 et lui-même.

Pour déterminer si un nombre $n$ est premier, on peut bien sûr essayer de le diviser par tous les nombres dans $[2, n-1]$ : si aucun diviseur n’est trouvé, $n$ est premier.

Une optimisation simple de cette méthode découle de deux faits simples :

La multiplication est commutative : si $m \mid n$ on a $n = km = mk$.
Si $n = km$ avec $m > \sqrt{n}$ alors $k < \sqrt{n}$ et vice-versa.

Il suffit donc de tester la divisibilité de $n$ par n’importe quel nombre de l’intervalle $[2, \left\lfloor \sqrt{n} \right\rfloor]$.

Un résultat particulièrement important est le suivant :

Theorem 4 (Théorème fondamental de l’arithmétique)

Tout nombre $n \in \mathbb{N}$ supérieur à $1$ peut être écrit d’une manière unique comme un produit de nombres premiers, à permutation des facteurs près:

\[n = \prod_{i=1}^{k} p^{n_i}_i,\]

où $p_i$ sont des nombres premiers et $n_i \in \mathbb{N} \setminus \{0\}$.

Par exemple :

$99 = 3^3 \cdot 37$,
$1000 = 2^3 \cdot 5^3$.

Le plus grand diviseur commun et l’algorithme d’Euclide#

Pour deux nombres naturels $n,m dans \mathbb{N}$, leur plus grand nombre $k$ tel que $k \mid n$ et $k \mid m$ est appelé leur plus grand commun diviseur (PGCD) et nous écrivons $n \wedge m = d$[1].

Il est clair que cette opération est commutative, de sorte que $n \wedge m = m \wedge n$. Nous avons aussi que $0 \wedge n = n = n \wedge 0$ pour tout $n \in \mathbb{N}$. Si $n \wedge m = 1$, nous disons que $n$ et $m$ sont relativement premiers.

Dans le cas où $m$ divise $n$, on a :

Lemma 10

Soit $n, m \in \mathbb{N}$. Si $m \mid n$, alors tous les diviseurs de $m$ sont aussi des diviseurs de $n$ et :

\[ n \wedge m = m.\]

Un autre lemme utile est :

Lemma 11

Soit $n, m \in \mathbb{N} \setminus \{0\}$. Si $d = n \wedge m$, alors il existe $a, b \in \mathbb{N}$ qui sont relativement premiers ($a \wedge b = 1$) tels que:

\[ n = a \cdot d, m = b \cdot d.\]

Nous allons maintenant nous intéresser au problème du calcul du PGCD de deux nombres donnés $n, m \in \mathbb{N}$.

Voici une façon de le calculer :

Calculer les factorisations premières (qui existent nécessairement grâce au Theorem 4) :
- $n = \prod\limits_{i=1}^{k} p^{a_i}_i$,
- $m = \prod\limits_{i=1}^{k'} q^{b_i}_i$.
Prendre le produit des facteurs qui apparaissent dans les deux factorisations et les élever à la plus petite puissance dans laquelle ils apparaissent dans l’une ou l’autre factorisation.

Par exemple, pour calculer le PGCD de $48$ et $180$ :

$48 = 2^4 \cdot 3$ et $180 = 2^2 \cdot 3^2 \cdot 5^1$.
Les facteurs premiers communs sont $2$ et $3$, qui apparaissent avec des puissances respectives de $4,2$ et $1,2$.
Par conséquent, le PGCD de $48$ et $180$ est : $2^{\min(4,2)} \times 3^{\min(1,2)} = 12$.

Malheureusement, bien qu’efficace, cette approche n’est pas très performante : nous ne connaissons aucun algorithme en temps polynomial pour décomposer les entiers positifs en nombres premiers !

Un algorithme plus efficace pour calculer le PGCD $n \wedge m$ était connu des anciens mathématiciens ! En effet, il s’agit de l’un des plus anciens algorithmes connus encore couramment utilisés. Il a été décrit par le mathématicien grec Euclide dans son traité Στοιχεῖα (Éléments) vers 300 avant J.-C. Il était probablement connu des gens encore plus tôt et a été redécouvert indépendamment par des mathématiciens indiens et chinois plus tard.

L’idée de base de l’algorithme d’Euclide est la suivante :

Lemma 12

Soit $n, m \in \mathbb{N}$ et soit $n = qm + r$ le résultat de la division euclidienne de $n$ par $m$, où $0 \leq r < b$. Alors :

\[n \wedge m = m \wedge r.\]

L’astuce consiste alors à appliquer le lemme ci-dessus de manière itérative :

Algorithm 3 (Euclide)

Inputs: Deux nombres $n, m \in \mathbb{N}$ et nous supposons, sans perte de généralité, que $n \geq m$ (sinon nous pouvons les intervertir).

Sortie: Le PGCD $n \wedge m$.

Algorithme :

Si $m = 0$, on retourne $n$ (puisque $n \wedge 0 = n$).
Sinon, effectuer la division euclidienne : $n = qm + r$.
Mettre à jour $n \leftarrow m, m \leftarrow r$.
Répéter les étapes précédentes.

Pour justifier la validité de l’algorithme, notons que :

$r < m$ à chaque itération (par définition du du reste) et donc si $m \in \mathbb{N}$ l’algorithme est sûr d’atteindre $m = 0$ et de se terminer après un nombre fini d’étapes.
Lemma 12 garantit une chaîne d’égalités $n \wedge m = m \wedge r$ pour chaque itération.

A titre d’exemple, calculons $21 \wedge 15$ en utilisant Algorithm 3 :

$n = 21, m = 15$. En effectuant la division euclidienne de $21$ par $15$, on obtient $21 = 1 \cdot 15 + 6$. Par conséquent, nous mettons à jour : $n \leftarrow 15, m \leftarrow 6$.
$n = 15, m = 6$. En effectuant la division euclidienne de $15$ par $6$, on obtient $15 = 2 \cdot 6 + 3$. Par conséquent, nous mettons à jour : $n \leftarrow 6, m \leftarrow 3$.
$n = 6, m = 3$. En effectuant la division euclidienne de $15$ par $6$, on obtient $6 = 2 \cdot 3 + 0$. Par conséquent, nous mettons à jour $n \leftarrow 3, m \leftarrow 0$.
Puisque $m=0$, le résultat est

Ainsi, nous avons calculé $21 \wedge 15 = 3$.

Enfin, nous mentionnons en passant que le plus petit commun multiple (LCM) de $n, m \in \mathbb{Z}$, écrit comme $n \vee m$[2], est le plus petit entier $d \in \mathbb{N}$ qui divise à la fois $n, m$ : $d \mid n$ et $d \mid m$.

Le LCM peut être calculé à l’aide de $n \wedge m$ et $n \cdot m$ :

\[ n \vee m = \frac{n \cdot m}{n \wedge m}.\]

Théorème de Bézout et résolution des équations diophantiennes#

Une équation fondamentale de l’arithmétique est la suivante :

Theorem 5 (Bézout)

Soit $n, m \in \mathbb{N}$ avec $n \wedge m = d$. Il existe deux entiers $a,b \in \mathbb{Z}$ tels que :

\[an + bm = d.\]

Son importance réside dans ses nombreuses applications : il peut être utilisé pour démontrer de nombreux autres théorèmes importants de l’arithmétique, y compris le lemme d’Euclide et le théorème des restes chinois. Il est également, comme nous le verrons plus loin, très utile pour résoudre des équations linéaires sur les entiers naturels $\mathbb{N}$.

Avant de passer aux applications, voyons d’abord comment calculer ces deux entiers $a, b$ (appelés coefficients de Bézout). L’astuce réside dans l’algorithme d’Euclide : il fournit une suite d’équations (correspondant aux divisions aux divisions euclidiennes successives que nous effectuons) qui relient les nombres $n, m, d$.

Avant d’énoncer l’algorithme lui-même, passons d’abord par un exemple. un exemple. Rappelant notre exemple précédent d’utiliser l’algorithme d’Euclide pour calculer $25 \wedge 15$ nous avons les équations suivantes :

A la première étape, nous avions la division euclidienne de $n = 21$ par $m = 15$ :

(49)#\[21 = 1 \cdot 15 + 6.\]

A la deuxième étape, nous avions la division euclidienne de $15$ par le reste $6$ :

(50)#\[15 = 2 \cdot 6 + 3.\]

Enfin, nous avions que :

(51)#\[6 = 2 \cdot 3 + 0.\]

Nous en avons déduit que $d = 21 \wedge 15 = 3$. Remarquez que l’avant-dernière équation (50) peut facilement être réécrite comme une équation pour $d = 3$ :

(52)#\[3 = 15 - 2 \cdot 6.\]

Nous avons déjà obtenu une équation impliquant $d=3$ et $m=15$ ! De plus, l’équation (49) de la séquence ci-dessus relie $6$ à $n=21$ :

(53)#\[6 = 21 - 1 \cdot 15.\]

En combinant les équations (52) et (53) ci-dessus, nous avons :

\[\begin{align*} 3 &= 15 - 2 \cdot 6 \\ &= 15 - 2 \cdot (21 - 1 \cdot 15) \\ &= -2 \cdot 21 + 3 \cdot 15, \end{align*}\]

d’où il résulte que les coefficients recherchés sont $a = -2, b = 3$.

Ceci est l’essence de l’« algorithme d’Euclide étendu » : remonter la séquence d’équations produites au cours des divisions successives d’une exécution de l’algorithme d’Euclide.

Plus formellement, l’algorithme que nous avons décrit s’écrit de manière équivalente :

Algorithm 4 (Euclide étendu)

Entrée: Deux nombres $n, m \in \mathbb{N}$ et nous supposons, sans perte de généralité, que $n \geq m$ (sinon nous pouvons les intervertir).

Sortie: Le PGCD $d = n \wedge m$ et les coefficients de Bézout $a, b \in \mathbb{Z}$, de sorte que $d = an + bm$.

Algorithm :

Fixer :

\[\begin{align*} a_0 &\leftarrow 1 \\ b_0 &\leftarrow 0 \\ r_0 &\leftarrow n \\ a_1 &\leftarrow 1 \\ b_1 &\leftarrow 1 \\ r_1 &\leftarrow m \\ i &\leftarrow 1. \end{align*}\]

Tant que $r_i \neq 0$ do :
1. Effectuer la division euclidienne de $r_{i-1}$ par $r_i$ pour obtenir un quotient $q$ et un reste $r_{i+1}.$
2. $a_{i+1} \leftarrow a_{i-1} - q \times a_{i}$.
3. $b_{i+1} \leftarrow b_{i-1} - q \times b_{i}$.
4. $i \leftarrow i + 1$.
Retourner le PGCD $d = r_i$ ainsi que les coefficients correspondants $a = a_i, b = b_i$.

Enfin, le théorème suivant est une application importante de l’identité de Bézout aux équations sur $\mathbb{Z}$ (appelées équations diophantiennes d’après le mathématicien grec Diophante).

Theorem 6 (Solution des équations diophantiennes linéaires)

Une équation diophantienne linéaire à coefficients $a, b, c \in \mathbb{Z}$ et deux inconnues $x,y$ :

\[ax+by=c\]

a des solutions entières si et seulement si $c$ est un multiple de $a \wedge b$. De plus, si $(x_0, y_0)$ est une solution particulière, alors toutes les autres solutions de cette équation ont la forme:

\[(x+kv, y-ku),\]

où $k \in \mathbb{Z}$ est un entier arbitraire et :

$u$ est le quotient de la division euclidienne de $a$ par $a \wedge b$,
$v$ est le quotient de la division euclidienne de $b$ par $a \wedge b$.

A titre d’exemple, considérons $a = 98, b = 35, c = 14$ :

(54)#\[98x + 35y = 14.\]

Puisque $d = 98 \wedge 35 = 7$ divise $c=4$ nous sommes sûrs que l’équation peut être résolue. En divisant les deux côtés de (54) par $d=7$ on obtient :

(55)#\[14x + 5y = 2.\]

Nous pouvons diviser une fois de plus par $2$ pour obtenir une équation équivalente :

(56)#\[\frac{14x}{2} + \frac{5y}{2} = 1.\]

En définissant $x' = x/2$ et $y' = y/2$ on obtient finalement :

(57)#\[14x' + 5y' = 1.\]

On remarque que $14$ et $5$ sont relativement premiers puisqu’ils
proviennent de la division de $a = 98, b = 35$ par leur PGCD $d = 7$.

Par conséquent, les coefficients $x', y'$ dans (57) sont les coefficients de Bézout et nous pouvons les calculer en utilisant Algorithm 4 :

\[\begin{align*} x' &= -1 \\ y' &= 3. \end{align*}\]

Enfin, en utilisant $x = 2x', y' = 2y'$, nous trouvons une solution particulière de (55) : $x_0 = -2, y_0 = 6$.

Par conséquent, en utilisant Theorem 6 nous avons qu’une solution générale est :

\[\begin{align*} x &= -2 + 5k \\ y &= 6 - 14k. \end{align*}\]

Arithmétique modulaire#

Lorsque l’on parle de temps, dans le format habituel de 24 heures, on s’aperçoit que l’arithmétique fonctionne différemment que dans $\mathbb{N}$ :

Trois heures après minuit est $3h$, c’est-à-dire $24h + 3 = 3$ (ou, alternativement, $0h + 3h = 3h$).
Douze heures après $13h$ est $1h$, c’est-à-dire $13h + 12h = 1h$.
Quarante-huit heures après $17h$ est $17h$, c’est-à-dire $17h + 2 \cdot 24h = 17h$.

ce qui n’est pas le cas des résultats habituels dans $\mathbb{N}$ :

$24 + 3 = 27$,
$13 + 12 = 25$.

En fait, il semble que l’arithmétique de l’horloge de 24 heures soit comme si nous prenions la ligne des nombres infinis de $\mathbb{N}$ et qu’on l’enroulait autour d’elle-même, de sorte que :

Les multiples de $24$ se comportent comme des $0$ : $2 \cdot 24h \cong 0$.
Les nombres qui diffèrent par un multiple de $24$ se comportent de la même manière : $x + k \cdot 24h \cong x$.

Dans cette optique, définissons la notion de congruence modulo $n$ :

Definition 20 (Congruence modulo $n$)

On dit que deux nombres $a, b \in \mathbb{N}$ sont congruents (ou égaux) modulo $n$ si leur différence est un multiple de $n$ : $n \mid (a-b)$. Dans ce cas, on note $a \equiv b [n]$ et on note qu’il s’agit d’une relation d’équivalence :

Réflexivité : pour tout $a \in \mathbb{N}$, $a \equiv a[n]$.
Symétrie : pour tout $a,b \in \mathbb{N}$, si $a \equiv b[n]$ alors $b \equiv a[n]$.
Transitivité : pour tous les $a,b,c \in \mathbb{N}$, si $a \equiv b[n]$ et $b \equiv c[n]$ alors $a \equiv c[n]$.

Ces relations d’équivalence partitionnent l’ensemble $\mathbb{N}$ en classes d’équivalence, ensembles infinis de nombres égaux modulo $n$. Par exemple, pour $n=2$, nous avons deux classes de ce type :

$0 \equiv 2 \equiv 4 \equiv 6 \equiv 8 \equiv \dots [n]$,
$1 \equiv 3 \equiv 5 \equiv 7 \equiv 9 \equiv \dots [n]$.

Nous pouvons donc définir la classe d’équivalence d’un nombre $k \in \mathbb{N}$, noté $\overline{k}$, comme suit :

\[ \overline{k} = \{ p \lvert p \in \mathbb{N} \land p \equiv k[n]\}.\]

Plus généralement, il existe toujours exactement $n$ classes d’équivalence de $\mathbb{N}$ modulo $n$. Les éléments de l’ensemble $\overline{k}$ sont appelés représentants de la classe.

Une question naturelle se pose alors : comment se comportent les opérations arithmétiques familières sur $\mathbb{N}$ ? Une paire de propriétés particulièrement importante est la suivante :

$\overline{a} + \overline{b} = \overline{a+b}$,
$\overline{a} \times \overline{b} = \overline{a \times b}$.

En utilisant ces propriétés, nous pouvons interpréter nos manipulations de l’horloge de 24 heures comme comme un cas d’arithmétique modulo $24$ :

Trois heures après minuit est $3h$ : $24 + 3 = 27 \equiv 3[24]$.
Douze heures après $13h$ est $1h$ : $13 + 12 = 25 \equiv 1[24]$.
Quarante-huit heures après $17h$ est $17h$ : $17+48=65 \equiv 17[24]$.

Les deux propriétés que nous avons énumérées ci-dessus nous amènent à penser que arithmétique utilisant des classes d’équivalence modulo $n$ puisse être analogue à celle de $\mathbb{N}$. Dans cette optique, définissons l’ensemble suivant regroupant toutes les classes d’équivalence modulo $n$, que nous désignons par leur plus petit représentant :

$\mathbb{Z} / n \mathbb{Z} = \{\overline{0}, \overline{1}, \dots, \overline{n-1}\}$

Nous pouvons alors considérer les deux lignes ci-dessus comme définissant les opérations $+, \cdot$ dans $\mathbb{Z}/n\mathbb{Z}$. L’ensemble $\mathbb{Z}/n\mathbb{Z}$ muni de ces deux opérations se comporte de manière similaire à $\mathbb{Z}$ muni des opérations habituelles $+,\cdot$. (plus abstraitement, les mathématiciens disent que les deux sont des instances d’une structure algébrique générale appelée anneau).

Comme première application, nous avons le lemme suivant qui relie les solutions d’équations diophantiennes aux solutions de l’équation modulo $n$ :

Lemma 13

Considérons une équation diophantienne de la forme :

\[P(x,y,\dots) = c,\]

où $P$ est un polynôme à coefficients entiers et $c \in \mathbb{Z}$. Si $x = x_0, y = y_0, \dots$ est une solution sur $\mathbb{Z}$ alors nous avons que :

\[F(\overline{x_0}, \overline{y_0}, \dots) = \overline{c},\]

est valable dans $\mathbb{Z}/n\mathbb{Z}$ pour tout $n \in \mathbb{N}$.

La réciproque de ce lemme est que s’il existe $n \in \mathbb{N}$ tel que l’équation n’a pas de solution dans $\mathbb{Z}/n\mathbb{Z}$, alors elle n’a pas non plus de solution dans $\mathbb{Z}$.

Ceci peut être utilisé pour réfuter l’existence de solutions aux équations diophantiennes diophantiennes en choisissant judicieusement $n$ : puisque $\mathbb{Z}/n\mathbb{Z}$ est un ensemble fini, nous finis, nous pouvons simplement essayer toutes les possibilités pour voir s’il y a une solution.

Par exemple, considérons l’équation $x^2 + y^2 = 35$. Puisqu’elle est non linéaire, nous ne pouvons pas utiliser le critère de Theorem 6. Cependant, en la réduisant modulo $4$, on obtient :

\[\begin{align*} \overline{x^2+y^2} &= \overline{35} \\ \overline{x}^2 + \overline{y}^2 &= \overline{3} \end{align*}\]

En regardant les carrés dans $\mathbb{Z}/4\mathbb{Z}$ nous voyons que :

$\overline{0}^2 = 0$,
$\overline{1}^2 = 1$,
$\overline{2}^2 = 0$,
$\overline{3}^2 = 1$,

d’où l’on conclut qu’il n’existe pas de solution à l’équation modulo $4$ : il n’y a aucun moyen d’additionner deux des valeurs ci-dessus pour obtenir 3 !

Par conséquent Lemma 13 implique qu’il n’existe pas de solutions entières à l’équation $x^2 + y^2 = 35$ !

Explorons maintenant une autre propriété algébrique de $\mathbb{Z}$ et son analogue dans $\mathbb{Z}/n\mathbb{Z}$. Dans $\mathbb{Z}$, tous les éléments à l’exception de $0$ sont inversibles : pour chaque $i \in \mathbb{Z} \setminus \{0\}$ il existe un nombre unique $j \in \mathbb{Z}$ tel que $i \cdot j = 1$. Nous désignons habituellement $j$ par $i^{-1}$ et l’appelons l’inverse de $i$.

Qu’en est-il de $\mathbb{Z}/n\mathbb{Z}$ ? A-t-il des éléments inverses ? Nous pouvons essayer de trouver quelques exemples pour de petites valeurs de $n$ :

Dans $\mathbb{Z}/2\mathbb{Z}$ nous avons $\overline{1} \times \overline{1} = \overline{1}$, donc $1$ est son propre inverse.
Dans $\mathbb{Z}/7\mathbb{Z}$ nous avons $\overline{3} \times \overline{5} = \overline{1}$, so $\overline{3}^{-1} = \overline{5}$.

Si nous continuons à travailler sur de tels exemples à la main, nous arrivons rapidement au résultat important suivant :

Lemma 14

Soit $n \in \mathbb{N}$, $x \in \mathbb{Z}$. Alors $\overline{x}$ est est inversible dans $\mathbb{Z}/n\mathbb{Z}$ si et seulement si $x \wedge n = 1$.

La preuve est assez simple :

\[\begin{align*} \overline{x} \text{ invertible } &\Leftrightarrow \exists y \in \mathbb{Z}, \overline{xy} = \overline{1} \\ &\Leftrightarrow xy \equiv 1 [n] \\ &\Leftrightarrow \exists k \in \mathbb{Z}, xy = 1 + nk\\ &\Leftrightarrow xy-nk=1 \\ &\overset{Bézout}{\Leftrightarrow} x \wedge n = 1. \end{align*}\]

La preuve ci-dessus nous donne également un moyen de calculer les inverses. Rappelons que $x$ étant inversible, il existe $y, k \in\mathbb{Z}$ tels que :

\[xy - nk = 1.\]

Par conséquent, modulo $n$, on a $\overline{xy} = \overline{1} \Rightarrow \overline{x}\overline{y}=\overline{1}$.

Autrement dit, l’inverse $\overline{y} = \overline{x}^{-1}$ est exactement le premier coefficient de Bézout de l’équation ci-dessus.

Nous pouvons donc trouver $\overline{y}$ en utilisant l’algorithme d’Euclide étendu !

Par exemple, supposons que nous recherchions l’inverse de $\overline{x}=\overline{5}$ dans $\mathbb{Z}/17\mathbb{Z}$.

En appliquant l’algorithme d’Euclide, nous avons :

\[\begin{align*} 17 &= 3 \times 5 + 2 \\ 5 &= 2 \times 2 + 1 \\ 2 &= 2 \times 1 + 0. \end{align*}\]

En raisonnant à l’envers (à partir de l’avant-dernière équation), nous obtenons :

\[\begin{align*} 1 &= 5 - 2 \times 2 \\ &= 5 - 2 \times (17 - 3 \times 5) &= 7 \times 5 - 2 \times 17. \end{align*}\]

Par conséquent, $\overline{y} = \overline{7}$ et donc $\overline{5}^{-1} = \overline{7}$. En effet, $5 \times 7 = 35 \equiv 1[17]$.

Kid-RSA#

Dans cette section, nous allons appliquer nos connaissances des bases numériques et de l’arithmétique modulo $n$ pour étudier un système de chiffrement simple appelé KidRSA.

Kid-RSA est un exemple simple de cryptographie à clé publique qui fonctionne sur la base de deux clés. sur la base de deux clés :

Une clé publique : toute personne qui y a accès peut encrypter les messages.
Une clé privée : seules les personnes qui y ont accès peuvent décrypter les messages.

Supposons pour simplifier qu’un message soit un texte en clair écrit avec les 26 lettres de l’alphabet latin (sans espace !)[3].

En utilisant la correspondance $A \leftrightarrow 0, B \leftrightarrow 1, \dots, Z \leftrightarrow 25$, nous pouvons traduire n’importe quel message en un nombre en base 26. Enfin, en utilisant un algorithme de conversion de base nous pouvons réécrire le message en base 10 pour faciliter les calculs.

Nos clés publiques et privées seront une paire d’entiers $(e,d)$. Le chiffrement et le déchiffrement seront effectués en multipliant respectivement par $e$ et $d$, modulo un nombre $n$ à définir ci-dessous.

Pour mettre en place le système, une personne, que nous appellerons Alice, doit choisir deux entiers quelconques $a,b \in \mathbb{Z}$ et calculer $M = ab - 1$. Alice doit ensuite choisir deux autres entiers $a', b' \in \mathbb{Z}$ et les utiliser pour calculer les trois valeurs souhaitées $(e,d)$ et $n$ :

\[\begin{align*} e &= a'M + a, \\ d &= b'M + b, \\ n &= \frac{ed-1}{M} = a'b'M + ab' + a'b + 1. \end{align*}\]

Enfin, Alice peut annoncer publiquement la clé $e$.

Si quelqu’un, disons Bob, souhaite envoyer un message crypté à Alice, il procède comme suit :

Convertir son message en un entier en base-25 et appliquer un algorithme de conversion de base pour le réécrire en base-10. En d’autres termes, nous supposons que le message est un entier $m \in \mathbb{Z}$ (écrit en base-10).
Calculer le texte crypté $c$ comme $c \equiv em[n]$.
Communiquer $c$ à Alice.

Une fois qu’Alice a reçu le texte chiffré $c$ de Bob, il lui suffit de multiplier par $d$ modulo $n$ pour déchiffrer, il lui suffit de multiplier par $d$ modulo $n$ pour déchiffrer : $m \equiv dc[n] \equiv dem[n]$.

Pour que cela fonctionne, nous devons avoir $dc \equiv dem \equiv 1 \equiv m \equiv m[n]$ ce qui signifie que $e$ et $d$ sont inverses l’un de l’autre dans $\mathbb{Z}/n\mathbb{Z}$. Pour le prouver, on calcule :

\[\begin{align*} ed - 1 &= (a'M + a)(b'M + b) - 1 \\ &= a'b'M^2 + a'Mb + ab'M + ab - 1 \\ &= (a'b'M + a'b + a'b)M + M \\ &= (a'b'M + a'b + a'b + 1)M \\ &= nM, \end{align*}\]

où nous avons utilisé les définitions de $M = ab-1$ et $n = a'b'M + ab' + a'b + 1$. On en déduit que $(ed - 1)$ est divisible à la fois par $n$ et $M$ et donc que $(ed - 1) \equiv 0[n] \Rightarrow ed \equiv 1[n]$, comme souhaité.

Let us now work through an example:

Pour commencer, nous choisissons $a = 120, b = 39$, $a' = 5, b' = 215$. On obtient ainsi :

\[\begin{align*} M &= 4679, \\ n &= 5055921, \\ e &= 23515, \\ d &= 1006024. \end{align*}\]

Pour notre message, choisissons « HELLO ». En réécrivant ce message en base 10, nous obtenons $(HELLO)_{26} = (3276872)_{10}$.
Nous calculons le texte chiffré en utilisant la clé publique $e$ :

\[\begin{align*} c &\equiv em[n] \\ &\equiv 3409040 [n]. \end{align*}\]

Nous décryptons en utilisant la clé privée $d$ :

\[\begin{align*} m &\equiv dc[n] \\ &\equiv 1006024 \times 3276872 [n] \\ &\equiv 3276872[n]. \end{align*}\]

Nous réécrivons cela en base-26 : $(3276872)_{10} = (HELLO)_{26}$.

Ce système de cryptographie n’est pas particulièrement sûr. vulnérabilités potentielles ? Si vous avez lu et compris tout ce qui a été présenté dans les sections précédentes, vous avez les outils pour casser ce système simple !

Exercices#

Note : les exercices de programmation peuvent être réalisés dans le langage de programmation de votre choix.

Exercice#

Implémenter un algorithme de conversion de base.

Exercice#

Pour les amateurs de solfège, considérons un morceau composé de deux voix jouant chacune une seule mesure en polymètre. C’est-à-dire,

Chaque voix suit sa propre métrique (par exemple une voix en $4/4$ et une en $3/4$).
Chaque voix répète une seule mesure.
Le tactus (pulsation) est fixe et commun aux deux voix.

Bien que les deux voix commencent en même temps, elles se désynchronisent rapidement : chacune commence et termine sa mesure à des temps différents. Cependant, au bout de temps, les deux voix recommenceront leurs mesures en même temps.

Compte tenu des mesures des deux voix, calculez le nombre de temps . Combien de mesures chacune des voix aura-t-elle exécutées avant de recommencer sur le même temps ?

Exercice#

Implémenter un algorithme de factorisation des nombres premiers (l’algorithme naïf, par exemple).

Exercice#

Implémenter l’algorithme d’Euclide. Envisagez différentes approches : une approche récursive et une approche itérative, par exemple.

Exercice#

Implémenter l’algorithme d’Euclide étendu.

Exercice#

Déterminer si les équations diophantiennes suivantes ont des solutions et si oui, les calculer :

$5x + 10y = 10$,
$5x + 10y = 11$,
$12x + 4y = 30$,
$12x + 4y = 32$.

Exercice#

Démontrer les propriétés de of $+, \times$ modulo $n$.

Exercice#

Montrer que les équations $x^2+y^2 = 2024$ et $x^2+y^2+z^2=87$ et n’admettent pas de solutions entières.

Exercice#

Liste de tous les éléments inversibles dans $\mathbb{Z}/2\mathbb{Z}, \mathbb{Z}/5\mathbb{Z}, \mathbb{Z}/7\mathbb{Z}, \mathbb{Z}/24\mathbb{Z}$.

Arithmétique et applications

Contents

Arithmétique et applications#

Systèmes numériques#

Nombres et notation positionnelle#

Conversion des bases#

Éléments de la structure multiplicative de \(\mathbb{N}\)#

Divisibilité, nombres premiers, décomposition en nombres premiers#

Le plus grand diviseur commun et l’algorithme d’Euclide#

Théorème de Bézout et résolution des équations diophantiennes#

Arithmétique modulaire#

Kid-RSA#

Exercices#

Exercice#

Exercice#

Exercice#

Exercice#

Exercice#

Exercice#

Exercice#

Exercice#

Exercice#

\(0\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)	\(9\)	\(10\)
	I	II	III	IV	V	VI	VII	VIII	IX	X
੦	੧	੨	੩	੪	੫	੬	੭	੮	੯	੧੦
	Α	Β	Γ	Δ	Ε	Ϝ	Ζ	Η	Θ	Ι