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



THÉORIES DES NOMBRES

1. Principe du bon ordre

2. Propriété archimédienne

3. Principe d'induction

4. Divisibilité

4.1. Division euclidienne

4.1.1. Plus grand commun diviseur

4.1.2. Algorithme d'euclide

4.1.3. Plus petit commun multiple

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

4.3. Congruences

4.3.1. Classes de congruence

4.4. Fractions continues

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, alors la preuve est terminée. Supposons que n n'est pas premier et considérons l'ensemble:

equation   (4.62)

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

exempleExemple:

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

4.3. CONRUENCES

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

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

equation   (4.65)

Le lecteur pourra vérifier que cela impose que

equation   (4.66)

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 de ces 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.67)

P2. Symétrique :

equation   (4.68)

P3. Transitive :

equation   (4.69)

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

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

par hypothèse. Mais alors :

equation   (4.72)

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

equation   (4.73)

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

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

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

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

equation   (4.77)

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

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 le première classe et -8 dans le 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.79)

Ainsi que :

equation   (4.80)

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

equation   (4.81)

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

equation   (4.82)

Remarque: Le fait d'avoir mis entre parenthèse l'expression "et congrus entre eux modulo m" est du 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 congruences equation (qui forment par le fait que la congruence est une relation d'équivalence des : "classes d'équivalences"), 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 congruences (ou : classes d'équivalences) 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.83)

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 est dans une classe de congruence modulo m est appelé "représentant de cette classe" (il est claire 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.84)

et de même pour la multiplication :

equation   (4.85)

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

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

equation   (4.87)

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

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.


page suivante : 4.4. Fractions continues