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 !

PGCD

Définitions : ensemble des diviseurs

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

Définition : PGCD

  • 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).
  • 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) .
  • On définit de la même manière le PGCD de deux entiers relatifs non nuls en prenant leurs valeurs absolues PGCD(a ;b)\text{PGCD}(|a|\ ;|b|). 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|.

Propriétés : PGCD

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

  • 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.
  • 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)\text{PGCD} (a\ ; b)=\text{PGCD} (b\ ;a)=\text{PGCD} (|a|\ ;|b|).
  • Les diviseurs communs à aa et bb sont les diviseurs de leur PGCD\text{PGCD}.
  • Pour tous entiers relatifs aa et bb non tous deux 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×\text{PGCD} (a\ ;b)

Algorithme d’Euclide

Remarque :

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

Théorème : algorithme d’Euclide

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

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

Propriété :

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.

Entiers premiers entre eux

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.

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

Démonstration :

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

Théorème de Bézout

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

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}

Théorème : caractérisation du PGCD

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

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.

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

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.

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 pp et qq deux nombres premiers distincts et supérieurs ou égaux à 33.

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

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