Divisibilité

Cours maths Terminale S

Divisibilité :

Dans ce module d’introduction à l’arithmétique, retour sur les notions connues depuis le collège que sont la division euclidienne, les nombres premiers et la décomposition d’un nombre en produit de facteurs premiers.

► Sommaire cours maths Terminale S

A voir aussi :

► Sommaire par thèmes
► Sommaire par notions

Avertissement :
L’arithmétique concerne le raisonnement sur les entiers
qu’ils soient naturels ou relatifs.

Cependant, certaines propriétés et certaines notions
ne sont valables que pour des entiers naturels,

c’est pourquoi il faudra être toujours très vigilant tout au long de ce chapitre
et bien regarder quel est l’ensemble dans lequel on travaille.

1/ Divisibilité : définition(s)
Divisibilité dans

:
Soient a et b deux entiers naturels.

* On dit que a divise b s’il existe un entier naturel k tel que : b = a x k. On note a \ b
* On dit également que b est un multiple de a ou que a est un diviseur de b.

Propriété : ordre et divisibilité.
Soient a et b deux entiers naturels : si a divise b et b

0 alors a < b

De même, on définit :
Divisibilité dans

:
Soient a et b deux entiers relatifs.

* On dit que a divise b s’il existe un entier relatif k tel que : b = a x k . On note a \ b

* On dit également que b est un multiple de a ou que a est un diviseur de b.

Remarque : si b n’est pas un multiple de a alors a ne divise pas b.

Exemples :

► 6 = 2 x 3
Donc : 2 \6 et 3 \ 6 6 = (-1) x (-6)
Donc (-1) \ 6 et (-6) \ 6

Si on note D₆ l’ensemble des diviseurs entiers de 6 :

D₆ = -6 ; -3 ; -2 ; -1 ; 1 ; 2 ; 3 ; 6

► -5 = (-1) x 5 Donc : 5 \ (-5) et pourtant attention : 5 > -5.

1/ Divisibilité : division euclidienne dans

Division euclidienne dans

Soient a

et b

^*
Il existe un unique couple ( q , r ) d’entiers naturels tels que :
a = b x q + r avec 0 < r < b

q est le quotient, r le reste, b le diviseur et a le dividende.

Propriété :
« b divise a » si et seulement si « le reste de la division euclidienne de a par b est nul ».

Remarque :
Nous n’abordons pas dans ce module le cas de la division euclidienne dans .
Cette notion sera travaillée en détail et sera le sujet d’exercices dans le module sur le pgcd.
Dans ce module-ci, nous nous contenterons d’utiliser la propriété pour montrer qu’un nombre n’en divise pas un autre.

1/ Divisibilité : rappel des critères
Divisibilité dans :
Soit n
► n est divisible par 2 si et seulement si : son dernier chiffre est 0, 2, 4, 6 ou 8

On dit alors que n est pair.
Dans le cas contraire, il est dit impair.

► n est divisible par 3 si et seulement si : la somme de ses chiffres est divisible par 3.

Remarque :
Ne pas hésiter à répéter l’application de ce critère à la somme trouvée s’il est difficile de savoir si cette somme est elle-même divisible par 3.

Exemple :
9876977 est-il divisible par 3 ?

9+8+7+6+9+7+7 = 53
5+3=8 qui n’est pas divisible par 3

Donc : 9876977 n’est pas divisible par 3.

► n est divisible par 4 si et seulement si : le nombre formé par ses deux derniers chiffres est divisible par 4.
► n est divisible par 5 si et seulement si : son dernier chiffre est 0 ou 5.

► n est divisible par 9 si et seulement si : la somme de ses chiffres est divisible par 9.
La technique des sommes successives vue avec 3 pouvant être utilisée également pour 9.

► n est divisible par 10 si et seulement si : son dernier chiffre est 0.

► n est divisible par 11 si et seulement si : il s’agit d’un nombre à deux chiffres dont les deux chiffres sont égaux.
Ou s’il s’agit d’un nombre à trois chiffres dont le chiffre des dizaines est égal à la somme du chiffre des centaines et du chiffre des unités. (à condition que cette somme ne dépasse pas 9)

A ces critères, se rajoute évidemment la connaissance des tables de multiplication.

2/ Divisibilité : résultats de référence

Démonstration du 6° :
Soit a entier naturel tel que a \ 1.
D’après la propriété sur l’ordre : a < 1 donc a = 0 ou a = 1.

Or 0 ne divise pas 1 donc a = 1.

Soit a entier relatif tel que a \ 1. Alors, il existe k entier relatif tel que : a = 1 x k

D’où : avec _lk_l
donc au sens de la divisibilité dans.
Par conséquent : et donc a = 1 ou a = -1.

3/ Divisibilité : propriétés
Transitivité :
Si a \ b et b \ c alors a \ c.

Si c\a et c\b alors c\u x a + v x b quels que soient u et v entiers relatifs.
On dit que c divise toute combinaison linéaire de a et de b à coeficients entiers.
En particulier : c\a + b et c\a - b
Cette propriété peut évidemment être adaptée aux entiers naturels et à la division dans

4/ Nombres premiers : définition

Définition :
Soit p

On dit que p est un nombre premier ou plus simplement qu’il est premier si :
il admet exactement 2 diviseurs entiers naturels distincts.

Diviseurs qui sont 1 et lui-même.
( puisque 1 divise tout nombre et tout nombre est diviseur de lui-même. )

Remarques :
1) La notion de nombre premier ne concerne que les entiers naturels.
Il est donc ici question de divisibilité dans

.
2) 0 a une infinité de diviseurs donc il n’est pas premier.
3) 1 n’a qu’un seul diviseur, qui est lui-même donc 1 n’est pas premier.
4) 2 a exactement 2 diviseurs : 1 et 2 donc 2 est le plus petit des nombres premiers.
5) L’ensemble des nombres premiers est noté :

6) Si n ≠ 1 n’est pas premier alors il possède au moins un diviseur autre que 1 et lui-même.

5/ Nombres premiers : théorèmes

Les nombres premiers constituent un des grands domaines de recherche en mathématiques.

A ce jour, il n’existe toujours pas de critère ou de formule qui permette instantanément de dire si un nombre quelconque est premier.

Prenons un entier naturel n différent de 1,et cherchons s’il est premier.

Si nous trouvons un entier naturel p, différent de 1 et de n, qui divise n alors par définition,
n n’est pas premier.

Or si ( p divise n ) et ( p différent de n ), alors ( p

Il suffit donc de partir de 2 et de tester tous les entiers jusqu’à (n -1)

Mais, prenons par exemple n = 247,
est-il vraiment nécessaire de tester tous les entiers de 2 à 246
jusqu’à ce que l’on trouve ou non un diviseur de 247 ?

Un premier théorème va nous aider à affiner notre stratégie :

Théorème n°1 : Soit n
Si n ≠ 1 alors n admet au moins un diviseur premier.

Démonstration :

Cas n°1 : n = 0
2 divise 0 donc 0 admet au moins un diviseur premier.

Cas n°2 : n ≠ 0
a ) si n est premier, ce diviseur est lui-même et la propriété est démontrée.
b ) si n n’est pas premier, n possède au moins un diviseur différent de 1 et de lui-même.

D, ensemble des diviseurs de n autres que 1 et n n’est donc pas vide.

D étant un sous ensemble non vide de , il possède un plus petit élément que nous noterons p.
p n’est pas nul car 0 ne divise que 0 et n est différent de 0.

Montrons par l’absurde que p est premier :

Si p n’est pas premier, en tenant le même raisonnement que pour n, nous pouvons affirmer qu’il possède un diviseur k autre que 1 et lui-même.

Or k \ p et p ≠ 0 donc k < p
mais k ≠ p donc k < p

De plus : p \ n non nul et p ≠ n donc p < n
D’où : k < n et donc : k ≠ n

Or : k \ p et p \ n donc k \ n.
Par conséquent : k D.
Donc D possède un élément strictement inférieur à p.

Ce qui est incompatible avec la définition de p. Donc p ne peut pas « ne pas être premier ».

Conclusion : n admet dans tous les cas un diviseur premier.

Conséquence de ce théorème au niveau de notre stratégie :
De 2 à (n -1) inclus nous n’allons donc tester que les nombres premiers.

en effet :

* Si on trouve que l’un de ces nombres premiers divise n alors n n’est pas premier.
* Si aucun de ces nombres ne divise n, n peut-il ne pas être premier ?
Autrement dit, est-il possible qu’il existe entre 2 et ( n -1) un diviseur non premier de n ?

Supposons qu’un tel nombre existe et appelons-le d.
Comme d > 1, d possède au moins un diviseur premier : p

p \ d et d \ n donc p \ n.
De plus : p \ d et d est non nul et non premier donc : p < d.
Et d \ n avec n non nul donc d < n.

D’où : 1< p

Il existerait alors un nombre premier entre 2 et ( n – 1 ) qui divise n.
Ce qui est contraire à l’hypothèse, donc n est premier.

Nous en sommes donc à la stratégie suivante :

Tester tous les nombres premiers de 2 à (n-1) inclus.

Avec comme méthode de discrimination :
♦ Si un de ces nombres divise n alors n n’est pas premier.
♦ Sinon n est premier.

Mais, tester tous les nombres premiers de 2 à (n-1) reste fastidieux.
Heureusement, un autre théorème va alléger nos efforts :

Théorème n°2 : Soit n avec n > 2
Si n n’est pas premier alors n admet au moins un diviseur premier p tel que :

Il nous suffit donc maintenant de tester les nombres premiers inférieurs ou égaux à

En effet :

* Si on trouve que l’un de ces nombres premiers divise n alors n n’est pas premier.

→ Si aucun de ces nombres ne divise n, n peut-il ne pas être premier ?
- Non car d’après le théorème n° 2, il admettrait alors au moins un diviseur premier inférieur ou égal à, ce qui est contraire à l’hypothèse.
Donc n est premier

D’où la version finale de la méthode de discrimination d’un nombre premier :

Tester dans l’ordre croissant les nombres premiers inférieurs ou égaux

Si l’un d’eux divise n alors n n’est pas premier.
Sinon, n est premier.

Cette méthode étant souvent énoncée comme un théorème :

Théorème n°3 ( contraposée du théorème n° 2 ) :
Si n n’est divisible par aucun nombre premier inférieur ou égal à alors n est premier.

Cependant, il demeure un problème de taille :
Pour appliquer cette méthode, nous avons besoin de la liste des nombres premiers inférieurs ou égaux à

Cette liste peut être obtenue entre autre grâce à la méthode du crible d’Eratosthène.

Quant à la liste complète des nombres premiers, c’est l’objet de notre quatrième théorème :

Théorème n°4 :
L’ensembledes nombres premiers est infini.

En voici la démonstration par l’absurde :
Supposons que

est fini et donc égal à p₁ ; p₂ ; ... ; p_n
* Soit a le nombre défini par : a = p₁ x p₂ x ... x p_n + 1
a ≠ 1 donc a admet au moins un diviseur premier, appelons-le p_k

p_k\ a et p_k \ p₁ x p₂ x... x p_n donc pk\a - p₁ x p₂ x... x p_n
d’où p_k\1 Or le seul diviseur entier naturel de 1 est 1 donc p_k = 1
Ce qui est impossible car 1 n’est pas un nombre premier.

Conclusion : l’ensemble des nombres premiers est infini.

6/ Application de la méthode de discrimination

Si nous reprenons notre exemple : « 247 est-il premier ? » ,

Nous avons besoin de la liste des nombres premier inférieurs ou égaux à

Or : ≈ 15,7 donc il nous faut la liste des nombres premiers inférieurs ou égaux à 15.
Qui est : 2, 3, 5, 7, 11, 13.

On utilise alors les critères de divisibilité :

247 ne se termine pas par 0, 2, 4, 6 ou 8 donc 2 ne le divise pas.
2+4+7=11 et 3 ne divise pas 11 donc 3 ne divise pas 247.
247 ne se termine pas par 0 ou 5 donc 5 ne le divise pas.
2 + 7= 9 ≠ 4 donc 11 ne divise pas 247

247 / 13 = 19 d’où 247 = 13 x 19 ; 13 divise 247
donc 247 n’est pas premier

7/ Décomposition d’un entier en produit de facteurs premiers

Nous avons vu que si n > 2 alors il possède au moins un diviseur premier p₁

Il existe alors q₁ entier naturel non nul tel que : n = p₁ x q₁
Et q₁divisant n non nul, q₁< n car p₁ ≠ 1

Si q₁≠ 1 alors il possède à son tour au moins un diviseur premier p₂ ( qui peut être égal à p₁).

Il existe alors q₂entier naturel non nul tel que : q₁ = p₂ x q₂
Et q₂divisant q₁ non nul, q₂ < q₁ car p₂ ≠ 1

On construit ainsi une suite (q_n) qui est strictement décroissante et minorée par 1.
Cette suite s’arrête donc « forcément » or elle ne peut s’arrêter que si l’un de ses termes vaut 1.

D’où : n = p₁ x q₁= p₁ x (p₂x q₂) = ... = p₁ x p₂ x p₃ ...x (p_k x 1)

Et en écrivant les produits de nombres premiers égaux entre eux sous forme de puissance, on obtient donc le théorème suivant :

Théorème n° 5 :
Tout entier n > 2 se décompose de façon unique sous la forme :

Où : p₁ , p₂ , ... p_m sont des nombres premiers tels que : p₁ < p₂ < ... < p_m
et ₁ , ₂, ... , _m sont des entiers naturels non nuls.

L’écriture de n sous cette forme est appelée décomposition de n en produit de facteurs premiers.

Remarques :
1) Ce théorème peut être montré de façon rigoureuse à l’aide d’un raisonnement par récurrence.
2) L’ordre strict imposé sur les facteurs sert à garantir l’unicité de la décomposition.
3) Quel que soit i : _i ≠ 0 donc quel que soit i : p_i \ n

De plus, il ne peut exister de nombre premier p différent des p_iqui divise n
car sinon la décomposition ne serait pas unique.

Conclusion : l’ensemble des diviseurs premiers de n est p₁ , p₂ , ... p_m

Exemple de décomposition : technique et présentation.
Décomposons n = 72.

Méthode :
Il faut appliquer à 72 la même méthode que si l’on cherchait à savoir s’il est premier.
C’est à dire qu’il faut tester si les nombres premiers inférieurs ou égaux à sa racine, le divisent.
* Si on lui trouve un diviseur, il faut alors continuer à appliquer cette méthode au quotient de 72 par ce diviseur. Et ainsi de suite, jusqu’à obtention d’un quotient égal à 1.

2 divise 72 et 72/2 = 36.
Attention à bien repartir de 2 ! 2 divise 36 et 36/2 = 18

2 divise 18 et 18/2 = 9

2 ne divise pas 9
* Il ne sera donc plus nécessaire de tester 2 à l’avenir.
* Car par transitivité, si 2 ne divise pas un nombre,
* il ne peut pas non plus diviser ses diviseurs.

Passons au nombre premier suivant : 3 divise 9 et 9/3 = 3
3 divise 3 et 3/3 = 1.
Fin de la décomposition.

Conclusion : 72 x 2³ x 3²

8/ Recherche des diviseurs d’un entier naturel

Soit n dont la décomposition en facteurs premiers est :
Si a ≠ 1 et a divise n, montrons que sa décomposition ne peut contenir de nombre premier autre que les p_i

Démonstration :
Supposons qu’il existe p premier différent des p_i qui divise a.
p\a donc p\n
Et p fait alors partie de l’ensemble des diviseurs premiers de n.
Ce qui est impossible car l’ensemble des diviseurs premiers de n se limite aux p_i

La décomposition de tout diviseur de n ne peut donc contenir que des nombres premiers égaux aux p_i

De plus, _i l’exposant de p_i dans la décomposition de a ne peut être strictement supérieur à _i car par transitivité diviserait n, qui possèderait alors une décomposition en facteurs premiers dans laquelle l’exposant de p_i serait différent de _i

Ce qui est impossible par unicité de la décomposition de n.

D’où le théorème suivant :

Si la décomposition en facteurs premiers de n est :
Alors, tout diviseur a de n s’écrit :
avec pour tout i compris entre 1 et m :

Remarques :
1) si _{i =}₀ alors p_i n’est pas un diviseur premier de a.
2) si tous les _i sont nuls alors a = 1 et si pour tout i : _{i =}_i alors a = n
3) par multiplication des choix possibles de puissances pour chaque diviseur premier, on obtient que :

Le nombre de diviseurs de n est : (₁ +1) x (₂ + 1) x ... x (_m +1)

Exemple : reprenons 72. 72 = 2³ x 3²
Le plus simple et le plus clair au niveau présentation pour trouver tous les diviseurs de 72 est de faire un arbre de choix comme en probabilités.

divisibilité ; arbre de choix comme en probabilités.

3+1
=
4 choix
pour l’exposant de 2
multipliés par
2+1
=
3 choix
pour l’exposant de 3

Il y a donc
12 choix possibles

72 a donc 12 diviseurs
dont la liste est ci-contre.

Cours complémentaires :

► Pgcd
► Ppcm
► Congruences
► Equations diophantiennes

► Sommaire cours maths Terminale S

A voir aussi :

► Sommaire par thèmes
► Sommaire par notions