Comment déterminer les diviseurs d'un entier et établir des critères de divisibilité ? | MetMat

Comment déterminer les diviseurs d'un entier et établir des critères de divisibilité ?

En testant les entiers de $1$ à $\lfloor\sqrt{n}\rfloor$ : si $d$ divise $n$ , alors $n/d$ aussi

Lister tous les diviseurs positifs d'un entier $n$ .

L'objectif

Lister tous les diviseurs positifs d'un entier $n$ .

Le principe

Les diviseurs de $n$ vont par paires $(d, n/d)$ avec $d \leq \sqrt{n}$ , donc il suffit de tester les entiers jusqu'à $\lfloor\sqrt{n}\rfloor$ .

La méthode

1
Calculer $\lfloor\sqrt{n}\rfloor$ pour déterminer la borne de recherche.
2
Pour chaque entier $d$ de $1$ à $\lfloor\sqrt{n}\rfloor$ , tester si $d \mid n$ (i.e. si $n \bmod d = 0$ ).
3
Si $d \mid n$ , ajouter $d$ et $n/d$ à la liste des diviseurs (si $d \neq n/d$ , sinon ajouter $d$ une seule fois).

Pour comprendre, fais des exercices !

0/5 validés

Exercice d'exemple

Diviseurs de $12$

Étape 1 —

Calculer

\lfloor\sqrt{n}\rfloor

pour déterminer la borne de recherche.

$\lfloor\sqrt{12}\rfloor = 3$ , donc on teste $d \in \{1, 2, 3\}$ .

Étape 2 —

Pour chaque entier

d

1

\lfloor\sqrt{n}\rfloor

, tester si

d \mid n

(i.e. si

n \bmod d = 0

$1 \mid 12$ (oui), $2 \mid 12$ (oui), $3 \mid 12$ (oui).

Étape 3 —

d \mid n

, ajouter

d

n/d

à la liste des diviseurs (si

d \neq n/d

, sinon ajouter

d

une seule fois).

Paires : $(1, 12)$ , $(2, 6)$ , $(3, 4)$ . Diviseurs : $\{1, 2, 3, 4, 6, 12\}$ .

Application guidée

Diviseurs de $36$

Application autonome 1

Diviseurs de $30$

Application autonome 2

Diviseurs de $49$

Application autonome 3

Diviseurs de $100$ .

Crée ton compte gratuit pour accéder à la fiche et aux exercices