Divisibilité et congruence
Divisibilité
Dans toute la suite de cette section, on notera par l’ensemble des nombres entiers relatifs (i.e. ) et par l’ensemble des nombres entiers naturels (i.e. ).
Définition
Soient et deux entiers relatifs. On dit que divise (ou que est un multiple de ) s’il existe tel que . On note ceci par .
Si on a divise , alors divise . Par exemple, comme divise , alors divise également .
Propriétés
Tout entier relatif divise (car ).
divise tout entier relatif (car ).
Si et alors pour tout , .
Division euclidienne
La division euclidienne est une notion mathématique que l’on aborde très tôt au cours de notre scolarité (dès la classe de CM1). Nous allons tenter de formaliser ceci :
Théorème de la division euclidienne
Soient , . On suppose . On appelle division euclidienne de par , l’opération qui à , associe le couple d’entiers relatifs tel que où . Un tel couple existe forcément et est unique.
Vocabulaire
En reprenant les notations du théorème, s’appelle le dividende, le diviseur, le quotient et le reste de la division euclidienne.
Exemple
On souhaite effectuer la division euclidienne de par . Posons-la :
On cherche combien de fois est contenu dans (cela ne sert à rien de commencer par car ). On a et donc on écrit sous le diviseur et le reste . Puis, on abaisse le chiffre des unités qui est .
On recommence : combien de fois est-il contenu dans ? Comme et , est contenu fois dans et il reste .
Comme , la division euclidienne est terminée : on a .
Donnons enfin une propriété qui nous sera utile dans la section suivante.
Propriété
Soit tel que . Deux entiers relatifs et ont le même reste dans la division euclidienne par si et seulement si est un multiple de .
Congruences dans
Définition
On dit que deux entiers relatifs et sont congrus modulo (où est un entier naturel supérieur ou égal à ) si et ont le même reste dans la division euclidienne par . On note alors .
On remarque que est un multiple de si et seulement si .
Exemple
Par exemple, .
On signale que la congruence est une relation d’équivalence.
Propriétés
Soit . Pour tout , , :
(réflexivité)
Si , alors (symétrie)
Si , et si , alors (transitivité)
De plus, la congruence est compatible avec les opérations usuelles sur les entiers relatifs.
Propriétés
Soit . Soient , , et tels que et . Alors on a la compatibilité avec :
L’addition : .
La multiplication : .
Les puissances : pour tout , .
Exemple
Comme , et , on a .
PGCD et théorème de Bézout
Plus Grand Commun Diviseur
Définition
Soient , non tous nuls. Le Plus Grand Commun Diviseur de et (noté ) est le plus grand entier positif qui les divise simultanément.
Avec cette définition, on peut dégager quelques propriétés.
Propriétés
Soient , non tous nuls.
Pour tout ,
Si , alors
Il existe une manière de déterminer le de deux entiers naturels non nuls et avec appelée Algorithme d’Euclide.
Algorithme d’Euclide
Soient , non tous nuls. Pour obtenir , on procède comme suit :
On fait la division euclidienne de par et on appelle le reste.
Si , alors .
Sinon on recommence l’étape 1 en remplaçant par et par .
Terminons cette section par une définition.
Nombres premiers entre eux
On dit que deux nombres sont premiers entre eux si leur est égal à 1.
Petite remarque : si on note le de deux nombres et , alors et sont deux nombres premiers entre eux.
Théorème de Bézout
Un résultat fondamental de l’arithmétique est le théorème de Bachet-Bézout (que l’on rencontre parfois sous le nom d’identité de Bézout).
Théorème de Bachet-Bézout
Soient et deux entiers relatifs non nuls. On note leur PGCD. Alors il existe deux entiers relatifs et tels que .
Théorème de Bézout
Une conséquence de ce théorème est que et sont premiers entre eux si et seulement s’il existe deux entiers relatifs et tels que .
Exemple
Calculons et déduisons-en deux entiers relatifs et tels que . Commençons par calculer le de et par l’algorithme d’Euclide :
La division euclidienne de par donne . La division euclidienne de par donne . La division euclidienne de par donne .
On a . Déterminons et :
Donc .
On a par conséquent et . L’algorithme que l’on vient d’utiliser pour trouver et s’appelle l’algorithme d’Euclide étendu.
Résolution d’une congruence simple
Supposons que l’on souhaite résoudre une congruence du type d’inconnue . On pose . Alors :
Si ne divise pas , on cherche deux entiers et tels que (avec l’algorithme d’Euclide étendu par exemple). Les solutions de la congruence sont alors les entiers vérifiant .
Si , cela revient à résoudre la congruence , et on se ramène au cas 1 (avec la nouvelle congruence à résoudre).
Exemple
On souhaite résoudre la congruence . Alors, comme , on a . On se ramène donc à résoudre (où et sont premiers entre eux).
On écrit l’identité de Bézout appliquée à et : . Donc les solutions à la congruence du début sont les entiers vérifiant (i.e. les de la forme où ).
Lemme de Gauss
Lemme de Gauss
Soient , et trois entiers non nuls. Si et est premier avec , alors .
Corollaire
Soient , et trois entiers non nuls. Si , et que et sont premiers entre eux, alors .
Équations diophantiennes
Définition
Une équation diophantienne linéaire en deux variables et est une équation de la forme où les coefficients , et sont des entiers relatifs et où les solutions sont également des entiers relatifs.
Solutions de
En reprenant les notations précédentes, on pose . Alors :
Si , on cherche une solution particulière à que l’on note . Alors les solutions de sont les couples où et .
Sinon, n’a pas de solution.
Exemple
On cherche à résoudre l’équation diophantienne . Commençons par chercher une solution particulière .
Comme , on a . En divisant les deux côtés de l’égalité par , on a .
Cherchons une solution particulière à . On écrit l’identité de Bézout appliquée à et : . Ainsi, en multipliant les deux côtés de l’égalité par , on obtient : .
On a trouvé une solution particulière à qui est le couple ) où et . On pourrait appliquer la formule pour donner la forme générale des solutions de , mais essayons de ne pas l’utiliser.
Soit une autre solution de . On a . D’où (en passant les et du même côté de l’égalité et en faisant de même pour et , puis en factorisant).
Ainsi, on a . Or, et sont premiers entre eux, donc par le lemme de Gauss, . Il existe donc tel que , d’où .
De même, avec et premiers entre eux, donc par le lemme de Gauss, . Il existe donc tel que , d’où .
En réinjectant tout ça dans , on obtient .
Les solutions de sont donc les couples où et (et on a bien les mêmes résultats qu’avec la formule).
Nombres premiers
Définition
Commençons cette section par définir ce qu’est un nombre premier. Il s’agit là d’une notion dont entend parler très tôt au cours de notre scolarité, sans pour autant vraiment rentrer dans le sujet. Détaillons donc un peu tout ceci.
Nombre premier
Un nombre entier est dit premier si ses seuls diviseurs positifs sont et lui-même.
Exemple
, , , , et sont des nombres premiers.
Propriétés
Voici quelques propriétés basiques que possèdent les nombres premiers.
Propriétés
Soit supérieur ou égal à 2, alors on a les propriétés suivantes :
Si n’admet aucun diviseur premier inférieur ou égal à , alors est premier.
Si n’est pas premier alors admet au moins un diviseur premier inférieur ou égal à .
Si est premier et ne divise pas un entier , alors et sont premiers entre eux.
Lemme d’Euclide
Soit un nombre premier et et deux entiers. Si alors ou .
On donne enfin un résultat fondamental (mais qui reste très simple) sur l’ensemble des nombres premiers.
Infinité de nombres premiers
Il existe une infinité de nombres premiers.
Infinité de nombres premiers
Supposons par l’absurde que l’ensemble des nombres premiers soit un ensemble fini. On note par cet ensemble et par sont cardinal. On a donc où , , ... , sont premiers.
Soit . Alors, donc n’est pas premier (et est strictement supérieur à ). Il existe donc un nombre premier qui divise .
En d’autres mots, il existe tel que . De plus, .
Donc , donc ou : c’est absurde car .
Pour la petite histoire, c’est Euclide qui a fourni une première version de cette preuve en 300 av. J.-C !
Petit théorème de Fermat
Soit un nombre premier et un entier non divisible par . Alors .
Cela revient au même de dire que si est un entier quelconque et que est un nombre premier, alors .
Décomposition de nombres
Passons maintenant à un résultat fondamental de l’arithmétique : le principe de décomposition en produit de facteurs premiers (il s’agit même là d’un théorème qui est sobrement intitulé théorème fondamental de l’arithmétique).
Théorème fondamental de l’arithmétique
Soit supérieur ou égal à 2, alors peut s’écrire de la façon suivante : où , , ... , des nombres premiers tels que et , , ... , des entiers naturels non nuls.
Exemple
Décomposons en produit de facteurs premiers.
( est le plus petit nombre premier qui divise ).
( est le plus petit nombre premier qui divise ).
( est le plus petit nombre premier qui divise ).
( est le plus petit nombre premier qui divise ).
( est un nombre premier, c’est terminé).
On a donc .