loadingPage en cours de chargement
    ACCUEIL | TÉLÉCHARGER | QCM | DON | ANNONCES | CHAT | FORUM | LIVRE D'OR | PARTENAIRES | CONTACT | BLOG
 
  Rechercher
  separation
  Introduction
  Arithmétique
  Algèbre
  Analyse
  Géométrie
  Mécanique
  Électrodynamique
  Atomistique
  Cosmologie
  Chimie
  Informatique Théorique
  Maths. Sociales
  Ingénierie
  separation
  Biographies
  Références
  Liens
  separation
  Humour
  Serveur d'exercices
  separation
  Parrains
6 connectés
News News :: Erreur Erreur :: Statistiques Visiteurs :: ClearType ClearType :: Imprimer Imprimer :: Bookmark and Share

Arithmétique

THÉORIE DE LA DÉMONSTRATION | NOMBRES | OPÉRATEURS ARITHMÉTIQUES
THÉORIE DES NOMBRES | THÉORIE DES ENSEMBLES | PROBABILITÉS | STATISTIQUES

4. THÉORIE DES NOMBRES

Dernière mise à jour de ce chapitre: 2017-08-06 17:23:03 | {oUUID 1.703}
Version:3.1 Révision 3 | Avancement: ~90%
viewsvues depuis le 2012-01-01: 8'473

Table des matières LISTE DES SUJETS TRAITÉS SUR CETTE PAGE

Traditionnellement, la théorie des nombres est une branche des mathématiques qui s'occupe des propriétés des nombres entiers, qu'ils soient entiers naturels ou entiers relatifs. Plus généralement, le champ d'étude de cette théorie concerne une large classe de problèmes qui proviennent naturellement de l'étude des entiers. La théorie des nombres peut être divisée en plusieurs branches d'étude (théorie algébrique des nombres, théorie calculatoire des nombres, etc.) en fonction des méthodes utilisées et des questions traitées.

Remarque:Le terme "arithmétique" était aussi utilisé pour faire référence à la théorie des nombres mais c'est un terme assez ancien, qui n'est plus aussi populaire que par le passé.

Nous avons choisi de ne présenter dans cet exposé que les sujets qui sont indispensables à l'étude de la mathématique et de la physique théorique ainsi que ceux devant faire absolument partie de la culture générale de l'ingénieur.

PRINCIPE DU BON ORDRE

Nous tiendrons pour acquit ce principe qui dit que tout ensemble non vide equation contient un plus petit élément.

Nous pouvons utiliser ce théorème pour démontrer une propriété importante des nombres appelée "propriété archimédienne" ou "axiome d'Archimède" qui s'énonce ainsi:

Pour equationa est non nul, il existe au moins un entier positif n tel que:

equation   (4.1)

En d'autres termes, pour deux grandeurs inégales, il existe toujours un multiple entier de la plus petite, supérieur à la plus grande. Nous appelons "archimédiennes" des structures dont les éléments vérifient une propriété comparable (cf. chapitre de Théorie Des Ensembles).

Même si cela est trivial à comprendre dans le cas des nombres entiers faisons la démonstration car elle permet de voir le type de démarches utilisées par les mathématiciens quand ils doivent démontrer des éléments triviaux de ce genre...

Démonstration:

Supposons le contraire en disant que pour equation nous avons:

  equation   (4.2)

Si nous démontrons que cela est absurde pour tout n alors nous aurons démontré la propriété archimédienne (et ce également si a,b sont réels).

Considérons alors l'ensemble:

equation   (4.3)

En utilisant le principe du bon ordre, nous en déduisons qu'il existe equation tel que equation pour tout equation. Posons donc que ce plus petit élément est: 

equation   (4.4)

et nous avons donc aussi:

equation   (4.5)

Comme par hypothèse equation nous devons alors avoir:

equation   (4.6)

et si nous réarrangeons et simplifions:

equation   (4.7)

et que nous simplifions le signe négatif nous devions donc avoir...:

equation   (4.8)

d'où une contradiction évidente!

Cette contradiction amène que l'hypothèse initiale comme quoi equation pour tout n alors est fausse et donc que la propriété archimédienne est démontrée par l'absurde.

equationC.Q.F.D.

PRINCIPE D'INDUCTION

Soit S un ensemble de nombres naturels qui possède les deux propriétés suivantes:

P1. equation

P2. Si equation, alors equation

Alors:

 equation  (4.9)

Nous construisons ainsi l'ensemble des nombres naturels (se référer au chapitre de Théorie des Ensembles pour voir la construction rigoureuse de l'ensemble des nombres entiers avec les axiomes de Zermelo-Fraenkel).

Soit maintenant:

equation   (4.10)

le symbole " \ " signifiant "excluant". Nous voulons démontrer que:

equation   (4.11)

A nouveau, même si cela est trivial à comprendre faisons la démonstration car elle permet de voir le type de démarches utilisées par les mathématiciens quand ils doivent démontrer des éléments triviaux de ce genre...

Démonstration:

Supposons le contraire, c'est-à-dire:

equation   (4.12)

Par le principe du bon ordre, puisque equation, B doit posséder un plus petit élément que nous noterons equation.

Mais puisque equation de par (P1), nous avons que equation et bien évidemment aussi que equation, c'est-à-dire aussi equation. En faisant appel à (P2), nous avons finalement que equation, c'est-à-dire que equation, donc une contradiction.

equationC.Q.F.D.

exempleExemple: 

Nous souhaitons montrer à l'aide du principe d'induction, que la somme des n premiers carrés est égale à equation, c'est-à-dire que pour equation nous aurions (cf. chapitre de Suites Et Séries):

equation   (4.13)

D'abord la relation ci-dessus est facilement vérifiée pour equation nous allons montrer que equation vérifie aussi cette relation. En vertu de l'hypothèse d'induction:

equation   (4.14)

nous retrouvons bien l'hypothèse de la validité de la première relation mais avec equation, d'où le résultat.

equationC.Q.F.D.

Ce procédé de démonstration est donc d'une très grande importance dans l'étude de l'arithmétique; souvent l'observation et l'induction ont permis de soupçonner des lois qu'il eût été plus difficile de trouver par a priori. Nous nous rendons compte de l'exactitude des formules par la méthode précédente qui a donné naissance à l'algèbre moderne par les études de Fermat et de Pascal sur le triangle de Pascal (voir la section d'Algèbre)

DIVISIBILITÉ

Définition: Soit equation avec equation. Nous disons que "A divise B (sans reste)" s'il existe un entier q (le quotient) tel que: 

equation   (4.15)

auquel cas nous écrivons:

A|B   (4.16)

Dans le cas contraire, nous écrivons equation et nous lisons "A ne divise pas B".

Remarques:

1. Se rappeler que le symbole | est une relation alors que le symbole / est une opération!

2. Il ne faut pas confondre l'expression "A divise B" qui signifie que le reste est obligatoirement nul et "A est le diviseur de la division de B" qui indique que le reste n'est pas forcément nul!

Par ailleurs, si A|B, nous dirons aussi que "B est divisible par A" ou que "B est un multiple de A".

Dans le cas où A|B et que equation, nous dirons que A est un "diviseur propre" de B.

De plus, il est clair que A|0 quel que soit equation sinon quoi nous avons une singularité.

Voici maintenant quelques théorèmes élémentaires se rattachant à la divisibilité:

T1. Si A|B, alors A|BC quel que soit equation

Démonstration:

Si A|B, alors il existe un entier q tel que equation. Alors, equation et ainsi A|BC.

equationC.Q.F.D.

T2. Si A|B et B|C, alors A|C.

Démonstration: 

Si A|B et B|C, alors il existe des entiers q et r tels que equation et equation. Donc, equationet ainsi A|C.

equationC.Q.F.D.

T3. Si A|B et A|C, alors:

equation, equation   (4.17)

Démonstration:

Si A|B et A|C, alors il existe des entiers q et r tels que equation et equation. Il s'ensuit que:

equation   (4.18)

et ainsi que equationequation.

equationC.Q.F.D.

T4. Si A|B et B|A, alors equation

Démonstration:

Si A|B et  B|A, alors il existe des entiers q et r tels que equation et equation. Nous avons donc equation et ainsi equation; c'est pourquoi nous pouvons avoir equation si equation et qu'ainsi equation

equationC.Q.F.D.

T5. Si A|B et equation alors equation

Démonstration:

Si A|B et equation, alors il existe un entier equation tel que equation. Mais alors, equation, puisque equation.

equationC.Q.F.D.

DIVISION EUCLIDIENNE

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 (cf. chapitre Nombres) que tout nombre qui admet exactement les deux diviseurs euclidiens (dont la division donne un reste nul) que sont 1 et lui-même est dit "nombre premier" (ce qui exclut le nombre 1 de la liste des nombres premiers) et que tout couple de nombres qui n'ont que 1 comme diviseur euclidien commun sont dits "premiers entre eux".

Soient 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 relativement 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   (4.27)

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: 

Soient equation, alors il existe des entiers  q et r tels que:

equation   (4.28)

equation. De plus, si equation, alors equation.

Les entiers  q et r sont uniques dans la division euclidienne. En effet, s'il existe deux autres entiers equation et equation tels que:

equation    (4.29)

avec toujours equation, alors:

equation    (4.30)

et ainsi equation. En vertu de (T5) nous avons, si equation, equation.

Or, cette dernière inégalité est impossible puisque par construction 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.31)

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

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

equation
Figure: 4.1 - Diagramme de Venn des diviseurs communs

avec l'ensemble des diviseurs communs suivant:

equation   (4.33)

et donc le PGCD est:

equation   (4.34)

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 premiers 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:

Soient 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.35)

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

Évidemment, 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.36)

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

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

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

constitue l'ensemble de tous les multiples de equation:

Comme d|a et d|b, alors nous avons forcément equation pour tout equation. Soit equation. Notre problème se réduit au fait à montrer queequation.

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

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 (algorithme) qui s'avérera très importante pour calculer (déterminer) le plus grand commun diviseur de deux entiers (utile en informatique parfois).

ALGORITHME D'EUCLIDE

L'algorithme d'Euclide est un algorithme permettant donc 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 vaut 15 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
Figure: 4.2 - Première étape de l'algorithme PGCD

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
Figure: 4.3 - Deuxième étape de l'algorithme PGCD

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 (rectangle 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
Figure: 4.4 - Troisième étape de l'algorithme PGCD

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
Figure: 4.5 - Quatrième étape de l'algorithme PGCD

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 s'il existe. Nous avons alors géométriquement:

equation
Figure: 4.6 - Cinquième étape de l'algorithme PGCD

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

equation
Figure: 4.7 - Sixième et dernière étape de l'algorithme PGCD

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
Figure: 4.8 - Résumé de l'algorithme PGCD

Maintenant, voyons l'approche formelle équivalente:

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

 equation   (4.41)

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é P1:

equation   (4.42)

nous avons:

equation   (4.43)

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

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

 equation   (4.45)

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 (429,966) et exprimons ce nombre comme une combinaison linéaire de 429 et de 966.

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

equation   (4.46)

Nous en déduisons donc que:

 equation   (4.47)

et, de plus, que:

equation   (4.48)

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" ou "premiers entre eux" si:

equation   (4.49)

PLUS PETIT COMMUN MULTIPLE

Définitions:

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

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

equation   (4.50)

le plus petit entier commun multiple positif à 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.51)

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

equation
Figure: 4.9 - Diagramme de Venn des communs multiples

avec l'ensemble des communs multiples suivants:

equation   (4.52)

et le PPCM est alors:

equation   (4.53)

Soit sous une autre forme schématique:

equation
Figure: 4.10 - Exemple schématique du PPCM de 3 et 5

Nous constatons que l'ensemble des multiples communs de 3 et 5 est aussi l'ensemble des multiples de 15.

Remarque: Soient equation. Alors, le plus petit commun multiple existe. En effet, considérons l'ensemble E des entiers naturels m qui pour tout i divisent equation. Ce que nous noterons:

equation   (4.54)

Puisque nous avons forcément 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 quelconque de equation alors equation, c'est-à-dire que m divise chacun des equation.

Démonstration:

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

equation   (4.55)

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

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

equation   (4.57)

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.

tHÉORÈME FONDAMENTAL DE L'ARITHMÉTIQUE

Le théorème fondamental de l'arithmétique dit que tout nombre naturel equation peut s'écrire comme un produit de nombres premiers, et cette représentation est unique, à part l'ordre dans lequel les facteurs premiers sont disposés.

Le théorème établit l'importance des nombres premiers. Essentiellement, ils sont les briques élémentaires de construction des entiers positifs, chaque entier positif contenant des nombres premiers d'une manière unique.

Remarque: Ce théorème est parfois appelé "théorème de factorisation" (un peu à tort... car d'autres théorèmes portent le même nom...).

Démonstration:

Si n est premier, et donc produit d'un unique entier premier, à savoir lui-même le résultat est vrai et la démonstration est terminée (dire qu'un nombre premier est produit de lui-même est bien évidemment un abus de langage!). Supposons que n n'est pas premier et donc strictement supérieur à 1 et considérons l'ensemble:

equation   (4.58)

Alors, equation et , puisque n est composé, nous avons que equation. D'après le principe du bon ordre, D possède un plus petit élément equation qui est premier, sans quoi le choix minimal de equation serait contredit. Nous pouvons donc écrire equation. Si equation est premier, alors la preuve est terminée. Si equation est composé, alors nous répétons le même argument que précédemment et nous en déduisons l'existence d'un nombre premier equation et d'un entier equation tels que equation. En poursuivant ainsi nous arrivons forcément à la conclusion que equation sera premier.

Donc finalement nous avons bien démontré qu'un nombre quelconque est décomposable en facteurs de nombres premiers à l'aide du principe du bon ordre.

equationC.Q.F.D.

Nous ne connaissons pas à ce jour de loi simple qui permette de calculer le n-ième facteur premier equation. Ainsi, pour savoir si un entier m est premier, il est pratiquement plus facile à ce jour de vérifier sa présence dans une table de nombres premiers.

En fait, nous utilisons aujourd'hui la méthode suivante:

Soit un nombre m, si nous voulons déterminer s'il est premier ou non, nous calculons s'il est divisible par les nombres premiers equation qui appartiennent à l'ensemble: 

equation   (4.59)

exempleExemple:

L'entier 223 n'est ni divisible par 2, ni par 3, ni par 5, ni par 7, ni par 11, ni par 13. Il est inutile de continuer avec le prochain nombre premier, car equation. Nous en déduisons dès lors que le nombre 223 est premier.

CONGRUENCES

Définition: Soit equation. Si a et b ont même reste dans la division euclidienne par m nous disons que "a est congru à b modulo m", et nous écrivons:

equation   (4.60)

ou de manière équivalente il existe (au moins) un nombre entier relatif k tel que:

equation   (4.61)

Nous appelons aussi le nombre b "résidu". Ainsi, un résidu est un entier congru à un autre, modulo un
entier m donnée. Le lecteur pourra vérifier que cela impose que:

equation   (4.62)

soit en français.... que m divise la différence entre a et b. Dans le cas contraire, nous disons que "a est non congru à b modulo m".

Une autre manière de dire tout cela si ce n'est pas clair...: L'étude des propriétés qui relient trois nombres entre eux est appelée communément "l'arithmétique modulaire".

Remarques:

R1. Que nous soyons bien d'accord, la congruence implique un reste nul pour la division!

R2. Nous excluons en plus de 0 aussi 1 et -1 pour les valeurs que peut prendre m dans la définition de la congruence dans certains ouvrages.

R3. Derrière le terme de congruence se cachent des notions semblables mais de niveaux d'abstraction différents:

- En arithmétique modulaire, nous disons donc que "deux entiers relatifs a et b sont congrus modulo m s'ils ont même reste dans la division euclidienne par m". Nous pouvons aussi dire qu'ils sont congrus modulo m si leur différence est un multiple de m.

- Dans la mesure des angles orientés, nous disons que "deux mesures sont congrues modulo equation si et seulement si leur différence est un multiple de equation". Cela caractérise deux mesures d'un même angle (cf. chapitre de Trigonométrie).

- En algèbre, nous parlons de congruence modulo I dans un anneau commutatif (cf. chapitre de Théorie Des Ensembles) dont I est un idéal: "x est congru à y modulo I si et seulement si leur différence appartient I". Cette congruence est une relation d'équivalence, compatible avec les opérations d'addition et multiplication et permet de définir un anneau quotient de l'ensemble parent avec son idéal I.

- Nous trouvons parfois, dans l'étude de la géométrie (cf. chapitre de Géométrie Euclidienne) le terme de congru mis à la place de semblable. Il s'agit alors d'une simple relation d'équivalence sur l'ensemble des figures planes.

La relation de congruence equation est une relation d'équivalence (cf. chapitre sur les Opérateurs), en d'autres termes , soient equation alors la relation de congruence est:

P1. Réflexive:

equation   (4.63)

P2. Symétrique:

equation   (4.64)

P3. Transitive:

equation   (4.65)

Démonstration:

Les propriétés P1 et P2 sont évidentes (si ce n'est pas le cas faites-le nous savoir nous développerons!). Nous démontrerons P3. Les hypothèses impliquent que equation. Mais alors:

equation   (4.66)

ce qui montre que a et c sont congrus modulo m.

equationC.Q.F.D.

La relation de congruence equation est compatible avec la somme et le produit (se rappeler que la puissance n'est finalement qu'une extension du produit!).

Effectivement, soient equation tel que equation et equation alors:

P1. equation

P2. equation

Démonstrations:

Nous avons:

equation   (4.67)

par hypothèse. Mais alors:

equation   (4.68)

ce qui démontre P1. Nous avons également:

equation   (4.69)

ce qui démontre P2.

equationC.Q.F.D.

Remarque: La relation de congruence se comporte sur de nombreux points comme la relation d'égalité. Néanmoins une propriété de la relation d'égalité n'est plus vraie pour celle de congruence, à savoir la simplification: si equation, nous n'avons pas nécessairement equation.

exempleExemple:

equation mais equation

Jusqu'ici, nous avons vu des propriétés des congruences faisant intervenir un seul modulus. Nous allons maintenant étudier le comportement de la relation de congruence lors d'un changement de modulus.

P1. Si equation et d|m, alors equation

P2. Si equation et equation alors a et b sont congrus modulo [r,s]

Ces deux propriétés sont évidentes. Inutile d'aller dans les détails pour P1. Pour P2, puisque b-a est un multiple de r et de s puisque par hypothèse:

equation   (4.70)

b-a est donc un multiple du PPCM de r et s, ce qui démontre P2.

De ces propriétés il vient que si nous désignons par f(x) un polynôme à coefficient entiers (positifs ou négatifs):

equation   (4.71)

La congruence equation donnera aussi equation.

Si nous remplaçons x successivement  par tous les nombres entiers dans un polynôme f(x) à coefficients entiers, et si nous prenons les résidus pour le module m, ces résidus se reproduisent  de m en m (dans le sens où la congruence se vérifie), puisque nous avons, quel que soit l'entier m et x:

equation   (4.72)

Nous en déduisons alors l'impossibilité de résoudre la congruence suivante:

equation   (4.73)

en nombres entiers, si r désigne l'un quelconque des non-résidus (un résidu qui ne satisfait pas la congruence).

CLASSES DE CONGRUENCE

Définition: Nous appelons "classe de congruence modulo m", le sous-ensemble de l'ensemble equation défini par la propriété que deux éléments a et b de equation sont dans la même classe si et seulement si equation ou qu'un ensemble d'éléments entre eux sont congrus par ce même modulo.

Remarque: Nous avons vu dans le chapitre traitant des opérateurs qu'il s'agit en fait d'une classe d'équivalence car la congruence modulo m est, comme nous l'avons démontré plus haut, une relation d'équivalence.

exempleExemple:

Soit equation. Nous divisons l'ensemble des entiers en classes de congruence modulo 3. Exemple de trois ensembles dont tous les éléments sont congrus entre eux sans reste (observez bien ce que donne l'ensemble des classes!):

equation   (4.74)

Ainsi, nous voyons que pour chaque couple d'élément d'une classe de congruence, la congruence modulo 3 existe. Cependant, nous voyons que nous ne pouvons pas prendre equation où -9 se trouve dans la première classe et -8 dans la seconde.

Le plus petit nombre non négatif de la première classe est 0, celui de la deuxième est 1 et celui de la dernière est 2. Ainsi, nous noterons ces trois classes respectivement equation, le chiffre 3 en indice indiquant le modulus.

Il est intéressant de noter que si nous prenons un nombre quelconque de la première classe et un nombre quelconque de la deuxième, alors leur somme est toujours dans la deuxième classe. Ceci se généralise et permet de définir une somme sur les classes modulo 3 en posant:

equation   (4.75)

Ainsi que:

equation   (4.76)

Ainsi, pour tout equation, la classe de congruence de:

equation   (4.77)

est l'ensemble des entiers congrus à a modulo m (et congrus entre eux modulo m). Cette classe est notée:

equation   (4.78)

Remarque: Le fait d'avoir mis entre parenthèses l'expression "et congrus entre eux modulo m" est dû au fait que la congruence, étant une relation d'équivalence nous avons comme nous l'avons démontré plus haut que si equation, alors equation.

Définition: L'ensemble des classes de congruence equation (qui forment par le fait que la congruence est une relation d'équivalence des: "classes d'équivalence"), pour un m fixe donne ce que nous appelons un "ensemble quotient" (cf. chapitre Opérateurs). Plus rigoureusement, nous parlons de "l'ensemble quotient de equation par la relation de congruence" dont les éléments sont les classes de congruence (ou: classes d'équivalence) et qui forment alors l'anneau equation.

Nous déduisons de la définition les deux propriétés triviales suivantes:

P1. Le nombre b est dans la classe equation si et seulement si equation

P2. Les classes equation et equation sont égales si et seulement si equation

Montrons maintenant qu'il y a exactement m différentes classes de congruence modulo m, à savoir equation.

Démonstration:

Soit equation, alors tout nombre entier a est congru modulo m à un et un seul entier r de l'ensemble equation (remarquez bien, c'est important, que nous nous restreignons aux entiers positifs ou nuls sans prendre en compte les négatifs!). De plus, cet entier r est exactement le reste de la division de a par m. En d'autres termes, si equation, alors:

equation   (4.79)

si et seulement si equationq est le quotient de a par m et r le reste. La démonstration est donc une conséquence immédiate de la définition de la congruence et de la division euclidienne.

equationC.Q.F.D.

Définition: Un entier b dans une classe de congruence modulo m est appelé "représentant de cette classe" (il est clair que par la relation d'équivalence que deux représentants d'une même classe sont donc congrus entre eux modulo m).

Nous allons pouvoir maintenant définir une addition et une multiplication sur les classes de congruences. Pour définir la somme de deux classes equation, il suffit de prendre un représentant de chaque classe, de faire leur somme et de prendre la classe de congruence du résultat. Ainsi (voir les exemples plus haut):

equation   (4.80)

et de même pour la multiplication:

equation   (4.81)

Par définition de la somme et du produit, nous constatons que la classe de 0 est l'élément neutre pour l'addition:

equation   (4.82)

et la classe de l'entier 1 est l'élément neutre pour la multiplication:

equation   (4.83)

Définition: Un élément equation de equation est "une unité" s'il existe un élément equation tel que equation

Le théorème suivant permet de caractériser les classes modulo m qui sont des unités dans equation:

Théorème: Soit [a] un élément de equation. Alors [a] est une unité si et seulement si equation.

Démonstration:

Supposons d'abord que equation. Alors par Bézout, nous avons son identité:

equation   (4.84)

Autrement dit, as est congru à 1 modulo m. Mais ceci est équivalent à écrire par définition que equation ce qui montre que [a] est une unité. Réciproquement, si [a] est une unité, ceci implique qu'il existe une classe [s] telle que equation.

Ainsi, nous venons de démontrer que equation constitue bien un anneau puisqu'il possède une addition, une multiplication, un élément neutre et un inverse.

equationC.Q.F.D.

SYSTÈME COMPLET DE RÉSIDUS

Considérons le système fini suivant de congruences modulo 6:

equation   (4.85)

où comme le lecteur l'aura remarqué: aucun résidu ne se répète et les résidus pris deux à deux ne sont pas congrus modulo m (c'est ce dernier point qui fait que nous nous arrêtons à 5 dans l'exemple).

Si ces conditions sont satisfaites, nous disons alors que l'ensemble ordonné {6, 13, 2, -3, 22, 11} est un "système complet de résidus modulo m". Un tel ensemble n'est pas unique pour un module donné. Ainsi, l'ensemble {0, 1, 2, 3, 4, 5} est aussi un système complet (trivial) de résidus modulo 6.

Si nous éliminons de ce sytème complet tous les nombres qui ne sont pas premier avec m, nous avons alors un "système réduit de résidus modulo m". Ainsi de la cas ci-dessus, le système réduit de résidus module 6 sera {13, 11}.

Les systèmes réduits nous seront utiles dans le chapitre de Cryptographie pour démontrer un résultat important dans les systèmes asymétriques à clé publique.

Nous verrons aussi dans le chapitre de Cryptographie, que la "fonction indicatrice d'Euler" lorsque m est premier (ce qui n'est pas le cas de l'exemple précédent) donne le cardinal du système réduit de résidus module m comme étant:

equation   (4.86)

Donc sous couvert que m est premier, le système réduit de résidu s'écrira bien évidemment:

equation   (4.87)

THÉORÈME DES RESTES CHINOIS

Le théorème des restes chinois peut être vu comme la résolution d'un système linéaire mais dans un ensemble modulaire. Pour beaucoup d'étudiants et futurs ingénieurs, ce théorème ne servira jamais dans la pratique, mais certains le retrouveront dans le domaine de la cryptographie (dans le cadre du décryptage en particulier).

Il existe comme toujours plusieurs démonstrations possibles mais nous avons opté pour celle qui nous semblait comme toujours la plus pédagogique.

Soient m et n deux entiers premiers entre eux. Le système de congruence:

equation   (4.88)

admet une unique solution.

Démonstration:

Comme m et n sont imposés comme étant premiers entre eux, il existe alors u et v deux entiers relatifs tels que (application de l'identité de Bézout démontrée plus haut):

equation   (4.89)

Nous avons donc:

equation   (4.90)

C'est-à-dire:

equation   (4.91)

Nous avons aussi in extenso:

equation   (4.92)

C'est-à-dire:

equation   (4.93)

Donc afin d'être clair, nous avons donc pour l'instant:

equation   (4.94)

Nous avons donc pour rappel:

equation   (4.95)

Mais nous pouvons aussi écrire avec equation:

equation   (4.96)

Dès lors:

equation   (4.97)

De même, nous avons:

equation   (4.98)

Mais nous pouvons aussi écrire avec equation:

equation   (4.99)

Dès lors:

equation   (4.100)

Donc afin d'être toujours clair, nous avons donc pour l'instant:

equation   (4.101)

Donc, il vient finalement que:

equation   (4.102)

est une solution particulière du système. Mais nous avons aussi pour equation de par la définition de la congruence:

equation   (4.103)

Afin que x soit toujours solution du système, il faut avoir:

equation   (4.104)

et donc:

equation   (4.105)

Dès lors, une solution un peu plus générale est:

equation   (4.106)

mais in extenso, nous avons la solution générale:

equation   (4.107)

avec equation. Nous disons alors parfois que la solution est x modulo nm

FRACTIONS CONTINUES

La notion de fraction continue remonte à l'époque de Fermat et atteint son apogée avec les travaux de Lagrange et Legendre vers la fin du 18ème siècle. Ces fractions sont importantes en physique car nous les retrouvons en acoustique ainsi que dans la démarche intellectuelle qui a amené Galois à créer sa théorie des groupes.

Considérons dans un premier temps le nombre rationnel a/b avec equation avec equation et equation. Nous savons que tous les quotients equation et les restes equation sont dans le cadre de la division euclidienne des entiers positifs.

Rappelons l'algorithme d'Euclide vu plus haut (mais noté de manière un peu différente):

equation   (4.108)

Par substitutions successives, nous obtenons:

equation   (4.109)

Ce qui est aussi parfois noté:

equation   (4.110)

Ainsi, tout nombre rationnel positif peut s'exprimer comme une fraction continue finie où equation.

Exemples:

E1. Cherchons l'expression de 17/49. Nous savons déjà que equation donc que equation. Nous avons alors:

equation   (4.111)

Nous voyons bien dans cet exemple que nous avons effectivement equation. Nous pouvons également remarquer que par construction:

equation   (4.112)

où les crochets représentent la partie entière et nous avons aussi:

equation   (4.113)

E2. Voyons comment extraire la racine carrée d'un nombre A par la méthode des fractions continues.

Soit a le plus grand nombre entier dont le carré equation est plus petit que A. On le soustrait de A. Il y a donc un reste de:

equation   (4.114)

où nous avons utilisé une des identités remarquables vues dans le chapitre d'Algèbre. D'où en divisant les deux membres par la deuxième parenthèse, nous avons:

equation   (4.115)

Soit:

equation   (4.116)

Dans le dénominateur, nous remplaçons equation par:

equation   (4.117)

Cela donne:

equation   (4.118)

etc.... on voit ainsi que le système est simple pour déterminer l'expression d'une racine en termes de fraction continue.

Le développement du nombre a/b s'appelle le "développement du nombre a/b en fraction continue finie" et est condensé sous la notation suivante:

equation   (4.119)

Nous considérerons comme intuitif que tout nombre rationnel peut s'exprimer comme fraction continue finie et inversement que toute fraction continue finie représente un nombre rationnel. Par extension, un nombre irrationnel est représenté par une fraction continue infinie!

Considérons maintenant equation une fraction continue finie. La fraction continue:

equation   (4.120)

equation est appelée la "k-ième réduite" ou la "k-ième convergente" ou encore le "k-ième quotient partiel".

Avec cette notation, nous avons:

equation   (4.121)

Pour simplifier les expressions ci-dessus, nous introduisons les suites equation (n pour numérateur et d pour dénominateur) définies par:

equation   (4.122)

à l'aide de cette construction, nous avons une petite inégalité immédiate intéressante pour un peu plus loin:

equation   (4.123)

Avec la définition ci-dessus, nous constatons que:

equation   (4.124)

Soit en généralisant:

equation   (4.125)

Maintenant, montrons pour un usage ultérieur que pour equation, nous avons:

equation   (4.126)

Le résultat est immédiat pour equation. En supposant que le résultat est vrai pour i montrons qu'il est aussi vrai pour equation. Puisque:

equation   (4.127)

alors en utilisant l'hypothèse d'induction, nous obtenons le résultat!

Nous pouvons maintenant établir une relation indispensable pour la suite. Montrons que si equation est la k-ième réduite de la fraction continue simple finie equation alors:

equation   (4.128)

Démonstration:

equation   (4.129)

puisque:

equation   (4.130)

donc:

equation   (4.131)

ce qui nous indique que le signe equation est le même que celui de equation.

Il en résulte que equation pour k impair, et que equation pour k pair. Il s'ensuit que:

equation et equation   (4.132)

Ensuite, puisque:

equation   (4.133)

Donc pour k pair, nous avons equation, nous en déduisons donc:

equation   (4.134)

equationC.Q.F.D.

Montrons maintenant que toute fraction continue infinie peut représenter un nombre irrationnel quelconque.

En des termes formels, si equation est une suite d'entiers tous positifs et que nous considérons equation alors celui-ci converge nécessairement vers un nombre réel si equation.

Effectivement il n'est pas difficile d'observer (c'est assez intuitif) avec un exemple pratique que nous avons:

equation   (4.135)

lorsque equation.

Maintenant, notons x un nombre réel quelconque et equation la partie entière de ce nombre réel. Alors nous avons vu tout au début de notre étude des fractions continues que:

equation   (4.136)

Il vient donc que:

equation   (4.137)

Attardons-nous pour les nécessités du chapitre d'Acoustique sur le calcul d'une fraction continue d'un logarithme en utilisant la relation précédente!

D'abord rappelons que:

equation   (4.138)

Soit (relation démontrée dans le chapitre d'Analyse Fonctionnelle):

equation   (4.139)

avec equation et equation.

Soit equation défini par:

equation   (4.140)

Alors montrons que:

equation   (4.141)

En effet, pour equation nous avons:

equation   (4.142)

pour equation nous avons d'abord:

equation   (4.143)

donc:

equation   (4.144)

et puisque nous avions montré que:

equation   (4.145)

etc... par récurrence ce qui démontre notre droit d'utiliser ce changement d'écriture.

exempleExemple:

Cherchons l'expression de la fraction continue de:

equation   (4.146)

Nous savons en jouant avec la définition du logarithme que:

equation   (4.147)

donc:

equation   (4.148)

donc equation. Nous avons alors:

equation   (4.149)

et puisque:

equation   (4.150)

il vient:

equation   (4.151)

Donc nous avons le premier quotient partiel:

equation   (4.152)

Et in extenso nous avons déjà:

equation   (4.153)

Simplifions:

equation   (4.154)

Donc le premier quotient partiel peut s'écrire:

equation   (4.155)

et passons au deuxième quotient partiel. Nous savons déjà pour cela que:

equation   (4.156)

donc il est immédiat que equation et alors comme:

equation   (4.157)

nous avons:

equation   (4.158)

Il vient finalement:

equation   (4.159)

etc... etc.

En Savoir Plus

- Introduction à la théorie des Nombres, Éditions Modulo, J.-M. De Koninck + A. Mercier,
ISBN10: 2891135008 (254 pages) - Imprimé en 1954 (disponible ici sur Amazon EU Sàrl


Haut de page

OPÉRATEURSTHÉORIE DES ENSEMBLES


Like8   Dislike0
65.93% sur 100%
Notée par 27 visiteur(s)
12345
Commentaires: [0] 
 
 


W3C - HTMLW3C - CSS Firefox
Ce travail est dans le domaine public
2002-2017 Sciences.ch

Haut de page