Médaille
N°1 pour apprendre & réviser du collège au lycée.
Arithmétiques et problèmes de codage (suite)

Déjà plus de

1 million

d'inscrits !

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 PGCD\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 aa, on note D(a)\text D(a) l’ensemble des diviseurs de aa.

bannière exemple

Exemple

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

Propriété

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

bannière à retenir

À retenir

Quelques remarques s’imposent :

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

Définition

PGCD :

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

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

bannière propriete

Propriété

Sachant que aa et bb sont deux entiers naturels supérieurs ou égaux à 2 :

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

Exemple

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

2070=2×32×5×23368=24×23\begin{aligned}2070&=2\times3^2\times5\times23\368&=2^4\times23\end{aligned}

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

bannière propriete

Propriété

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

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

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

Algorithme d’Euclide

bannière theoreme

Théorème

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

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

bannière demonstration

Démonstration

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

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

bannière à retenir

À retenir

Lorsque bb ne divise pas aa, le PGCD\text{PGCD} de aa et bb 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 20702070 et 368368. On écrit les divisions euclidiennes successives :

2070=5×368+230368=1×230+138230=1×138+92138=1×92+4692=2×46+0\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 PGCD (2070 ;368)=46\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 aa et bb sont premiers entre eux signifie que leur PGCD\text{PGCD} est égal à 11.

bannière attention

Attention

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

bannière definition

Définition

Caractérisation du PGCD\text {PGCD} :

aa et bb sont deux entiers naturels non nuls. « dd est le PGCD\text {PGCD} de aa et bb » équivaut à « il existe deux entiers naturels aa' et bb' tels que :

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

bannière demonstration

Démonstration

Supposons que PGCD (a ;b)=d1\text {PGCD }(a'\ ; b') = d' ≠1, alors a=daa'= d'a'' et b=dbb' = d'b''aa'' et bb'' sont des entiers.

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

Donc PGCD (a ;b)=1\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 :
aa et bb sont deux entiers naturels non nuls. Dire « aa et bb sont premiers entre eux » équivaut à dire « il existe deux entiers relatifs uu et vv tels que au+bv=1au+bv = 1 ».

bannière demonstration

Démonstration

Supposons qu’il existe deux entiers uu et vv tels que au+bv=1au+bv=1 et prouvons que aa et bb sont premiers entre eux.

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

Comme au+bv=1au+bv=1, d=1d=1 et aa et bb sont premiers entre eux.

Supposons aa et bb premiers entre eux et démontrons que 11 s’écrit sous la forme au+bvau+bv. Soit ε\varepsilon l’ensemble des nombres de la forme au+bvau+bv, avec uZu ∈\mathbb Z et vZv ∈\mathbb Z.

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

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

Notons m=au1+bv1m = au1+bv1 ce plus petit élément. La division euclidienne de aa par mm s’écrit a=mq+ra=mq+r avec 0r<m0 ≤ r < m

soit r=amq=a(au1+bv1)q=a(1u1q)+b(v1q)\begin{aligned}r&=a-mq\&=a-(au1+bv1)q\&=a(1-u1q)+b(-v1q)\end{aligned}

Ainsi r ∈ ε\varepsilon.

Or mm est le plus petit entier strictement positif de ε\varepsilon donc r=0r=0. Ainsi mm divise aa. On montre de même que mm divise bb.

Comme aa et bb sont premiers entre eux, m=1m = 1 et au1+bv1=1au1+bv1=1.

En pratique, pour trouver uu et vv, 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=392a = 392 et b=33b = 33.

On écrit les divisions euclidiennes successives :

392=11×33+29392= 11\times33+29

33=1×29+433=1\times29+4

29=7×4+129=7\times4+1

4=4×1+04=4\times1+0

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

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

  • 392=11×33+29392=11\times33+29 donc :

29=39211×33=a11b\begin{aligned}29&=392-11\times33\&=a-11b\end{aligned}

  • 33=1×29+433=1\times29+4 donc :

4=331×29=b1×(a11b)=12ba\begin{aligned}4&=33-1\times29\&=b-1\times(a-11b)\&=12b-a\end{aligned}

  • 29=7×4+129=7\times4+1 donc :

1=297×4=(a11b)7×(12ba)=8a95b\begin{aligned}1&=29-7\times4\&=(a-11b)-7\times(12b-a)\&=8a-95b\end{aligned}

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

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

bannière definition

Définition

Nouvelle caractérisation du PGCDPGCD :

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

Dire que « dd est le PGCD\text{PGCD} de aa et bb » revient à dire que « dd est un diviseur de aa et bb et qu’il existe deux entiers relatifs uu et vv tels que d=au+bvd = au + bv ».

Théorème de Gauss

bannière theoreme

Théorème

Théorème de Gauss :

Soit aa, bb et cc des entiers strictement positifs. Si aa divise le produit bcbc tout en étant premier avec bb, alors aa divise cc.

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 aa et bb sont premiers entre eux, d’après le théorème de Bézout, il existe des entiers relatifs uu et vv tels que au+bv=1au + bv = 1. Donc (ac)u+(bc)v=c(ac)u + (bc)v = c. Or, aa divise acac et bcbc donc aa divise acu+bcvacu + bcv. Il en résulte que aa divise cc.

bannière theoreme

Théorème

Corollaires du théorème de Gauss :

Si un entier naturel nn est divisible par deux entiers naturels aa et bb premiers entre eux, il est divisible par leur produit. Si un nombre premier pp divise un produit abab, alors pp divise aa ou pp divise bb. 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 xx et yy tels que 2x+3y=52x+3y=5

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

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

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

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

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

2×3k=3(y+1)2\times 3k = 3(-y +1) soit y+1=2k-y +1= 2k, soit y=12ky = 1- 2k.

Réciproquement, si x=1+3kx = -1+ 3k et y=12ky = 1- 2k,

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

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

Les solutions de cette équation sont les couples (1+3k ;12k)(-1+3k\ ;1-2k) avec kZk∈\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 pp et qq deux nombres premiers distincts et supérieurs ou égaux à 3.

On pose n=p.qn = p.q

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

bannière rappel

Rappel

nn désigne un entier naturel non nul, aa et bb sont des entiers relatifs.

On dit que aa et bb sont congrus modulo nn lorsque la différence aba - b est un multiple de nn.

Voici les notations :

ab mod na≡b\text{ mod }n
ou :

ab[n]a≡b [n]

ou encore :

ab(n)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)(p\ ; q\ ; e\ ; d) tel que : pp et qq sont deux nombres premiers ; ee est un entier premier avec le produit (p1)(q1)(p -1)(q -1) et dd est un entier strictement positif tel que ed1 mod (p1)(q1)ed ≡ 1\text{ mod }(p -1)(q -1). L’entier dd constitue la clé privée tenue secrète par Pierre.

  • Création de la clé publique  :

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

  • Codage  :

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

  • Décodage  :

Pour décoder BB, Pierre calcule BdAedA mod (n)B^d ≡ A^{ed} ≡ A\text{ mod }(n), ce qui lui redonne AA 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 nn, pp et qq. L’inviolabilité du système en dépend. La sécurité du RSA réside en la difficulté de factoriser nn en produit de deux nombres premiers : si l’on réussit à factoriser nn, le calcul de dd étant aisé, le code est facile à briser.