4.1. DIVISION EUCLIDIENNE



THÉORIES DES NOMBRES

1. Principe du bon ordre

2. Propriété archimédienne

3. Principe d'induction

4. Divisibilité

4.1. Division euclidienne

4.1.1. Plus grand commun diviseur

4.1.2. Algorithme d'euclide

4.1.3. Plus petit commun multiple

4.2. Théorème fondamental de l'arithmétique

4.3. Congruences

4.3.1. Classes de congruence

4.4. Fractions continues

La division euclidienne est une opération qui, à deux entiers naturels appelés dividende et diviseur, associe deux entiers appelés quotient et reste. Initialement définie aux entiers naturels non nuls, elle se généralise aux entiers relatifs et aux polynômes, par exemple.

Définition: Nous appelons "division euclidienne" ou "division entière" de deux nombres A et B l'opération consistant à diviser B par A en s'arrêtant quand le reste devient strictement inférieur à A.

Rappelons que tout nombre qui n'a pas de diviseur euclidien autre 1 et lui-même est dit "nombre premier" et que tout couple de nombres qui n'ont que 1 comme diviseur euclidien commun sont dits "premiers entre eux".

Soit equation avec equation. Le "théorème de la division euclidienne" affirme qu'il existe des entiers uniques  q et r tels que :

equation   (4.19)

equation. De plus, si equation, alors equation.

Démonstration:

Considérons l'ensemble:

equation   (4.20)

Il est facile de voir que equation et que equation, d'où, d'après le principe du bon ordre, nous concluons que S contient un plus petit élément equation. Soit q l'entier satisfaisant donc à

equation   (4.21)

Nous voulons d'abord montrer que equation en supposant le contraire (démonstration par l'absurde), c'est-à-dire que equation. Alors, dans ce cas, nous avons :

equation   (4.22)

ce qui est équivalent à:

equation   (4.23)

mais equation et:

equation   (4.24)

ce qui contredit le fait que :

equation    (4.25)

est le plus petit élément de S. Donc, equation. Enfin, il est clair que si equation, nous avons A|B, d'où la seconde affirmation du théorème.

equationC.Q.F.D.

Remarque: Dans l'énoncé de la division euclidienne, nous avons supposé que equation. Qu'obtenons-nous lorsque equation? Dans cette situation, -A est positif, et alors nous pouvons appliquer la division euclidienne à B et -A. Par conséquent, il existe des entiers  q et r  tels que:

equationequation   (4.26)

Or, cette relation peut s'écrire equation, où bien sûr, -q est un entier. La conclusion est que la division euclidienne peut s'énoncer sous la forme plus générale : 

Soit equation, alors il existe des entiers  q et r tels que equation, où equation. De plus, si equation, alors equation.

Les entiers  q et r sont dans la division euclidienne uniques. En effet, s'il existe deux autres entiers equation et equation tels que equation avec toujours equation, alors equation et ainsi equation. En vertu de (T5) nous avons, si equation, equation. Or, cette dernière inégalité est impossible puisque equation. Donc, equation et, puisque equation, alors equation; d'où l'unicité.

PLUS GRAND COMMUN DIVISEUR

Soit equation tels que equation. Le "plus grand commun diviseur" (noté "PGCD" par la suite) de a et b, noté :

 equation   (4.27)

est l'entier naturel  d non nul qui satisfait aux deux propriétés suivantes :

P1. d|a et d|b (donc sans reste r dans la division!)

P2. si c|a et c|b alors equation et c|d (par définition!)

Notons que 1 est toujours un diviseur commun de deux entiers arbitraires.

exempleExemple:

Considérons les entiers positifs 36 et 54. Un diviseur commun de 36 et 54 est un entier positif qui divise 36, et aussi 54. Par exemple, 1 et 2 sont des diviseurs communs de 36 et 54.

equation   (4.28)

Nous avons alors l'intersection représentée par le diagramme de Venn suivant:

equation
  (4.29)

avec l'ensemble des diviseurs communs suivant:

equation   (4.30)

et donc le PGCD est:

equation   (4.31)

et nous constatons que l'ensemble des diviseurs communs de 36 et 54 est aussi l'ensemble des
diviseurs de 18.

Cependant, il n'est pas forcément évident que le PGCD autre qu'unitaire (c'est-à-dire différent 1) de deux entiers a et b qui ne sont pas premier entre eux existe toujours. Ce fait est démontré dans le théorème suivant (cependant, si le PGCD existe, il est de par sa définition unique!) dit "théorème de Bézout" qui permet aussi de démontrer d'autres propriétés intéressantes de deux nombres comme nous le verrons plus tard.

Démonstration:

Soit equation  tels que equation. Si d divise a et d divise b (pour les deux sans reste r!) il existe alors obligatoirement des entiers relatifs x et y tels que:

equation   (4.32)

Cette relation est appelée "identité de Bézout" et il s'agit d'une équation diophantienne linéaire (cf. chapitre de Calcul Algébrique).

Evidemment, si a et b sont premiers entre eux nous savons que d vaut alors 1.

Pour démontrer l'identité de Bézout considérons d'abord l'ensemble:

equation   (4.33)

Comme equation et equation , nous pouvons utiliser le principe du bon ordre et conclure que S possède un plus petit élément d. Nous pouvons alors écrire:

equation   (4.34)  

pour un certain choix equation. Il suffit donc de montrer que equation pour démontrer l'identité de Bézout!

Procédons via une démonstration par l'absurde en posant supposant equation. Alors si c'est le cas, d'après la division euclidienne, il existe equation tels que equation, où equation. Mais alors:

equation   (4.35)

Ainsi, nous avons que equation et equation, ce qui contredit le fait que d est le plus petit élément possible de S. Donc nous avons démontré ainsi non seulement que d|a mais qu'en plus d existe toujours et, de la même façon, nous démontrons que d|b.

Comme corollaire important montrons maintenant que si equation tels que equation, alors :

equation   (4.36)

constitue l'ensemble de tous les multiples de equation:

Comme d|a et d|b, alors equation pour tout equation. Soit equation. Nous voulons montrer que equation.

Soit d'abord equation ce qui signifie que d|s et qui implique equation. Soit un equation, cela voudrait donc dire que equation pour un certain equation.

Comme equation pour un choix d'entiers quelconques equation, alors:

equation   (4.37)

equationC.Q.F.D.

Les hypothèses peuvent sembler compliquées mais portez plutôt votre attention un certain temps sur la dernière relation. Vous allez tout de suite comprendre!

Remarque: Si au lieu de définir le PGCD de deux entiers non nuls, nous permettons à l'un d'entre eux d'être égal à 0, disons equation, equation? Dans ce cas, nous avons a|b et , selon notre définition du PGCD, il est clair que equation.

Soit equation et soit equation, alors nous avons les propriétés suivantes du PGCD :

P1. equation

P2. equation où equation

P3. equation

P4. Si equation tel que g|a et g|b alors equation

Dans certains ouvrages, ces quatre propriétés sont démontrées en utilisant intrinsèquement la propriété elle-même. Personnellement nous nous en abstiendrons car faire cela est plus ridicule qu'autre chose à notre goût car la propriété est une démonstration en elle-même.

Elaborons maintenant une méthode qui s'avérera très importante pour calculer le plus grand commun diviseur de deux entiers (utile en informatique parfois).

ALGORITHME D'EUCLIDE

L'algorithme d'Euclide est un algorithme permettant de déterminer le plus grand commun diviseur de deux entiers.

Pour aborder cette méthode de manière intuitive, il faut savoir que vous devez comprendre un nombre entier comme une longueur, un couple d'entiers comme un rectangle (côtés) et leur PGCD est la taille du plus grand carré permettant de carreler (paver) ce rectangle par définition (oui si vous réfléchissez un petit moment c'est assez logique!).

L'algorithme décompose le rectangle initial en carrés, de plus en plus petits, par divisions euclidiennes successives, de la longueur par la largeur, puis de la largeur par le reste, jusqu'à un reste nul. Il faut bien comprendre cette démarche géométrique pour comprendre ensuite l'algorithme.

exempleExemple:

Considérons que nous cherchons le PGCD (a,b) où b vaut 21 et a vaut15 et gardons à l'esprit que le PGCD, outre le fait qu'il divise a et b, doit laisser un reste nul! En d'autres termes il doit pouvoir diviser le reste de la division de b par a aussi!

Nous avons donc le rectangle de 21 par 15 suivant:

equation
  (4.38)

D'abord nous regardons si 15 est le PGCD (on commence toujours par le plus petit). Nous divisons alors 21 par 15 ce qui équivaut géométriquement à:

equation
  (4.39)

15 n'est donc pas le PGCD (on s'en doutait...). Nous voyons immédiatement que nous n'arrivons pas à paver le rectangle avec un carré de 15 par 15.

Nous avons donc un reste de 6 (rectange de gauche). Le PGCD comme nous le savons doit, s'il existe, par définition pouvoir diviser ce reste et laisser un reste nul.

Il nous reste donc un rectangle de 15 par 6. Nous cherchons donc maintenant à paver ce nouveau rectangle car nous savons que le PGCD est par construction inférieur ou égal à 6. Nous avons alors:

equation
  (4.40)

Et nous divisons donc 15 par le reste 6 (ce résultat sera inférieur à 6 et permet immédiatement de tester si le reste sera le PGCD). Nous obtenons:

equation
  (4.41)

A nouveau, nous n'arrivons pas à paver ce rectangle rien qu'avec des carrés. En d'autres termes, nous avons un reste non nul qui vaut 3. Soit un rectangle de 6 par 3. Nous cherchons donc maintenant à paver ce nouveau rectangle car nous savons que le PGCD est par construction inférieur ou égal à 3 et qu'il laissera un reste nul si il existe. Nous avons alors géométriquement:

equation
  (4.42)

Nous divisons 6 par 3 (ce qui sera inférieur à 3 et permet immédiatement de tester si le reste sera le PGCD):

equation
  (4.43)

et c'est tout bon! Nous avons 3 qui laisse donc un reste nul et divise le reste 6 il s'agit donc du PGCD. Nous avons donc au final:

equation

Maintenant, voyons l'approche formelle équivalente:

Soit equation, où equation. En appliquant successivement la division euclidienne (avec b>a), nous obtenons la suite d'équations:

 equation   (4.44)

Si equation, alors equation.

Sinon de manière plus formelle:

Démonstration:

Nous voulons d'abord montrer que equation. Or, d'après la propriété :

equation   (4.45)

nous avons :

equation   (4.46)

Pour démontrer la deuxième propriété de l'algorithme d'Euclide, nous écrivons l'avant dernière équation du système sous la forme:

equation   (4.47)

Or, en utilisant l'équation qui précède cette avant dernière équation du système, nous avons :

 equation   (4.48)

En continuant ce processus, nous arrivons à exprimer equation comme une combinaison linéaire de a et b.

equationC.Q.F.D.

exempleExemple:

Calculons le plus grand commun diviseur de (966,429) et exprimons ce nombre comme une combinaison linéaire de 966 et de 429.

Nous appliquons bien évidemment l'algorithme d'Euclide: 

equation   (4.49)

Nous en déduisons donc que :

 equation   (4.50)

et, de plus, que:

equation   (4.51)

Donc le PGCD est bien exprimé comme une combinaison linéaire de a et b et constitue à ce titre le PGCD.

Définition: Nous disons que les entiers equation sont "relativement premiers" si :

equation   (4.52)

PLUS PETIT COMMUN MULTIPLE

Définitions:

D1. Soit equation, nous disons que m est un "commun multiple" de equation si equation pour equation.

D2. Soit equation, nous appelons "plus petit commun multiple" (PPCM) de equation, noté : 

equation   (4.53)

le plus petit entier positif par tous les communs multiples de equation.

exempleExemple :

Considérons les entiers positifs 3 et 5. Un multiple commun de 3 et 5 est un entier positif qui est à la fois un multiple de 3, et un multiple de 5. Autrement dit, qui est divisible par 3 et aussi par 5. Nous avons donc:

equation   (4.54)

Nous avons alors l'intersection représentée par le diagramme de Venn suivant:

equation
  (4.55)

avec l'ensemble des communes multiples suivant:

equation   (4.56)

et le PPCM est alors:

equation   (4.57)

On constate que l'ensemble des multiples communs de 3 et 5 est aussi l'ensemble des multiples de 15.

Remarque: Soit equation. Alors, le plus petit commun multiple existe. En effet, considérons l'ensemble:

equation   (4.58)

Puisque equation, alors l'ensemble est non vide et, d'après l'axiome du bon ordre, l'ensemble E contient un plus petit élément positif.

Voyons maintenant quelques théorèmes relatifs au PPCM :

T1. Si m est un commun multiple de equation alors equation

Démonstration:

Soit equation. Alors, d'après la division euclidienne, il existe des entiers  q et r tels que:

equation   (4.59)

Il suffit de montrer que equation. Supposons equation (démonstration par l'absurde). Puisque equation et equation, alors on a equation et cela pour equation. Donc, r est un commun multiple de equation plus petit que le PPCM On vient d'obtenir une contradiction, ce qui prouve le théorème.

equationC.Q.F.D.

T2. Si equation, alors equation

La démonstration sera supposée évidente (dans le cas contraire contactez-nous et cela sera détaillé!)

T3. equation

Démonstration:

Pour la démonstration, nous allons utiliser le "lemme d'Euclide" qui dit que si a|bc et equation alors a|c.

Effectivement cela se vérifie aisément car nous avons vu qu'il existe equation tels que equation et alors equation. Mais a|ac et a|bc impliquent que equation, c'est-à-dire également que equation.

Revenons à notre théorème:

Puisque equation et equation, il suffit de prouver le résultat pour des entiers positifs a et b. En tout premier lieu, considérons le cas où equation. L'entier [a,b] étant un multiple de a, nous pouvons écrire equation. Ainsi, nous avons equation et, puisque equation, il s'ensuit, d'après le lemme d'Euclide, que b | m. Donc, equation et alors equation. Mais ab est un commun multiple de a et b qui ne peut être plus petit que le PPCM. c'est pourquoi equation.

Pour le cas général, c'est-à-dire equation, nous avons, d'après la propriété :

 equation   (4.60)

et avec le résultat obtenu précédemment que:

equation   (4.61)

Lorsque nous multiplions des deux côtés de l'équation par equation, le résultat suit et la démonstration est effectuée.

equationC.Q.F.D.


page suivante : 4.2. Théorème fondamental de l'arithmétique