Division euclidienne et nombres premiers

Prérequis :

cours de 6^e sur la division euclidienne et la divisibilité
cours de 5^e sur les fractions

Introduction :

En sixième, nous avons appris à effectuer des divisions euclidiennes. Nous avons ensuite défini les notions de multiple et diviseur d’un nombre entier.
Dans ce cours, nous allons apprendre à dresser la liste des diviseurs d’un nombre entier. Puis nous découvrirons les nombres premiers, qui sont au centre de la recherche, en informatique notamment. Enfin, nous verrons comment nous en servir pour simplifier des fractions.

Divisibilité d’un nombre entier

Division euclidienne, multiple et diviseur

Commençons par rappeler les définitions de la division euclidienne, d’un multiple et d’un diviseur.

Définition

Division euclidienne :

On considère deux nombres entiers positifs $a$ et $b$, avec $b$ non nul.
Effectuer la division euclidienne de $\textcolor{#0066CC}a$ par $\textcolor{#009900}b$ revient à trouver deux nombres entiers $\textcolor{#B5739D}q$ et $\textcolor{#FF8000}r$ tel que :

$\textcolor{#0066CC}a=\textcolor{#009900}b\times \textcolor{#B5739D}q+\textcolor{#FF8000}r$, avec $r < b$

$Division euclidienne de a par b$ Division euclidienne de a par b

$\textcolor{#0066CC}a$ est appelé dividende, $\textcolor{#009900}b$ diviseur, $\textcolor{#B5739D}q$ quotient et $\textcolor{#FF8000}r$ reste.

On utilise souvent la division euclidienne quand on veut effectuer un partage équitable :

$q$ donne le nombre de groupes de $b$ éléments que l’on peut faire avec $a$ éléments ;
parfois, la seule façon de faire ce partage équitable est de laisser de côté un certain nombre d’éléments, il s’agit alors du reste $r$.

Et, lorsque $r$ est nul, c’est-à-dire que le partage peut se faire équitablement sans « perte », on parle de multiple et de diviseur.

Définition

Multiple et diviseur :

Dans la division euclidienne d’un nombre entier $a$ par un nombre entier $b$ non nul, si le reste $r$ est nul, on a : $a = b \times q$. On dit alors, indifféremment, que :

$a$ est un multiple de $b$ ;
$a$ est divisible par $b$ ;
$b$ est un diviseur de $a$ (on peut faire $q$ groupes de $b$ éléments avec un reste nul) ;
$b$ divise $a$.

Remarque : Si, en outre, $q$ est non nul, alors $q$ est aussi un diviseur de $a$ (on peut faire $b$ groupes de $q$ éléments avec un reste nul).

Astuce

Quel que soit le nombre entier $b$, nous avons $0=b\times 0$.

$0$ est un multiple de tout nombre entier. Autrement dit, tout nombre entier est un diviseur de $0$.
Mais $0$ ne divise aucun nombre entier non nul, puisque la division par $0$ est impossible.

À retenir

Précisons aussi que tout nombre entier strictement supérieur à $1$ admet au moins deux diviseurs : $1$ et lui-même.

Par exemple, si je possède $20$ chocolats que je veux partager équitablement sans qu’il en reste :

je peux être égoïste et faire $1$ paquet de $20$ chocolats, que je garde pour moi ;
je peux au contraire vouloir partager avec un maximum de personnes et faire $20$ paquets de $1$ chocolat.
Ainsi, $1$ et $20$ sont des diviseurs de $20$.

Rappelons enfin les critères de divisibilité qu’il faut absolument connaître, car ils nous seront utiles pour établir qu’un nombre est multiple d’un autre, trouver un diviseur…

À retenir

Un nombre est divisible par $2$ si son chiffre des unités est $0$, $2$, $4$, $6$ ou $8$.
Un nombre est divisible par $3$ si la somme de ses chiffres est divisible par $3$.
Un nombre est divisible par $4$ si ses deux derniers chiffres sont divisibles par $4$.
Un nombre est divisible par $5$ si son chiffre des unités est $0$ ou $5$.
Un nombre est divisible par $9$ si la somme de ses chiffres est divisible par $9$.
Un nombre est divisible par $10$ si son chiffre des unités est $0$.

Définition

Nombre pair, nombre impair :

Un nombre entier divisible par $2$ est dit pair.
Un nombre entier qui n’est pas pair est dit impair.

Illustrons par un petit exercice ces notions de divisibilité, de multiple et de diviseur.

Exemple

Parmi les entiers $52$, $131$ et $260$, lesquels sont des multiples de $13$ ?

On peut effectuer la division euclidienne des trois nombres par $13$ et voir si le reste est nul.

S’il l’est, alors le nombre est un multiple de $13$. Sinon, ce n’est pas un multiple de $13$.

Mais on peut le faire « de tête ». Nous détaillons ci-dessous les opérations, mais elles sont faisables sans écritures.

On calcule rapidement que $13\times 2=26$, puis que $26\times 2=52$. Donc :

$$52=26\times 2=(13\times 2)\times 2=13\times (2\times 2)=13\times 4$$

$52$ est un multiple de $13$ (et aussi de $4$).
Ensuite, on sait que : $13\times 10=130$.
On voit ainsi que le reste sera égal à $1$ : $131=13\times 10+1$.
$131$ n’est pas un multiple de $13$.
Enfin, on vient de le voir : $13\times 10=130$, et on calcule aussi facilement : $130\times 2=260$. D’où :

$$260=130\times 2=(13\times 10)\times 2=13\times (10\times 2)=13\times 20$$

$260$ est un multiple de $13$ (et aussi de $20$).
En conclusion, on peut dire que $52$ et $260$ sont des multiples de $13$, mais pas $131$.

Dresser la liste des diviseurs d’un nombre entier

Dans certains exercices, résoudre le problème reviendra à trouver tous les diviseurs d’un nombre.

À retenir

Méthode : Comment dresser la liste des diviseurs d’un nombre entier

On considère un nombre entier $a > 1$.

On sait déjà que $1$ et $a$ sont des diviseurs de $a$. On les met dans la liste.
On teste alors la divisibilité de $a$ par $2$, puis $3$, $4$, etc., par ordre croissant, en se servant des tables de multiplication, des critères de divisibilité, en trouvant des astuces de calcul mental, ou en posant la division euclidienne si besoin.
Lorsque $b$ divise $a$, le quotient $q$ de $a$ par $b$ divise aussi $a$. On ajoute $b$ et $q$ à la liste des diviseurs.
On continue jusqu’à ce qu’on retrouve, par symétrie, les mêmes diviseurs (ou qu’on atteigne $a$).

Pour bien comprendre cette méthode, appliquons-la sur un exemple.

Exemple

Nous souhaitons dresser la liste complète des diviseurs de $24$.

$\green 1$ et $\green {24}$ sont des diviseurs de $24$.
$24$ a $4$ pour chiffre des unités, il est donc divisible par $2$, avec : $24=2\times 12$.
$\green 2$ et $\green {12}$ sont des diviseurs de $24$.
$2+4=6$ est divisible par $3$, donc $24$ est divisible par $3$, avec : $24=3\times 8$.
$\green 3$ et $\green 8$ sont des diviseurs de $24$.
$24$ fait partie de la table de $4$, il est donc divisible par $4$, avec : $24=4\times 6$.
$\green 4$ et $\green 6$ sont des diviseurs de $24$.
$24$ n’est pas divisible par $5$.
Nous arrivons à $6$, dont nous avons déjà dit que c’est un diviseur de $24$.
Nous arrêtons.
Nous pouvons maintenant donner la liste complète des diviseurs de $24$, que nous rangeons par ordre croissant :

$$1\ ;\, 2\ ;\, 3\ ;\, 4\ ;\, 6\ ;\, 8\ ;\, 12\ ;\, 24$$

Résolvons maintenant un problème, assez typique de ce que vous rencontrerez.

Exemple

Un garçon de café doit répartir $24$ croissants et $36$ pains au chocolat dans des corbeilles. Chaque corbeille doit avoir le même contenu, et il ne doit rester ni croissants ni pains au chocolat après la répartition. Quelles sont les répartitions possibles ?

Tout d’abord, il s’agit de bien comprendre l’énoncé.

D’une part, le garçon de café a $24$ croissants, et il ne doit pas en rester après la répartition dans les corbeilles. Il faut donc que le nombre de corbeilles soit un diviseur de $24$.
D’autre part, il a $36$ pains au chocolat. Comme pour les croissants, pour qu’il ne reste pas de pains au chocolat à la fin, il faut que le nombre de corbeilles soit un diviseur de $36$.

Il s’agit donc de lister tous les diviseurs de $24$, puis de $36$, et de ne garder que ceux qu’ils ont en commun. Nous obtiendrons ainsi les nombres de corbeilles possibles et, par suite, les répartitions possibles de croissants et pains au chocolat.
Nous avons trouvé les diviseurs de $24$ dans l’exemple précédent :

$$1\ ;\, 2\ ;\, 3\ ;\, 4\ ;\, 6\ ;\, 8\ ;\, 12\ ;\, 24$$

Déterminons maintenant l’ensemble des diviseurs de $36$, en utilisant la méthode utilisée pour $24$.
$\green 1$ et $\green {36}$ sont des diviseurs de $36$.
$36$ a $6$ pour chiffre des unités, il est donc divisible par $2$, avec : $36=2\times 18$.
$\green 2$ et $\green {18}$ sont des diviseurs de $36$.
$3+6=9$ est divisible par $3$, donc $36$ est divisible par $3$, avec : $36=3\times 12$.
$\green 3$ et $\green {12}$ sont des diviseurs de $36$.
$36$ fait partie de la table de $4$, il est donc divisible par $4$, avec : $36=4\times 9$.
$\green 4$ et $\green 9$ sont des diviseurs de $36$.
$36$ n’est pas divisible par $5$.
$36$ fait partie de la table de $6$, il est donc divisible par $6$, avec : $36=6\times 6$.
$\green 6$ est un diviseur de $36$.
On sait que, par symétrie, on a trouvé l’ensemble des diviseurs de $36$ :

$$1\ ;\, 2\ ;\, 3\ ;\, 4\ ;\, 6\ ;\, 9\ ;\, \, 12\ ;\, 18\ ;\, 36$$

Identifions maintenant les diviseurs communs :

$$\begin{aligned} \textcolor{#A9A9A9}{\text{Diviseurs de $24$\ :\ }} &\purple 1\ ;\, \purple 2\ ;\, \purple 3\ ;\, \purple 4\ ;\, \purple 6\ ;\, 8\ ;\, \purple {12}\ ;\, 24 \\ \textcolor{#A9A9A9}{\text{Diviseurs de $36$\ :\ }} &\purple 1\ ;\, \purple 2\ ;\, \purple 3\ ;\, \purple 4\ ;\, \purple 6\ ;\, 9\ ;\, \, \purple {12}\ ;\, 18\ ;\, 36 \end{aligned}$$

Les quantités de corbeilles possibles sont donc : $1\ ;\, 2\ ;\, 3\ ;\, 4\ ;\, 6\ ;\, 12$.
Nous pouvons maintenant donner les répartitions possibles, c’est-à-dire le nombre de croissants et de pains au chocolat par corbeille en fonction du nombre de corbeilles.
Ce sera tout simplement égal aux quotients de $24$ et $36$ par le nombre de corbeilles considéré. Nous les avons indiqués lors de la recherche des diviseurs, nous mettons les résultats dans un tableau.

Nombre de corbeilles	$1$	$2$	$3$	$4$	$6$	$12$
Nombre de croissants	$24$	$12$	$8$	$6$	$4$	$2$
Nombre de pains au chocolat	$36$	$18$	$12$	$9$	$6$	$3$

Nombres premiers

Définition

Nous avons dit plus haut qu’un nombre entier (strictement supérieur à $1$) admet au moins deux diviseurs : $1$ et lui-même. Et certains nombres n’en admettent pas d’autres. Ces nombres remarquables sont appelés nombres premiers.

Définition

Nombre premier :

Un nombre premier est un entier positif qui admet exactement deux diviseurs : $1$ et lui-même.

À retenir

$0$ n’est pas un nombre premier, car tous les nombres entiers sont des diviseurs de $0$.
$1$ n’est pas non plus un nombre premier, car il n’admet qu’un seul diviseur.
$2$ est un nombre premier, car il admet bien $2$ diviseurs exactement : $1$ et lui-même.
C’est le seul nombre pair premier, puisque tout autre nombre pair admet par définition $2$ comme diviseur, en plus de $1$ et lui-même.

Exemple

$13$ est un nombre premier, car il n’admet comme diviseur que $1$ et $13$.
$368$ n’est pas un nombre premier, car il est aussi divisible, par exemple, par $2$.
$837$ n’est pas non plus un nombre premier, car il est aussi divisible, par exemple, par $3$ ($8+3+7=18$ est un multiple de $3$).

Astuce

Pour montrer qu’un nombre n’est pas premier, il suffit de lui trouver un diviseur différent de $1$ et de lui-même.

À retenir

Il est important de connaître le début de la liste des nombres premiers. Nous donnons ici ceux qui sont inférieurs à $30$ :

$2$	$3$	$5$	$7$	$11$
$13$	$17$	$19$	$23$	$29$

Décomposition en facteurs premiers

Nous allons maintenant voir une propriété fondamentale en arithmétique.

Propriété

Tout nombre entier strictement supérieur à $1$ peut être décomposé en produit de facteurs premiers, c’est-à-dire qu’il peut s’écrire sous la forme d’un produit de nombres premiers.

Cette décomposition est unique, à l’ordre des facteurs près.

À retenir

Méthode : Comment décomposer un nombre en produit de facteurs premiers

on écrit le nombre sous la forme d’un produit de deux entiers ;
et on fait pareil avec les facteurs obtenus qui ne sont pas des nombres premiers, jusqu’à ne plus avoir que des facteurs premiers.

Exemple

$6=2\times 3$, où $2$ et $3$ sont des nombres premiers.
$12=2\times 6=2\times 3\times 3$, où $2$ et $3$ sont des nombres premiers.
$60=2\times 30=2\times 2\times 15=2\times 2\times 3\times 5$, où $2$, $3$ et $5$ sont des nombres premiers.

Il existe une méthode générale pour décomposer un nombre en produit de facteurs premiers, que l’on va expliquer à travers un exemple.

On cherche à décomposer en produit de facteurs premiers le nombre $308$, qui n’est pas premier, puisqu’il est pair.
Pour déterminer sa décomposition, on va tester sa divisibilité par les nombres premiers de manière croissante, en utilisant les critères de divisibilité et la liste des nombres premiers.

On commence par tester la divisibilité de $308$ par $2$.
$308$ est un nombre pair, il est donc divisible par $2$.
$\textcolor{#0066CC}{308} \div \textcolor{#009900}2=\textcolor{#B5739D}{154}$.

$308 est divisible par 2$ 308 est divisible par 2

On teste ensuite si le quotient obtenu, $154$, est aussi divisible par $2$.
$154$ est un nombre pair, il est donc divisible par $2$.
$\textcolor{#0066CC}{154} \div \textcolor{#009900}2=\textcolor{#B5739D}{77}$.

$154 est divisible par 2$ 154 est divisible par 2

On regarde encore si le quotient obtenu est divisible par $2$.
$77$ est un nombre impair, il n’est pas divisible par $2$.
On passe alors au nombre premier immédiatement supérieur, soit $3$.
$7+7=14$, qui n’est pas un multiple de $3$ ; $77$ n’est donc pas divisible par $3$.
On passe au nombre premier immédiatement supérieur, soit $5$.
$77$ n’est bien sûr pas divisible par $5$, son chiffre des unités étant différent de $0$ et $5$.
On passe de nouveau au nombre premier immédiatement supérieur, soit $7$.
$77$ est visiblement divisible par $7$.
$\textcolor{#0066CC}{77} \div \textcolor{#009900}7=\textcolor{#B5739D}{11}$.

$77 est divisible par 7$ 77 est divisible par 7

$11$ fait partie des nombres premiers à connaître, son seul diviseur supérieur ou égal à $7$ est donc lui-même.
$\textcolor{#0066CC}{11} \div \textcolor{#009900}{11}=\textcolor{#B5739D}{1}$.

$11 est un nombre premier, divisible par 1 et lui-même$ 11 est un nombre premier, divisible par 1 et lui-même

On s’arrête quand on obtient un quotient égal à $1$.
Les facteurs de la décomposition de $308$ sont alors les nombres premiers de la colonne de droite :

$$\boxed{308=2\times 2\times 7\times 11}$$

Simplification de fractions

La décomposition en facteurs premiers peut être utile pour simplifier une fraction.

À retenir

Méthode : Comment simplifier une fraction grâce à la décomposition en facteurs premiers

On applique la méthode du paragraphe précédent pour décomposer en produits de facteurs premiers le numérateur et le dénominateur.
On peut alors simplifier par les facteurs premiers que le numérateur et le dénominateur ont en commun.
S’ils n’ont aucun facteur premier commun, alors on ne peut pas davantage simplifier la fraction.
S’ils sont plusieurs facteurs premiers en commun, on peut aussi simplifier par leur produit.

Exemple

Nous cherchons à simplifier la fraction $\frac {308}{231}$.

Décomposons $308$ et $231$ en facteurs premiers.
Nous l’avons déjà fait pour $308$ :

$$308=2\times 2\times 7\times 11$$

Utilisons la même méthode pour décomposer $231$ :

$Décomposition en produit de facteurs premiers de 231$ Décomposition en produit de facteurs premiers de 231

La décomposition en facteurs premiers de $231$ est donc :

$$231=3\times 7\times 11$$

Nous obtenons ainsi :

$$\dfrac{308}{231}=\dfrac {2\times 2\times 7\times 11}{3\times 7\times 11}$$

Le tableau suivant donne l’ensemble des simplifications possibles :

$$\footnotesize \dfrac {308}{231}=\dfrac {2\times 2\times \green{\cancel 7}\times 11}{3\times \green{\cancel 7}\times 11}$$	Simplification par $7$	$$\footnotesize \dfrac {308}{231}=\dfrac{2\times 2\times 11}{3\times 11}=\dfrac {44}{33}$$
$$\footnotesize \dfrac{308}{231}=\dfrac {2\times 2\times 7\times \green{\cancel{11}}}{3\times 7\times \green{\cancel{11}}}$$	Simplification par $11$	$$\footnotesize \dfrac{308}{231}=\dfrac { 2\times 2\times 7}{3\times 7}=\dfrac{28}{21}$$
$$\footnotesize \dfrac {308}{231}=\dfrac {2\times 2\times \green{\cancel 7}\times \green{\cancel{11}}}{3\times \green{\cancel 7}\times \green{\cancel{11}}}$$	Simplification par $7\times 11$	$$\footnotesize \dfrac {308}{231}=\dfrac{2\times 2}{3}=\dfrac {4}{3}$$

Pour cette dernière égalité de fractions, nous nous rendons compte qu’il n’y a plus de facteurs premiers communs après simplification.

Nous ne pouvons pas davantage simplifier la fraction $\frac 43$.

Conclusion :

Dans ce cours, nous avons vu comment résoudre des problèmes en utilisant la divisibilité de nombres entiers.
Surtout, nous avons défini ces nombres fascinants que sont les nombres premiers, puis avons donné la propriété de décomposition unique d’un nombre en facteurs premiers.

Si la définition d’un nombre premier est simple, il devient difficile, pour des entiers très grands, de montrer s’ils sont premiers ou non, tant les tests de divisibilité à faire sont nombreux. C’est d’ailleurs pour cela que les nombres premiers et leurs produits sont utilisés pour sécuriser l’échange de données sur Internet, par exemple quand quelqu’un y effectue un paiement par carte bancaire…

Cours : Division euclidienne et nombres premiers

Divisibilité d’un nombre entier

Division euclidienne, multiple et diviseur

Dresser la liste des diviseurs d’un nombre entier

Nombres premiers

Définition

Décomposition en facteurs premiers

Simplification de fractions