4. DIVISIBILITÉ



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

Définition: Soit equation avec equation. Nous disons que "A divise B (sans restes)" 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 est "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.


page suivante : 4.1. Division euclidienne