recevoir les news :: signaler une erreur :: statistiques visiteurs :: imprimer

THEORIE DE LA DEMONSTRATION | NOMBRES | OPERATEURS | THEORIE DES NOMBRES | THEORIE DES ENSEMBLES | PROBABILITES ET STATISTIQUES |

La théorie des nombres est un sujet très vaste qui englobe de nombreuses parties des mathématiques dont les probabilités, la statistique, la théorie des graphes, la théorie des ensembles, l'algèbre (d'une certaine façon) et encore bien d'autres...

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 partie de la culture générale du scientifique.

PRINCIPE DU BON ORDRE

Nous tiendrons acquis ce principe qui s'énonce ainsi :

Tout ensemble non vide  contient un plus petit élément.

LA DIVISIBILITE

Soit  avec . Nous disons que "divise (sans restes)" s'il existe un entier (le quotient) tel que : 

auquel cas nous écrivons : . 

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

Remarque : si , nous dirons aussi que " est divisible par " ou que " est un multiple de ". Dans le cas où  et que , nous dirons que est un "diviseur propre" de . De plus, il est clair que  quel que soit  sinon quoi nous avons une singularité. Enfin, nous écrira  pour signifier que mais que .

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

T1. Si , alors  quel que soit

Démonstration: 

Si , alors il existe un entier tel que . Alors, et ainsi .

T2. Si  et , alors

Démonstration: 

Si  et , alors il existe des entiers et tels que et . Donc, et ainsi .

T3. Si  et , alors ,

Démonstration: 

Si  et , alors il existe des entiers et tels que et . Il s'ensuit que:

et ainsi que

T4. Si  et , alors

Démonstration: 

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

T5. Si  et , alors il existe un entier  alors

Démonstration: 

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

DIVISION EUCLIDIENNE

Soit  avec ; alors, il existe des entiers  et tels que , où . De plus, si , alors .

Démonstration : 

Considérons l'ensemble:

Il est facile de voir que  et donc que , d'où, d'après le principe du bon ordre, nous concluons que contient un plus petit élément . Soit l'entier satisfaisant à . Il reste à montrer que . Supposons le contraire à nouveau (démonstration par l'absurde), c'est-à-dire que . Alors, dans ce cas, nous avons , ce qui est équivalent à ; mais  et , ce qui contredit le fait que  est le plus petit élément de . Donc, . Enfin, il est clair que si , nous avons , d'où la seconde affirmation du théorème.

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

où

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

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

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

PLUS GRAND COMMUN DIVISEUR

Soit  tels que . Le "plus grand commun diviseur" (noté "p.g.c.d" par la suite) de , noté :

est l'entier positif  qui satisfait aux deux propriétés suivantes :

P1.  et

P2. si  et  alors  (par définition)

Remarque: notons que 1 est un diviseur commun de deux entiers arbitraires. Cependant, il n'est pas évident que le p.g.c.d de deux entiers  existe toujours; ce fait est démontré dans le théorème suivant (cependant, si le p.g.c.d existe, il est de par sa définition unique) :

Soit  tels que . Alors, il existe des entiers  tels que:

Démonstration:

Considérons l'ensemble . Comme  et , nous pouvons utiliser le principe du bon ordre et conclure que possède un plus petit élément . Nous pouvons alors écrire  pour un certain choix . Il suffit de montrer que . Pour cela, il faut montrer que satisfait aux propriétés (P1) et (P2) de la définition du p.g.c.d. 

Commençons par la première: 

Supposons que . Alors, d'après la division euclidienne, il existe  tels que , où . Mais alors:

et donc  et , ce qui contredit le fait que est le plus petit élément possible de . Donc,  et, de la même façon, nous démontrons que .

Corollaire: 

Soit tels que . Alors:

constitue l'ensemble de tous les multiples de .

Démonstration: 

Comme  et , alors nous supposons  pour tout . Soit . Nous voulons montrer que . Soit d'abord  ce qui signifie que et qui implique . Supposons maintenant également qu'il existe un , cela voudrait donc dire que  pour un certain . Comme  pour un choix d'entiers quelconques , alors:

Ainsi se termine la démonstration. Les hypothèses peuvent vous 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 p.g.c.d de deux entiers non nuls, nous permettons à l'un d'entre eux d'être égal à 0, disons , ? Dans ce cas, nous avons  et , selon notre définition du p.g.c.d, il est clair que .

Propriétés : Soit  et soit , alors:

P1.

P2.  où

P3.

P4. Si  tel que  et  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 un démonstration en elle-même.

Elaborons maintenant un 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

Soit , où . En appliquant successivement la division euclidienne, nous obtenons la suite d'équations:

Si , alors . Par suite, les entiers  satisfaisant à

Démonstration: 

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

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:

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

En continuant ce processus, nous arrivons à exprimer  comme un combinaison linéaire de .

Exemple:

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

Solution : nous appliquons bien évidemment l'algorithme d'Euclide: 

Nous en déduisons donc que :

et, de plus, que:

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

PLUS PETIT COMMUN MULTIPLE

Définition: soit . Nous disons que est un "commun multiple de  si  pour . Le "plus petit commun multiple" (p.p.c.m) de , noté : 

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

Remarque : soit ; alors, le plus petit commun multiple existe. En effet, considérons l'ensemble:

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

Théorèmes :

T1. Si est un commun multiple de  alors

Démonstration: 

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

Il suffit de montrer que . Supposons  (démonstration par l'absurde). Puisque  et , alors on a  et cela pour . Donc, est un commun multiple de  plus petit que le p.p.c.m. On vient d'obtenir une contradiction, ce qui prouve la première partie.

T2. Si , alors

La démonstration est évidente.

T3.

Démonstration:

Pour la démonstration, nous allons utiliser le "lemme d'Euclide" qui s'énonce ainsi :

Si et  alors .

Démonstration :

Nous avons vu qu'il existe  tels que  et alors . Mais et 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  et . En tout premier lieu, considérons le cas où . L'entier  étant un multiple de , nous pouvons écrire . Ainsi, nous avons  et, puisque , il s'ensuit, d'après le lemme d'Euclide, que . Donc,  et alors . Mais est un commun positif de  et qui ne peut être plus petit que le p.p.c.m; c'est pourquoi .

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

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

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

theoreme fondamental de l'arithmétique

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.

Si est premier, alors la preuve est terminée. Supposons que n'est pas premier et considérons l'ensemble:

Alors,  et , puisque est composé, nous avons que . D'après le principe du bon ordre, 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.

Nous ne connaissons pas à ce jour de loi qui permette de calculer le -ième facteur premier . Ainsi, pour savoir si un entier 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 , 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 : 

Exemple: L'entier 223 n'est 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.

NOMBRES CONGRUS

Définition: soit . Nous disons que " est congru à modulo ", et nous écrivons :

si ; dans le cas contraire, nous disons que " est non congru à modulo ".

D'autre part, nous pouvons étendre la signification du mot "reste" en disant que deux nombres congrus pour le module sont "résidus" l'un de l'autre pour ce module. 

L'égalité entre deux nombres, en supprimant les multiples du module, s'appelle "congruence" ou "équivalence". La notation de Gauss permet de mettre en évidence l'analogie qui existe entre les égalités et les congruences, sans introduire de confusion.

Nous avons les propriétés suivantes:

P1. Nous pouvons peut ajouter ou retrancher membre à membre des congruences de même module.

P2. Nous pouvons multiplier les deux membres d'une congruence par un même nombre entier.

P3. Nous pouvons multiplier membre à membre les congruences de même module.

P4. Nous pouvons élever à une même puissance les deux membres d'une congruence.

Des ces propriétés il vient que si nous désignons par un polynôme à coefficient entiers, positifs ou négatifs:

La congruence  donnera aussi

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

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

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

PREUVE PAR NEUF

La "preuve par 9" dans le système de numérotation décimale, pour les quatre opérations fondamentales de l'arithmétique (+, - , x, / ), repose sur les théorèmes que nous venons de voir sur les congruences, en supposant . 

En effet, suivant le module , toutes les puissances de dix sont congrues à l'unité, puisque , étant un nombre formé exclusivement des chiffres 9999…., est divisible par 9. Par conséquent, si  désignent respectivement les chiffres des unités, dizaines, centaines, … d'un nombre écrit dans le système décimal, nous avons :

et, par suite de par les propriétés de la congruence:

En d'autres termes, le reste de la division d'un nombre par 9 est égal au reste de la division par 9, de la somme de ses chiffres.

Par conséquent, si l'on remplace, dans les quatre opérations fondamentales de l'arithmétique, les nombres donnés par leurs restes suivant le module 9, les nombres obtenus doivent êtres congrus à ceux qu'on déduirait des résultats; sinon il y aurait erreur dans les calculs.