Déjà plus de
1 million
d'inscrits !
Déjà plus de
1 million
d'inscrits !
PGCD
Définitions : ensemble des diviseurs
Définition : PGCD
Propriétés : PGCD
Sachant que et sont deux entiers naturels supérieurs ou égaux à :
Algorithme d’Euclide
Remarque :
Pour déterminer le de deux nombres et entiers naturels non nuls avec strictement supérieur à , on utilise l’algorithme d’Euclide, vu en troisième.
Théorème : algorithme d’Euclide
et sont deux entiers naturels non nuls tels que la division euclidienne de par se traduit par avec compris entre et tous deux exclus .
Alors l’ensemble des diviseurs commun à et sont identiques à ceux communs à et ce qui amène à .
Démonstration :
si divise et , divise toute combinaison linéaire de et , donc en particulier , soit .
Il en résulte que l’ensemble des diviseurs de et sont inclus dans les diviseurs de et :
Si divise et , divise toute combinaison linéaire de et , donc en particulier bq+r, soit . Il en résulte que l’ensemble des diviseurs de et figurent parmi les diviseurs de et : .
La double inclusion équivaut donc à dire que l’ensemble des diviseurs à et sont communs à ceux de et .
Ces deux ensembles étant identiques, ils ont le même plus grand élément donc :
Propriété :
Lorsque ne divise pas , le de et 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 et sont premiers entre eux signifie que leur est égal à .
Théorème : caractérisation du
et sont deux entiers naturels non nuls.
« est le de et » équivaut à « il existe deux entiers naturels et tels que : ; ; »
Démonstration :
Supposons que alors et où et sont des entiers.
Par conséquent, et et ainsi (qui est strictement supérieur à ) est un diviseur de et de , ce qui contredit . Donc .
Théorème de Bézout
Théorème de Bézout :
et sont deux entiers naturels non nuls. Dire « et sont premiers entre eux » équivaut à dire « il existe deux entiers relatifs et tels que ».
Démonstration :
Supposons qu’il existe deux entiers et tels que et prouvons que et sont premiers entre eux.
On note . divise et donc divise .
Comme , et et sont premiers entre eux.
Supposons et premiers entre eux et démontrons que s’écrit sous la forme . Soit l’ensemble des nombres de la forme , avec et .
L’ensemble n’est pas vide car pour et , ∈ . Il en est de même pour .
Ainsi contient des entiers strictement positifs et, parmi eux, un plus petit que tous les autres.
Notons ce plus petit élément. La division euclidienne de par s’écrit avec
soit
Théorème : caractérisation du PGCD
Dans le , et sont toujours deux entiers naturels non nuls.
Dire que « est le de et » revient à dire que « est un diviseur de et et qu’il existe deux entiers relatifs et tels que ».
Théorème de Gauss
Théorème de Gauss:
Soit , et des entiers strictement positifs ;
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 et sont premiers entre eux, d’après le théorème de Bézout, il existe des entiers relatifs et tels que . Donc . Or, divise et donc divise . Il en résulte que divise .
Corollaires du théorème de Gauss :
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 et deux nombres premiers distincts et supérieurs ou égaux à .
On pose
Si le nombre est un entier premier avec , alors il existe un entier strictement positif tel que :
et, pour cet entier et un entier naturel quelconque, on a :
Définition : modulo (rappel)
désigne un entier naturel non nul, et sont des entiers relatifs.
On dit que et sont congrus modulo lorsque la différence est un multiple de .
Voici les notations :
ou :
ou encore :