Corrigé de l'exercice 81, page 70 - Transmath 3e

⭐ À savoir pour bien répondre :

A) Diviseur d’un nombre entier

Un entier naturel \(d\) est un diviseur d’un entier naturel \(a\) si la division de \(a\) par \(d\) donne un reste nul.

On écrit alors : « \(d\) divise \(a\) » ou \(d \mid a\).

Par exemple, pour \(a = 12\) : les diviseurs sont \(1, 2, 3, 4, 6, 12\) car :

\[12 \div 1 = 12\] \[\;12 \div 2 = 6\] \[\;12 \div 3 = 4\] \[\;12 \div 4 = 3\] \[\;12 \div 6 = 2\] \[\;12 \div 12 = 1\]

Dans chaque cas, le reste est nul, donc les entiers testés sont bien des diviseurs.

B) Nombre premier

Un entier naturel \(n \geq 2\) est appelé nombre premier s’il possède exactement deux diviseurs positifs : \(1\) et lui-même.

Exemples :

– 7 est premier : ses seuls diviseurs sont 1 et 7.

– 12 n’est pas premier car il a plus de deux diviseurs : 1, 2, 3, 4, 6, 12.

C) Décomposition en produit de facteurs premiers

Tout nombre entier \(n \geq 2\) peut s’écrire de manière unique (à l’ordre près) comme un produit de nombres premiers, par exemple :

\[60 = 2 \times 30\] \[\;= 2^2 \times 15\] \[\;= 2^2 \times 3 \times 5\]

On dit que la décomposition en facteurs premiers de 60 est \(2^2 \times 3 \times 5\).

D) Nombre de diviseurs à partir de la décomposition

Si un entier s’écrit sous la forme :

\[n = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k}\]

(où les \(p_i\) sont des nombres premiers et les \(a_i\) des entiers \(\geq 1\)), alors le nombre total de diviseurs positifs de \(n\) est :

\[(a_1 + 1) \times (a_2 + 1) \times \dots \times (a_k + 1)\]

Exemple : pour \(60 = 2^2 \times 3^1 \times 5^1\), on obtient :

\[(2+1) \times (1+1) \times (1+1) = 3 \times 2 \times 2\] \[\;= 12\]

Donc 60 possède 12 diviseurs.

E) Reste d’une division euclidienne et « modulo »

La division euclidienne de \(a\) par \(d\) consiste à écrire :

\[a = d \times q + r\]

où \(q\) est le quotient et \(r\) le reste, avec \(0 \leq r < d\).

On note souvent « \(a\) modulo \(d\) » le reste de cette division. Par exemple :

\[17 \text{ modulo } 5 = 2\]

car :

\[17 = 3 \times 5 + 2\]

Si « \(a\) modulo \(d = 0\) », cela signifie que le reste est nul, donc que \(d\) est un diviseur de \(a\).

F) Idée d’un algorithme pour compter les diviseurs

Pour compter le nombre de diviseurs d’un entier \(a\), on peut :

1. Faire parcourir à une variable \(d\) tous les entiers de 1 à \(a\).

2. À chaque valeur de \(d\), vérifier si \(a\) est divisible par \(d\) (par exemple en regardant si « \(a\) modulo \(d = 0\) »).

3. Si c’est le cas, on ajoute 1 à un compteur.

À la fin, le compteur contient le nombre de diviseurs de \(a\).