Arithmétique

Soit $a$ et $b$ deux entiers relatifs non nuls. Si $d = a \wedge b$ et $m = a \vee b$ alors :

• $d \ge 1$ et $d \mid a$ et $d \mid b$
• $m \ge 1$ et $a \mid m$ et $b \mid m$
• Pour tout $c \in \mathbb{N}^*$ : $\left[(c \mid a \text{ et } c \mid b) \Rightarrow c \mid d\right]$ et $\left[(a \mid c \text{ et } b \mid c) \Rightarrow m \mid c\right]$
• Pour tout $c \in \mathbb{N}^*$ : $\left[(c \mid a \text{ et } c \mid b) \Rightarrow c \le d\right]$ et $\left[(a \mid c \text{ et } b \mid c) \Rightarrow m \le c\right]$
• $|a| \wedge |b| = d$ et $a \wedge 1 = 1$ et $a \wedge a = a \wedge 0 = |a|$.
• $|a| \vee |b| = m$ et $a \vee 1 = |a|$ et $a \vee a = |a|$.

Pour tout $(x; y) \in \left(\mathbb{N}^*\right)^2$ :

Explication de l'algorithme d'Euclide : On considère deux entiers $a \in \mathbb{Z}^*$ et $b \in \mathbb{N}^*$.

• On fait la division euclidienne de $a$ par $b$ : $a = bq_1 + r_1$ avec $0 \le r_1 < b$.
  • Si $r_1 = 0$, on arrête l'algorithme en déduisant que : $a \wedge b = b$
  • Si $r_1 \ne 0$, on continue.
• On fait la division euclidienne de $b$ par $r_1$ : $b = r_1 q_2 + r_2$ avec $0 \le r_2 < r_1$.
  • Si $r_2 = 0$, on arrête l'algorithme en déduisant que : $a \wedge b = r_1$
  • Si $r_2 \ne 0$, on continue.
• Etc.

Notons que le processus engagé va s'arrêter, car sinon, on construirait une suite d'entiers naturels strictement décroissante, ce qui est impossible. Il existe donc un entier $p \in \mathbb{N}$ tel que $r_p \ne 0$ et $r_{p+1} = 0$. Par conséquent : $a \wedge b = r_p$

L'inconvénient du théorème du Bezout, sous sa forme théorique, est qu'il ne fournit pas les coefficients $u$ et $v$ intervenant dans la relation $au+bv = 1$. L'algorithme d'Euclide fournit une réponse pratique à ce problème. À titre d'exemple, posons : $a = 1452$ et $b = 161$. Utilisons la méthode de l'algorithme d'Euclide pour déterminer $a \wedge b$ : On déduit donc que $1452 \wedge 161 = 1$, donc, les entiers $a$ et $b$ sont premiers entre eux. Nous allons déduire des quatre lignes ci-dessus un couple $(u;v) \in \mathbb{Z}^2$ tel que $1452u + 161v = 1$. Il suffit pour cela de remonter l'algorithme d'Euclide : Finalement : $1452 \times 54 + 161 \times (-487) = 1 (u = 54 \text{ et } v = -487)$

Dans le théorème de Gauss, la condition $a \wedge b = 1$ est nécessaire. Par exemple : $12 \mid 9 \times 8$ mais 12 ne divise ni le nombre 9 ni le nombre 8.

Dans le théorème 5, la condition $a \wedge b = 1$ est nécessaire. Par exemple : $8 \mid 48$ et $12 \mid 48$ mais $12 \times 8$ ne divise pas 48.

Une équation diophantienne est une équation polynomiale à une ou plusieurs inconnues dont les solutions sont cherchées parmi les nombres entiers, éventuellement rationnels, les coefficients étant eux-mêmes également entiers. Certaines équations diophantiennes ont demandé pour leur résolution les efforts conjugués de nombreux mathématiciens sur plusieurs siècles. Le dernier théorème de Fermat est un exemple typique ; il est conjecturé par Pierre de Fermat et démontré en 1994 par Andrew Wiles, après 357 ans d'efforts de la part de nombreux mathématiciens. L'intérêt de la résolution de questions de cette nature réside rarement dans l'établissement d'un théorème clé pour les mathématiques, la physique ou les applications industrielles, même s'il existe des contre exemples comme la cryptologie, qui fait grand usage du petit théorème de Fermat. Leur analyse amène le développement d'outils mathématiques puissants dont l'usage dépasse le cadre de l'arithmétique. La richesse et la beauté formelle des techniques issues de la résolution d'équations diophantiennes fait de l'arithmétique la branche $\ll \text{reine des mathématiques} \gg$ pour David Hilbert. L'équation $ax + by = c$, où les coefficients $a$, $b$ et $c$ sont trois entiers relatifs ($a$ et $b$ non tous deux nuls) et où les inconnues $x$ et $y$ sont entiers relatifs, est une des équations diophantiennes les plus simples à résoudre. Sa résolution s'appuie sur l'algorithme d'Euclide, le théorème de Bezout (qui correspond au cas, appelé aussi identité de Bezout, où $c$ est égal à $a \wedge b$) et le théorème de Gauss. Dans l'ensemble des entiers relatifs, une telle équation possède, ou bien aucune solution, ou bien une infinité de solutions. Lorsque les coefficients et les inconnues sont des entiers naturels, l'équation possède un nombre fini de solutions.

\textbf{Technique de résolution de l'équation $(E')$ dans $\mathbb{Z}^2$ :} Soit $(x_0; y_0)$ une solution (particulière) de l'équation $(E')$. On a donc $a'x_0 + b'y_0 = c'$ et l'équation $(E')$ se lit alors : $a'x + b'y = a'x_0 + b'y_0$, c'est-à-dire : $ a'(x – x_0) = b'(y_0 – y) (*)$ La relation $(*)$ entraîne $b' \mid a'(x – x_0)$, et comme $a' \wedge b' = 1$, le théorème de Gauss nous donne $b' \mid x – x_0$. Soit $k \in \mathbb{Z}$ tel que $x – x_0 = b'k$. La relation $(*)$ donne alors $y – y_0 = -a'k$. Les solutions de $(E')$ dans $\mathbb{Z}^2$ ne peuvent être que $(x_0 + b'k; y_0 – a'k)$. Pour conclure, il suffit de vérifier que tous ces couples sont solutions de $(E')$. D'où le théorème suivant :

On montre sans difficulté que les notions de PGCD et PPCM sont associatives, au sens où : Ainsi, le calcul d'un PGCD ou d'un PPCM de $n$ entiers peut se ramener au PGCD ou au PPCM de $n-1$ entiers par les égalités suivantes : Cela permet de généraliser au cas de $n$ entiers les définitions et résultats qui viennent d'être exposés concernant le PGCD et le PPCM de deux entiers.

La proposition suivante montre que la relation de congruence est compatible avec les opérations usuelles dans $\mathbb{Z}$.

On a : $7 \equiv 1 \ [3]$ et $5 \equiv -1 \ [3]$ et $7^2 \equiv 1 \ [3]$ et $5^2 \equiv 1 \ [3]$.
Par conséquent : $2 \times 7^{2018} + 3 \times 5^{2018} – 5 \equiv 2 + 3 – 5 \ [3]$, c'est-à-dire : $a \equiv 0 \ [3]$.
Enfin, puisque $8 \mid a$ et $3 \mid a$ et $3 \wedge 8 = 1$ alors $24 \mid a$, d'où le résultat.

Les résultats cités dans la proposition suivante sont des conséquences importantes du théorème 10, très utiles en pratique.

Un entier relatif $n$ non nul a au plus $2n$ diviseurs (si $k \mid n$, alors $|k| \le |n|$ et $k \ne 0$).
Si $|n| \ge 2$, il y a au moins quatre diviseurs distincts : $1$ ; $-1$ ; $n$ ; $-n$.
$1$ et $-1$ ont exactement deux diviseurs.

Voici deux questions qui se posent naturellement :

• Comment savoir si un entier $N \ge 2$ est premier ?
  La proposition ci-dessus donne une réponse : On dresse la liste des nombres premiers $p$ tels que $p^2 \le N$, c'est-à-dire $p \le E(\sqrt{N})$ ($x \mapsto E(x)$ est la fonction partie entière). Alors $N$ est premier si, et seulement s'il n'est multiple d'aucun des nombres obtenus.
  À titre d'exemple : Montrons que le nombre 2017 est premier.
  D'abord $E(\sqrt{2017}) = 44$. Les nombres premiers inférieurs ou égaux à 44 sont : \[ 2 – 3 – 5 – 7 – 11 – 13 – 17 – 19 – 23 – 29 – 31 – 37 – 41 – 43 \] Par division euclidienne ou critère de divisibilité, on vérifie qu'aucun de ces nombres ne divise 2017.
• Soit $N \ge 2$ un entier donné, comment trouver tous les nombres premiers inférieurs ou égaux à $N$ ?
  Le crible d'Ératosthène fournit une méthode. Dans la liste des entiers de 2 à $N$, on supprime tous les multiples de 2, puis tous les multiples de 3, et ainsi de suite. Après avoir supprimé tous les multiples d'un certain entier, le plus petit des entiers qui restent dans la liste, s'il y en a, est premier, et tous les nombres premiers entre 2 et $N$ sont obtenus successivement par ce procédé.

Les nombres premiers inférieurs ou égaux à 120 sont au nombre de 30 : \[ \begin{array}{cccccccccc} \mathbf{2} & \mathbf{3} & \mathbf{5} & \mathbf{7} & \mathbf{11} & \mathbf{13} & \mathbf{17} & \mathbf{19} & \mathbf{23} & \mathbf{29}
\mathbf{31} & \mathbf{37} & \mathbf{41} & \mathbf{43} & \mathbf{47} & \mathbf{53} & \mathbf{59} & \mathbf{61} & \mathbf{67} & \mathbf{71}
\mathbf{73} & \mathbf{79} & \mathbf{83} & \mathbf{89} & \mathbf{97} & \mathbf{101} & \mathbf{103} & \mathbf{107} & \mathbf{109} & \mathbf{113} \end{array} \]

INTRODUCTION
Soit $x$ et $y$ deux éléments de $\mathbb{Z}$, et $n \in \mathbb{N}^*$.
Soit $r$ le reste de la division euclidienne de $x$ par $n$, et $r'$ le reste de la division euclidienne de $y$ par $n$.

• On a : $\begin{cases} x \in \overline{r} \iff x \equiv r \ [n]
  y \in \overline{r'} \iff y \equiv r' \ [n] \end{cases}$, donc : $x + y \equiv r + r' \ [n]$, c'est-à-dire : $\overline{x + y} = \overline{r + r'}$.
  On a $x + y \in \overline{r + r'}$ et on écrit alors : $\overline{r + r'} = \overline{r} + \overline{r'}$.
• On a : $\begin{cases} x \in \overline{r} \iff x \equiv r \ [n]
  y \in \overline{r'} \iff y \equiv r' \ [n] \end{cases}$, donc : $xy \equiv rr' \ [n]$, c'est-à-dire : $\overline{xy} = \overline{rr'}$.
  On a $xy \in \overline{rr'}$ et on écrit alors : $\overline{rr'} = \overline{r} \times \overline{r'}$.

Par suite, on peut donner la définition suivante :

\subsection*{3.3. APPLICATIONS À LA CRYPTOGRAPHIE} Voici une application du théorème de Fermat. Il s'agit d'une méthode de codage très utilisée en cryptographie, la méthode RSA (due à Rivest, Shamir et Adleman). Soient $p$ et $q$ deux nombres premiers distincts, $N = pq$ et $c \in \N^*$ fixé premier avec $(p-1)(q-1)$. L'expéditeur du message ne connaît que $N$ et $c$ : la «~Clé publique~», mais ni $p$ ni $q$. Le message à transmettre est initialement constitué de «~lettres~»~ou, plus généralement, de «~caractères~». On le transforme en une liste de «~chiffres~»~en remplaçant, dans le premier cas, chaque lettre par son rang dans l'alphabet et, dans le second, chaque caractère par le nombre qui le représente dans un certain encodage, par exemple en utilisant le codage ASCII (American Standard Code for Information Interchange ; version étendue 8 bits) par un entier entre $0$ et $255 = 2^8 – 1$.

On découpe ensuite le message ainsi transformé en «~tranches~»~de même longueur représentant chacune un nombre entier $x < N$, puis l'on remplace chaque tranche par le $\overline{x} \in \Z/N\Z$ correspondant. On code chaque $\overline{x}$ en le remplaçant par $\overline{y} = \overline{x}^c$ et l'on transmet la liste des $y \in \{0 ; 1 ; \dots ; N-1\}$ correspondants. Comment le destinataire du message peut-il \underline{décoder}, c'est-à-dire retrouver $\overline{x}$ à partir de $\overline{y}$ en connaissant $p$ et $q$ ? Voici la réponse. D'après le théorème de Bezout, il existe deux entiers $d$ et $k$ tels que : vérifier que $x^{cd} \equiv x \pmod{pq}$, ou encore que $pq$ divise $x^{cd} – x$. Comme $pq = p \vee q$, il suffit de voir que $x^{cd} – x$ est multiple de $p$ et $q$. Par symétrie, il suffit de montrer que $x^{cd} – x \equiv 0 \pmod p$. C'est clair si $p \mid x$, auquel cas $p \mid x^{cd}$. Si $p$ ne divise pas $x$, le théorème de Fermat donne $x^{p-1} \equiv 1 \pmod p$. Puisque : En pratique, on choisit pour $p$ et $q$ deux «~grands~»~nombres premiers distincts (de quelques centaines de chiffres chacun). Quel est l'intérêt ? Le point capital est que, depuis un peu plus d'une vingtaine d'années, grâce à des méthodes que nous ne pouvons pas détailler ici, on sait fabriquer à la demande des nombres premiers $p$ et $q$ de la taille requise. En revanche, il se trouve que, dans l'état actuel, on ne peut pas factoriser un entier de taille de $N = pq$. Les entiers $N$ et $c$ constituent la «~clé publique~», ils peuvent sans inconvénient être connus de tous, et permettant de coder les messages. Pour décoder il faut avoir $d$, ce qui revient, comme nous l'avons vu, à connaître le nombre suivant être trouvé, même si $N$ et $c$ sont connus, ainsi le message initial $\overline{x}$ et le message codé $\overline{y}$. C'est l'avantage essentiel de cette méthode de codage, dite à clé publique. Voici un exemple numérique : $N := 415439 = pq$, où $p := 233$ et $q := 1783$. Alors : Choisissons $c := 113$ et $q := 336593$. Il est facile de vérifier que $cd \equiv 1 \pmod{(p-1)(q-1)}$. Le mot «~eau~»~est codé par $\overline{x} := 50121$ (les numéros des lettres $e$, $a$ et $u$ sont $5, 1$ et $21$ respectivement). On vérifie que $\overline{x}^c = \overline{220914}$. \section*{4 – SYSTÈMES DE NUMÉRATION} \subsection*{4.1. REPRÉSENTATION D'UN ENTIER NATUREL DANS UN SYSTÈME DE NUMÉRATION}

La numération est la science qui traite de la dénomination et de la représentation graphique des nombres. Le problème posé est de représenter tous les entiers naturels et les décimaux à l'aide d'un ensemble fini de symboles (appelés des chiffres) rassemblés selon des règles (le code) pour former un nombre. Il est important de connaître les différents systèmes car ils sont utilisés en informatique et plus généralement dans le traitement de l'information. Selon le contexte il peut être plus judicieux d'utiliser un code plutôt qu'un autre, il faut donc savoir comment passer de l'un à l'autre.

Mais de nombreux logiciels, parfois même certains systèmes d'exploitation, utilisent toujours la notation antérieure à 1998 pour laquelle $1\,\text{Ko} = 1024\,\text{octets } (2^{10}\text{ bits})$.

Méthode de représentation d'un entier naturel non nul $n$ dans un système de numération de base $b$ : En utilisant la division euclidienne par $b$, on obtient ce qui suit : n = \overline{a_m a_{m-1} \dots a_1 a_0}_{(b)}$$

\subsection*{4.2. COMPARAISON DE DEUX NOMBRES PRÉSENTÉS DANS LE MÊME SYSTÈME DE NUMÉRATION}

\subsection*{4.3. ADDITION ET MULTIPLICATION DE DEUX NOMBRES PRÉSENTÉS DANS LE MÊME SYSTÈME DE NUMÉRATION}

• On considère les deux nombres suivants : $x = \overline{5312}_{(6)}$ et $y = \overline{214}_{(6)}$ On veut représenter le nombre $x + y$ en base $6$. On a : $x = 5 \times 6^3 + 3 \times 6^2 + 6 + 2 \text{et} y = 2 \times 6^2 + 6 + 4$ Par conséquent : $x + y = 5 \times 6^3 + 5 \times 6^2 + 3 \times 6 = x = \overline{5530}_{(6)}$. On peut représenter le nombre $x + y$ directement en base $6$ en utilisant la méthode vue au primaire «~l'addition par retenue~»~comme suit :
  \[\begin{array}{r@{}l} & \stackrel{1}{\overline{5312}}_{(6)} \\ + & \phantom{\overline{53}}\overline{214}_{(6)} \\ \hline = & \overline{5530}_{(6)} \end{array}\]
• On considère les deux nombres suivants : $a = \overline{432}_{(5)}$ et $b = \overline{134}_{(5)}$ On veut représenter le nombre $a \times b$ en base $5$. On a : $a = 4 \times 5^2 + 3 \times 5 + 2 \text{et} b = 5^2 + 3 \times 5 + 4$ Par conséquent :
  \[\begin{aligned} a \times b &= (4 \times 5^2 + 3 \times 5 + 2)(5^2 + 3 \times 5 + 4) \\ &= 4 \times 5^4 + 3 \times 5^4 + 5^4 + 2 \times 5^2 + 3 \times 5^2 + 3 \times 5 + 5 + 3 \\ &= 5^5 + 3 \times 5^4 + 5^3 + 4 \times 5 + 3 \\ &= \overline{131043}_{(5)} \end{aligned}\]
  Tout comme l'addition, on peut représenter le nombre $a \times b$ directement dans en base $5$ en utilisant la méthode de «~la multiplication par retenue~»~comme suit :
  \[\begin{array}{r@{}l} & \stackrel{1}{\overline{432}}_{(5)} \\ \times & \phantom{\overline{4}}\overline{134}_{(5)} \\ \hline & \phantom{\overline{43}}\overline{3333} \\ + & \phantom{\overline{4}}\overline{2401\bullet} \\ + & \overline{432\bullet\bullet} \\ \hline = & \overline{131043}_{(5)} \end{array}\]

\subsection*{4.4. CRITÈRES DE DIVISIBILITÉ SUR LES NOMBRES $3 ; 4 ; 5 ; 9 ; 11 ; 25$ DANS LE SYSTÈME DÉCIMAL}