2. PRINCIPE D'INDUCTION



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

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és par les mathématiciens quand ils doivent démontrer des éléments triviaux de ce type...

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)


page suivante : 4. Divisibilité