News :: Erreur :: Visiteurs :: ClearType :: Imprimer ::

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

Dernière mise à jour de ce chapitre: 2015-09-15 08:59:01 | {oUUID 1.703}
Version:3.1 Révision 3 | Rédacteur: Vincent ISOZ  | Avancement: ~90%
vues depuis le 2012-01-01: 5'989

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.

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  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 où a est non nul, il existe au moins un entier positif n tel que:

  (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  nous avons:

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

  (4.3)

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

  (4.4)

et nous avons donc aussi:

  (4.5)

Comme par hypothèse nous devons alors avoir:

  (4.6)

et si nous réarrangeons et simplifions:

  (4.7)

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

  (4.8)

d'où une contradiction évidente!

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

C.Q.F.D.

PRINCIPE D'INDUCTION

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

P1.

P2. Si , alors

Alors:

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

  (4.10)

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

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

  (4.12)

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

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

C.Q.F.D.

Exemple: 

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

  (4.13)

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

  (4.14)

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

C.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  avec . Nous disons que "A divise B (sans reste)" s'il existe un entier q (le quotient) tel que: 

  (4.15)

auquel cas nous écrivons:

A|B   (4.16)

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

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 , nous dirons que A est un "diviseur propre" de B.

De plus, il est clair que A|0 quel que soit  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

Démonstration:

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

C.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 et . Donc, et ainsi A|C.

C.Q.F.D.

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

,   (4.17)

Démonstration:

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

  (4.18)

et ainsi que .

C.Q.F.D.

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

Démonstration:

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

C.Q.F.D.

T5. Si A|B et  alors

Démonstration:

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

C.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  avec . Le "théorème de la division euclidienne" affirme qu'il existe des entiers uniques  q et r tels que:

  (4.19)

où . De plus, si , alors .

Démonstration:

Considérons l'ensemble:

  (4.20)

Il est relativement facile de voir que  et que , d'où, d'après le principe du bon ordre, nous concluons que S contient un plus petit élément .

Soit q l'entier satisfaisant donc à:

  (4.21)

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

  (4.22)

ce qui est équivalent à:

  (4.23)

mais  et:

  (4.24)

ce qui contredit le fait que:

    (4.25)

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

C.Q.F.D.

Remarque: Dans l'énoncé de la division euclidienne, nous avons supposé que . Qu'obtenons-nous lorsque ? 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:

où   (4.26)

Or, cette relation peut s'écrire:

  (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 , alors il existe des entiers  q et r tels que:

  (4.28)

où . De plus, si , alors .

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

    (4.29)

avec toujours , alors:

    (4.30)

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

Or, cette dernière inégalité est impossible puisque par construction . Donc,  et, puisque , alors d'où l'unicité.

PLUS GRAND COMMUN DIVISEUR

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

    (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 et c|d (par définition!)

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

Exemple:

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.

  (4.32)

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

Figure: 4.1 - Diagramme de Venn des diviseurs communs

avec l'ensemble des diviseurs communs suivant:

  (4.33)

et donc le PGCD est:

  (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   tels que . 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:

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

  (4.36)

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

  (4.37)  

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

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

  (4.38)

Ainsi, nous avons que  et , 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 tels que , alors:

  (4.39)

constitue l'ensemble de tous les multiples de :

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

Soit d'abord  ce qui signifie que d|s et qui implique .

Soit un , cela voudrait donc dire que  pour un certain .

Comme  pour un choix d'entiers quelconques , alors:

  (4.40)

C.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: , . Dans ce cas, nous avons a|b et , selon notre définition du PGCD, il est clair que .

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

P1.

P2.  où

P3.

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

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.

Exemple:

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:

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

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:

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:

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:

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

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:

Figure: 4.8 - Résumé de l'algorithme PGCD

Maintenant, voyons l'approche formelle équivalente:

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

    (4.41)

Si , alors .

Sinon de manière plus formelle:

Démonstration:

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

  (4.42)

nous avons:

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

  (4.44)

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

    (4.45)

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

C.Q.F.D.

Exemple:

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: 

  (4.46)

Nous en déduisons donc que:

    (4.47)

et, de plus, que:

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

  (4.49)

PLUS PETIT COMMUN MULTIPLE

Définitions:

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

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

  (4.50)

le plus petit entier commun multiple positif à tous les communs multiples de .

Exemple:

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:

  (4.51)

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

Figure: 4.9 - Diagramme de Venn des communs multiples

avec l'ensemble des communs multiples suivants:

  (4.52)

et le PPCM est alors:

  (4.53)

Soit sous une autre forme schématique:

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 . Alors, le plus petit commun multiple existe. En effet, considérons l'ensemble E des entiers naturels m qui pour tout i divisent . Ce que nous noterons:

  (4.54)

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

Démonstration:

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

  (4.55)

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

C.Q.F.D.

T2. Si , alors

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

T3.

Démonstration:

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

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

Revenons à notre théorème:

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

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

    (4.56)

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

  (4.57)

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

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

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:

  (4.58)

Alors,  et , puisque n est composé, nous avons que . D'après le principe du bon ordre, D possède un plus petit élément  qui est premier, sans quoi le choix minimal de  serait contredit. Nous pouvons donc écrire . Si  est premier, alors la preuve est terminée. Si  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  et d'un entier  tels que . En poursuivant ainsi nous arrivons forcément à la conclusion que  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.

C.Q.F.D.

Nous ne connaissons pas à ce jour de loi simple qui permette de calculer le n-ième facteur premier . 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 qui appartiennent à l'ensemble: 

  (4.59)

Exemple:

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 . Nous en déduisons dès lors que le nombre 223 est premier.

CONGRUENCES

Définition: Soit . 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:

  (4.60)

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

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

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

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

P1. Réflexive:

  (4.63)

P2. Symétrique:

  (4.64)

P3. Transitive:

  (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 . Mais alors:

  (4.66)

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

C.Q.F.D.

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

Effectivement, soient tel que et alors:

P1.

P2.

Démonstrations:

Nous avons:

  (4.67)

par hypothèse. Mais alors:

  (4.68)

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

  (4.69)

ce qui démontre P2.

C.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 , nous n'avons pas nécessairement .

Exemple:

mais

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 et d|m, alors

P2. Si et 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:

  (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):

  (4.71)

La congruence  donnera aussi .

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:

  (4.72)

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

  (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 défini par la propriété que deux éléments a et b de sont dans la même classe si et seulement si ou qu'un ensemble d'éléments entre eux sont congrus par ce même modulo.

Exemple:

Soit . 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!):

  (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 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 , 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:

  (4.75)

Ainsi que:

  (4.76)

Ainsi, pour tout , la classe de congruence de:

  (4.77)

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

  (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 , alors .

Définition: L'ensemble des classes de congruence (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 par la relation de congruence" dont les éléments sont les classes de congruence (ou: classes d'équivalence) et qui forment alors l'anneau .

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

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

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

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

Démonstration:

Soit , alors tout nombre entier a est congru modulo m à un et un seul entier r de l'ensemble (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 , alors:

  (4.79)

si et seulement si où q 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.

C.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 , 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):

  (4.80)

et de même pour la multiplication:

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

  (4.82)

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

  (4.83)

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

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

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

Démonstration:

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

  (4.84)

Autrement dit, as est congru à 1 modulo m. Mais ceci est équivalent à écrire par définition que 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 .

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

C.Q.F.D.

SYSTÈME COMPLET DE RÉSIDUS

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

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

  (4.86)

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

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

  (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):

  (4.89)

Nous avons donc:

  (4.90)

C'est-à-dire:

  (4.91)

Nous avons aussi in extenso:

  (4.92)

C'est-à-dire:

  (4.93)

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

  (4.94)

Nous avons donc pour rappel:

  (4.95)

Mais nous pouvons aussi écrire avec :

  (4.96)

Dès lors:

  (4.97)

De même, nous avons:

  (4.98)

Mais nous pouvons aussi écrire avec :

  (4.99)

Dès lors:

  (4.100)

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

  (4.101)

Donc, il vient finalement que:

  (4.102)

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

  (4.103)

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

  (4.104)

et donc:

  (4.105)

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

  (4.106)

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

  (4.107)

avec . 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  avec  et . Nous savons que tous les quotients  et les restes  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):

  (4.108)

Par substitutions successives, nous obtenons:

  (4.109)

Ce qui est aussi parfois noté:

  (4.110)

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

Exemples:

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

  (4.111)

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

  (4.112)

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

  (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é  est plus petit que A. On le soustrait de A. Il y a donc un reste de:

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

  (4.115)

Soit:

  (4.116)

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

  (4.117)

Cela donne:

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

  (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  une fraction continue finie. La fraction continue:

  (4.120)

où  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:

  (4.121)

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

  (4.122)

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

  (4.123)

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

  (4.124)

Soit en généralisant:

  (4.125)

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

  (4.126)

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

  (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  est la k-ième réduite de la fraction continue simple finie  alors:

  (4.128)

Démonstration:

  (4.129)

puisque:

  (4.130)

donc:

  (4.131)

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

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

 et   (4.132)

Ensuite, puisque:

  (4.133)

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

  (4.134)

C.Q.F.D.

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

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

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

  (4.135)

lorsque .

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

  (4.136)

Il vient donc que:

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

  (4.138)

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

  (4.139)

avec  et .

Soit  défini par:

  (4.140)

Alors montrons que:

  (4.141)

En effet, pour  nous avons:

  (4.142)

pour  nous avons d'abord:

  (4.143)

donc:

  (4.144)

et puisque nous avions montré que:

  (4.145)

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

Exemple:

Cherchons l'expression de la fraction continue de:

  (4.146)

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

  (4.147)

donc:

  (4.148)

donc . Nous avons alors:

  (4.149)

et puisque:

  (4.150)

il vient:

  (4.151)

Donc nous avons le premier quotient partiel:

  (4.152)

Et in extenso nous avons déjà:

  (4.153)

Simplifions:

  (4.154)

Donc le premier quotient partiel peut s'écrire:

  (4.155)

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

  (4.156)

donc il est immédiat que  et alors comme:

  (4.157)

nous avons:

  (4.158)

Il vient finalement:

  (4.159)

etc... etc.

- 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

7   0

Notée par 22 visiteur(s) 12345 PageRater 0.5.0 Commentaires: [0]