Arithmétiques et problèmes de codage (suite)

Introduction :

Ce cours fait suite à celui sur l’arithmétique et les problèmes de codage. Dans un premier temps, nous évoquerons la notion de $\text {PGCD}$ avec les définitions et propriétés. Nous verrons ensuite ce que sont des nombres dits premiers entre eux, comment savoir s’ils sont premiers entre eux avec l’algorithme d’Euclide et enfin les théorèmes de Bézout et de Gauss. Nous pourrons alors revenir sur la notion de nombres premiers avec une application concrète : le RSA.

PGCD et Euclide

PGCD

Tout d’abord, il faut noter que par convention dans ce cours, lorsqu’on parlera de diviseurs d’un entier naturel, il s’agira toujours de diviseurs positifs.
Commençons par voir les diviseurs communs à deux nombres. Pour cela, quelques notations sont à connaître…
Pour tout entier naturel $a$, on note $\text D(a)$ l’ensemble des diviseurs de $a$.

bannière exemple

Exemple

  • L’ensemble des diviseurs de $1$ est $1$ : $\text D(1)=\lbrace1\rbrace$
  • L’ensemble des diviseurs de zéro est l’ensemble des entiers naturels : $\text D(0)=\mathbb N$
bannière propriete

Propriété

Comme $1$ peut diviser tous les entiers, l’ensemble des diviseurs de $a$ $\text D(a)$ contient toujours au moins $1$ et $a$ lui-même. Par ailleurs, le plus grand élément des diviseurs de $a$ est $a$ (quand $a\neq 0$).
Pour tous entiers naturels $a$ et $b$ non nuls, on note $\text D(a\ ;b)$ l’ensemble des diviseurs communs à $a$ et à $b$.

bannière à retenir

À retenir

Quelques remarques s’imposent :

  • $\text D(a\ ;b)$ est non vide puisqu’il contient toujours au moins $1$
  • tous les nombres que contient $\text D(a\ ;b)$ sont inférieurs ou égaux à $a$ et à $ b$
  • comme toute partie non vide et majorée de $\mathbb N$ admet un plus grand élément, $\text D(a\ ;b)$ a un plus grand élément qu’on appelle $\text{PGCD} (a\ ; b)$.
bannière definition

Définition

PGCD :

  • ​$a$ et $b$ sont deux entiers naturels non nuls. Le plus grand commun diviseur de $a$ et $b$ est noté $\text{PGCD} (a\ ;b) $
  • $a$ et $b$ sont deux entiers relatifs non nuls en prenant leurs valeurs absolues : $\text{PGCD}(\mid a \mid ;\mid b \mid)$
  • Par conséquent, si $a$ divise $b$, alors le $\text {PGCD}$ de $a$ et $b$ est égal à la valeur absolue de $a$ $\text{PGCD} (a\ ;b)=|a|$.

Voici quelques propriétés qui vont compléter cette notion de $\text {PGCD}$.

bannière propriete

Propriété

Sachant que $a$ et $b$ sont deux entiers naturels supérieurs ou égaux à 2 :

  • si, dans leur décomposition en produit de facteurs premiers, $a$ et $b$ n’ont pas de facteur premier commun leur $\text {PGCD}$ est $1$, $\text {PGCD}$ $(a\ ;b)=1$
  • sinon, le $\text {PGCD}$ de $a$ et de $b$ est égal au produit des facteurs premiers communs à $a$ et à $b$, chacun d’eux étant affecté du plus petit exposant figurant dans la décomposition de $a$ et de $b$.
bannière exemple

Exemple

Pour déterminer le $\text {PGCD}$ de $2070$ et $368$, on décompose ces nombres en produits de facteurs premiers :

$\begin{aligned}2070&=2\times3^2\times5\times23\\368&=2^4\times23\end{aligned}$

Donc le $\text {PGCD}$ de $2070$ et $368$ est égal au produit de leurs facteurs premiers commun, $2$ et $23$, soit $46$. $\text{PGCD} (2070\ ; 368)=2\times23=46$

bannière propriete

Propriété

Si le $\text{PGCD}(a ; b)$ est un entier strictement positif :

$\text{PGCD} (a\ ;-a)=|a|$ ; $\text{PGCD} (a\ ;1)=1$ ; $\text {PGCD} (a\ ;0)=|a|$ ;$\begin{aligned}\text{PGCD} (a\ ;b)&=\text{PGCD} (b\ ;a)\\&=\text{PGCD} (|a|\ ;|b|)\end{aligned}$.

Les diviseurs communs à $a$ et $b$ sont les diviseurs de leur $\text{PGCD}$. Pour tous les entiers relatifs $a$ et $b$ tous deux non nuls, et tout $c$ de l’ensemble des entiers naturels strictement positifs $\mathbb N^*$, $$ \text{PGCD} (ac\ ;bc)=c\times\text{PGCD} (a\ ;b)$$

Algorithme d’Euclide

bannière theoreme

Théorème

$a$ et $b$ sont deux entiers naturels non nuls tels que la division euclidienne de $a$ par $b$ se traduit par $a=bq+r$ avec $r$ compris entre $0$ et $b$ tous deux exclus $0 < r < b$.

Alors l’ensemble des diviseurs commun à $a$ et $b$ est identique à ceux communs à $b$ et $r$ $\text D(a\ ;b)=\text D(b\ ;r)$ ce qui amène à $\text{PGCD }(a\ ;b)=\text{PGCD }(b\ ;r)$.

bannière demonstration

Démonstration

  • Démontrons que si $d$ divise $a$ et $b$, alors $d$ divise $b$ et $r$ : Si $d$ divise $a$ et $b$, $d$ divise toute combinaison linéaire de $a$ et $b$, donc en particulier $a-bq$, soit $r$. Il en résulte que l’ensemble des diviseurs de $a$ et $b$ sont inclus dans les diviseurs de $b$ et $r$ : $$\text D(a\ ;b)⊂\text D(b\ ;r)$$
  • Démontrons que si $δ$ divise $b$ et $r$, alors $δ$ divise $a$ et $b$​. Si $δ$ divise $b$ et $r$, $δ$ divise toute combinaison linéaire de $b$ et $r$, donc en particulier $bq+r$, soit $a$. Il en résulte que l’ensemble des diviseurs de $b$ et $r$ figurent parmi les diviseurs de $a$ et $b$ : $$\text D(b\ ;r)⊂\text D(a\ ;b)$$

La double inclusion équivaut donc à dire que l’ensemble des diviseurs à $a$ et $b$ sont communs à ceux de $b$ et $r$ $\text D(a\ ;b)=\text D(b\ ;r)$. Ces deux ensembles étant identiques, ils ont le même plus grand élément donc : $$\text{PGCD }(a\ ;b)=\text{PGCD}(b\ ;r)$$

bannière à retenir

À retenir

Lorsque $b$ ne divise pas $a$, le $\text{PGCD}$ de $a$ et $b$ est le dernier reste non nul dans la succession des divisions de l’algorithme d’Euclide.

bannière exemple

Exemple

Reprenons le calcul du PGCD de $2070$ et $368$. On écrit les divisions euclidiennes successives :

$\begin{aligned}2070&=5\times368+230\\368&=1\times230+138\\230&=1\times138+92\\138&=1\times92+46\\92&=2\times46+0\end{aligned}$

Donc $\text{PGCD } (2070\ ; 368) = 46$.

Entiers premiers entre eux

bannière definition

Définition

Entiers premiers entre eux :

Dire que deux entiers naturels non nuls $a$ et $b$ sont premiers entre eux signifie que leur $\text{PGCD}$ est égal à $1$.

bannière attention

Attention

Ne pas confondre « nombres premiers entre eux » et « nombres premiers ».

bannière definition

Définition

Caractérisation du $\text {PGCD}$ :

$a$ et $b$ sont deux entiers naturels non nuls. « $d$ est le $\text {PGCD}$ de $a$ et $b$ » équivaut à « il existe deux entiers naturels $a'$ et $b'$ tels que :

$a = da'$ ; $b = db'$ ; $\text {PGCD} (a'\ ; b') = 1$

bannière demonstration

Démonstration

Supposons que $\text {PGCD }(a'\ ; b') = d' ≠1$, alors $a'= d'a''$ et $b' = d'b''$ où $a''$ et $b''$ sont des entiers.

Par conséquent, $a = dd'a''$ et $b = dd'b''$ ; ainsi $dd'$ (qui est strictement supérieur à $d$) est un diviseur de $a$ et de $b$, ce qui contredit $\text {PGCD }(a\ ; b) = d$.

Donc $\text{PGCD }(a'\ ; b') = 1$.

Bézout et Gauss

Théorème de Bézout

bannière theoreme

Théorème

Théorème de Bézout :
$a$ et $b$ sont deux entiers naturels non nuls. Dire « $a$ et $b$ sont premiers entre eux » équivaut à dire « il existe deux entiers relatifs $u$ et $v$ tels que $au+bv = 1$ ».

bannière demonstration

Démonstration

Supposons qu’il existe deux entiers $u$ et $v$ tels que $au+bv=1$ et prouvons que $a$ et $b$ sont premiers entre eux.

On note $d=\text{PGCD }(a\ ;b)$. $d$ divise $a$ et $b$ donc $d$ divise $au+bv$.

Comme $au+bv=1$, $d=1$ et $a$ et $b$ sont premiers entre eux.

Supposons $a$ et $b$ premiers entre eux et démontrons que $1$ s’écrit sous la forme $au+bv$. Soit $\varepsilon$ l’ensemble des nombres de la forme $au+bv$, avec $u ∈\mathbb Z$ et $v ∈\mathbb Z$.

L’ensemble  $\varepsilon$ n’est pas vide car pour $u = 1$ et $v = 0$, ∈ $\varepsilon$. Il en est de même pour $b$.

Ainsi $\varepsilon$ contient des entiers strictement positifs et, parmi eux, un plus petit que tous les autres.

Notons $m = au_1+bv_1$ ce plus petit élément. La division euclidienne de $a$ par $m$ s’écrit $a=mq+r$ avec $0 ≤ r < m$

soit $\begin{aligned}r&=a-mq\\&=a-(au_1+bv_1)q\\&=a(1-u_1q)+b(-v_1q)\end{aligned}$

Ainsi r ∈ $\varepsilon$.

Or $m$ est le plus petit entier strictement positif de $\varepsilon$ donc $r=0$. Ainsi $m$ divise $a$. On montre de même que $m$ divise $b$.

Comme $a$ et $b$ sont premiers entre eux, $m = 1$ et $au_1+bv_1=1$.

En pratique, pour trouver $u$ et $v$, on utilise l’algorithme d’Euclide pour démontrer que les deux nombres sont premiers entre eux. Puis, on reprend chaque division euclidienne pour exprimer chaque reste au fur et à mesure. On trouve ainsi le couple solution.

bannière exemple

Exemple

Soit $a = 392$ et $b = 33$.

On écrit les divisions euclidiennes successives :

$392= 11\times33+29$

$33=1\times29+4$

$29=7\times4+1$

$4=4\times1+0$

Donc $\text{PGCD }(392\ ; 33) = 1$. Ainsi $a = 392$ et $b = 33$ sont premiers entre eux.

On réécrit les divisions euclidiennes en exprimant les restes :

  • $392=11\times33+29$ donc :

$\begin{aligned}29&=392-11\times33\\&=a-11b\end{aligned}$

  • $33=1\times29+4$ donc :

$\begin{aligned}4&=33-1\times29\\&=b-1\times(a-11b)\\&=12b-a\end{aligned}$

  • $29=7\times4+1$ donc :

$\begin{aligned}1&=29-7\times4\\&=(a-11b)-7\times(12b-a)\\&=8a-95b\end{aligned}$

Ainsi $a\times8+b\times(-95)=1$. Donc $u = 8$ et $v = -95$

Voici à présent une nouvelle caractérisation du $\text{PGCD}$ :

bannière definition

Définition

Nouvelle caractérisation du $PGCD$ :

Dans le $\text{PGCD }(a\ ;b)$, $a$ et $b$ sont toujours deux entiers naturels non nuls.

Dire que « $d$ est le $\text{PGCD}$ de $a$ et $b$ » revient à dire que « $d$ est un diviseur de $a$ et $b$ et qu’il existe deux entiers relatifs $u$ et $v$ tels que $d = au + bv$ ».

Théorème de Gauss

bannière theoreme

Théorème

Théorème de Gauss :

Soit $a$, $b$ et $c$ des entiers strictement positifs. Si $a$ divise le produit $bc$ tout en étant premier avec $b$, alors $a$ divise $c$.

bannière à retenir

À retenir

Autrement dit, si un entier naturel divise un produit de deux facteurs et s’il est premier avec l’un d’eux, il divise l’autre.

La démonstration est assez courte, elle fait appel à un autre théorème, le théorème de Bézout vu précédemment.

Puisque $a$ et $b$ sont premiers entre eux, d’après le théorème de Bézout, il existe des entiers relatifs $u$ et $v$ tels que $au + bv = 1$. Donc $(ac)u + (bc)v = c$. Or, $a$ divise $ac$ et $bc$ donc $a$ divise $acu + bcv$. Il en résulte que $a$ divise $c$.

bannière theoreme

Théorème

Corollaires du théorème de Gauss :

Si un entier naturel $n$ est divisible par deux entiers naturels $a$ et $b$ premiers entre eux, il est divisible par leur produit. Si un nombre premier $p$ divise un produit $ab$, alors $p$ divise $a$ ou $p$ divise $b$. Entre autres, on se sert de ces notions dans la résolution d’équations diophantiennes.

bannière definition

Définition

Équation diophantienne :

Une équation diophantienne est une équation dont les coefficients sont des nombres entiers et dont les solutions recherchées sont également entières.

bannière exemple

Exemple

Déterminons les entiers $x$ et $y$ tels que $2x+3y=5$

On remarque que $2\times(-1)+ 3\times1= 1$ donc le couple $(-1\ ; 1)$ est solution de cette équation.

De plus, $2x + 3y = 1$ équivaut à $2x + 3y = 2\times(-1)+ 3\times1$ ce qui équivaut à $2(x +1) = 3(-y +1)$.

Supposons que $(x\ ; y)$ soit solution de $2x + 3y = 1$ alors $3$ divise $2(x +1)$. Comme $3$ est premier avec $2$, d’après le théorème de Gauss, $3$ divise $(x + 1)$.

Donc il existe un entier $k$ tel que $x + 1 = 3k$ soit $x = -1+ 3k$.

En reportant la valeur de $x$ dans $2(x +1) = 3(-y +1)$, on obtient :

$2\times 3k = 3(-y +1)$ soit $-y +1= 2k$, soit $y = 1- 2k$.

Réciproquement, si $x = -1+ 3k$ et $y = 1- 2k$,

$\begin{aligned}2x+3y &=2(-1+3k)+3(1-2k)\\ &=-2+6k+3-6k\end{aligned}$

On a bien $2x+3y=1$

Les solutions de cette équation sont les couples $(-1+3k\ ;1-2k)$ avec $k∈\mathbb Z$.

Nombres premiers et application RSA

Rivest Shamir Adleman (presque toujours abrégé en RSA) est un algorithme de chiffrement très utilisé pour échanger des données confidentielles sur internet, notamment dans le commerce électronique. Cet algorithme a été décrit en 1977 par Ronald Rivest, Adi Shamir et Leonard Adleman.

Le fonctionnement de RSA repose sur une idée simple : il est facile de multiplier deux grands nombres premiers entre eux alors qu’il est très difficile de retrouver les facteurs premiers du nombre ainsi obtenu.

RSA est un algorithme de chiffrement à clé publique. Cela signifie que la clé de codage et l’algorithme de calcul ne sont pas cachés : n’importe quel émetteur peut envoyer un message au destinataire. Par contre, seul le destinataire peut le déchiffrer grâce à une clé de décodage privée qu’il tient secrète.

Le système est dit dissymétrique car les clés de codage et décodage sont différentes.

Le protocole du RSA repose sur le théorème suivant :

bannière theoreme

Théorème

Théorème RSA :

Soit $p$ et $q$ deux nombres premiers distincts et supérieurs ou égaux à 3.

On pose $n = p.q$

Si le nombre $e$ est un entier premier avec $m = (p -1)(q -1)$, alors il existe un entier $d$ strictement positif tel que  : $$ed ≡ 1 \text{mod} (p -1)(q -1)$$ et, pour cet entier $d$ et un entier naturel $A$ quelconque, on a : $$A^{ed} ≡ A \text{mod }(n)$$

bannière rappel

Rappel

$n$ désigne un entier naturel non nul, $a$ et $b$ sont des entiers relatifs.

On dit que $a$ et $b$ sont congrus modulo $n$ lorsque la différence $a - b$ est un multiple de $n$.

Voici les notations :

$a≡b\text{ mod }n$
ou :

$a≡b [n]$

ou encore :

$a≡b (n)$

bannière exemple

Exemple

Éline, l’émettrice, souhaite envoyer un message chiffré à Pierre, le destinataire.

  • Création de la clé privée  :

Pierre se donne un quadruplet de nombres $(p\ ; q\ ; e\ ; d)$ tel que : $p$ et $q$ sont deux nombres premiers ; $e$ est un entier premier avec le produit $(p -1)(q -1)$ et $d$ est un entier strictement positif tel que $ed ≡ 1\text{ mod }(p -1)(q -1)$. L’entier $d$ constitue la clé privée tenue secrète par Pierre.

  • Création de la clé publique  :

On pose $n = pq$. Pierre rend public le couple $(n ; e)$ qui constitue la clé publique.

  • Codage  :

Éline veut transmettre une information sous la forme d’un nombre $A$ à Pierre avec $A < n$ (si $A ≥ n$, elle transmet plusieurs nombres). Pour cela, elle calcule $B = A^e\text{ mod }(n )$ et envoie le nombre $B$ à Pierre.

  • Décodage  :

Pour décoder $B$, Pierre calcule $B^d ≡ A^{ed} ≡ A\text{ mod }(n)$, ce qui lui redonne $A$ d’après le théorème du RSA. Une petite remarque tout de même, on utilise, en réalité, de très grands nombres $n$, $p$ et $q$. L’inviolabilité du système en dépend. La sécurité du RSA réside en la difficulté de factoriser $n$ en produit de deux nombres premiers : si l’on réussit à factoriser $n$, le calcul de $d$ étant aisé, le code est facile à briser.