Fiche de révision : Arithmétiques et problèmes de codage (suite)

PGCD

Définitions : ensemble des diviseurs

• 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.
• Le plus grand élément des diviseurs de $a$ est $a$ (quand $a≠0$).
• L’ensemble des diviseurs communs à $a$ et $b$ $D(a\ ; b)$ est non vide puisqu’il contient toujours au moins $1$.
• Tous les nombres que contient l’ensemble des diviseurs communs à $a$ et à $b$ $D(a\ ; b)$ sont inférieurs ou égaux à $a$ et à $b$.

Définition : PGCD

• 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)$.
• $a$ et $b$ sont deux entiers naturels non nuls. Le plus grand commun diviseur de $a$ et $b$ est noté $\text{PGCD} (a\ ; b) $.
• On définit de la même manière le PGCD de deux entiers relatifs non nuls en prenant leurs valeurs absolues $\text{PGCD}(|a|\ ;|b|)$. 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|$.

Propriétés : PGCD

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

Algorithme d’Euclide

Remarque :

Pour déterminer le $PGCD$ de deux nombres $a$ et $b$ entiers naturels non nuls avec $a$ strictement supérieur à $b$ $a >b$, on utilise l’algorithme d’Euclide, vu en troisième.

Théorème : algorithme d’Euclide

$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$ sont identiques à 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)$.

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)$$

Propriété :

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.

Entiers premiers entre eux

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$.

Théorème : 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$ »

Démonstration :

Supposons que $\text {PGCD} (a'\ ; b') = d'$ 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''$ et 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$.

Théorème de Bézout

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$ ».

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}$

Théorème : 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

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$.

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.

Démonstration :

La démonstration est assez courte, elle fait appel au théorème de Bézout :

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$.

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$.

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.

Nombres premiers et application RSA

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.

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 \equiv 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)$$

Définition : modulo (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)$