Critères usuels et moins usuels de divisibilité

Comme le titre l’indique, cet article traite des principales règles de divisibilité : certaines sont très classiques – on les rencontre dès le début du collège (parfois même un peu plus tôt); d’autres le sont nettement moins.

Si vous pensez maîtriser suffisamment les pré-requis (pour l’essentiel : notions de divisibilité et de congruence modulo un entier, écriture dans une base de numération donnée), alors je vous invite à vous rendre directement à la section 4. Et sinon, pas de panique, car j’ai prévu de reprendre toutes ces notions à zéro 🙂

1 – Diviseurs et multiples, vite fait

Avant toute chose, je vous propose de revisiter le B-A-BA concernant les notions de diviseurs et de multiples d’un nombre entier.

Vous connaissez probablement tout ça, mais c’est juste pour être sûr …

Définition

Etant donnés deux nombres entiers $n$ et $d$ :

$n$ est dit multiple de $d$ lorsqu’il existe un entier $k$ tel que $k\times d=n.$

Les trois affirmations :

$n$ est un multiple de $d$
$d$ est un diviseur de $n$
$d$ divise $n$

expriment une seule et même propriété, que l’on note $\boxed{d\mid n}$ .

Dans le cas contraire, on note $\boxed{d\nmid n}$

Dans la définition ci-dessus, on insiste sur le caractère entier de $k$ : si l’on autorisait pour $k$ n’importe quelle valeur réelle, la notion perdrait tout intérêt. On peut, en effet, toujours écrire des égalités du type $3=\frac{3}{4}\times4$ mais il ne faudrait pas en déduire que $3$ est multiple de $4$ …

Exemples

$8\mid1\thinspace000$ puisque $125\times8=1\thinspace000.$
$37\mid-111$ puisque $\left(-3\right)\times37=-111.$

En revanche : $7\nmid20$ car $2\times7=14,$ trop petit … et $3\times7=21,$ trop grand … !

On observera que :

0 ne divise aucun entier hormis lui-même
1 et -1 sont des diviseurs de tout entier

Par ailleurs, on prouve aisément les propriétés suivantes :

Tout entier $n$ vérifie $n\mid n.$
Si deux entiers $m,n$ vérifient $m\mid n$ et $n\mid m$ alors $m=n$ ou $m=-n.$
Si trois entiers $m,n,p$ vérifient $m\mid n$ et $n\mid p,$ alors $m\mid p.$

Pour les amateurs de concepts abstraits, la première et la troisième affirmation ci-dessus expriment respectivement la réflexivité et la transitivité de la relation de divisibilité dans l’ensemble $\mathbb{Z}.$

Quant à la seconde affirmation, elle dit que deux entiers qui se divisent mutuellement sont nécessairement égaux ou opposés.

En se plaçant dans $\mathbb{N},$ au lieu de $\mathbb{Z}$ (c’est-à-dire en ne considérant que des entiers positifs ou nuls), les choses « s’arrangent » :

→ Si deux entiers naturels $m,n$ vérifient $m\mid n$ et $n\mid m,$ alors $m=n.$

On parle, pour traduire cela, d’antisymétrie de la relation de divisibilité dans $\mathbb{N}.$

Cette propriété est à rapprocher des deux suivantes, certainement bien connues :

si deux nombres réels $x,y$ vérifient $x\leqslant y$ et $y\leqslant x,$ alors $x=y.$
si deux ensembles $A,B$ vérifient $A\subset B$ et $B\subset A,$ alors $A=B.$

Lorsqu’on s’intéresse aux diviseurs d’un entier $n,$ on peut se limiter aux diviseurs positifs puisque $d\mid n$ équivaut à $-d\mid n.$ D’où la convention suivante :

Dans toute la suite, et sauf avis contraire, lorsqu’on écrira « diviseur », il faudra comprendre « diviseur positif ».

Par exemple, les diviseurs de 48 sont au nombre de dix. Les voici dans l’ordre croissant :

$1,\:2,\:3,\:4,\:6,\:8,\:12,\:16,\:24,\:48$

Quant à 17, ses seuls diviseurs sont 1 et 17, ce qu’on exprime en disant que 17 est premier (pour en savoir davantage sur les nombres premiers, on pourra consulter cet article).

Un petit test pour voir si vous suivez :

Vrai ou Faux ?

Quelques « Vrai ou Faux » pour voir si vous suivez…

54 possède plus de diviseurs que 24.
7 est un diviseur de 343.
1001 est un nombre premier.
il existe des entiers naturels possédant exactement trois diviseurs.
si un entier $n$ divise simultanément deux entiers $a$ et $b,$ alors $n\mid a+b.$
la somme des diviseurs de 512 est inférieure à 1000.

Les réponses sont regroupées en fin d’article.

Il revient au même de dire que $n$ est multiple de $d$ ou que le reste de la division de $n$ par $d$ est nul.

Par exemple, 128588 est divisible par 17 comme on le voit en posant la division (le reste est nul) :

Maintenant, interrogeons-nous :

Question [Q]

Est-il possible de reconnaître qu’un entier est multiple d’un autre sans effectuer la division ?

Par exemple, si 5 enfants souhaitent se partager équitablement 1165 billes, ils peuvent vérifier que c’est possible en posant la division : comme $1165=233\times5,$ alors 1165 est multiple de 5 et chaque enfant recevra 233 billes.

Mais pour se convaincre que le partage équitable est possible, ils peuvent aussi observer que l’écriture décimale de 1165 se termine par un ‘5’.

Vous saviez cela. Mais sauriez-vous le justifier ?

Voici l’explication pour un nombre de 4 chiffres :

Explication (cliquer pour déplier / replier)

Prenons un nombre à quatre chiffres et notons-le $n=abcd,$ ce qui signifie :

$n=a\times1000+b\times100+c\times10+d$

avec $a,b,c,d$

des entiers, tous compris entre 0 et 9. En posant $q=a\times200+b\times20+c\times2,$

cette égalité prend la forme plus concise :

$n=5\times q+d$

$\boxed{\Rightarrow}$

Si $n$

est multiple de 5, disons $n=5\times k,$

alors $d$

aussi puisque :

$d=5\times\left(k-q\right)$

Mais puisque $0\leqslant d\leqslant9,$

ceci impose $d=0$

ou bien $d=5.$

$\boxed{\Leftarrow}$ Réciproquement, si $d=0$ alors :

$n=5\times q$

et si $d=5,$

alors :
n=5\times\left(q+1\right)
\]On voit ainsi l’équivalence entre les deux énoncés :

$n$ est multiple de 5
$d=0$ ou $d=5$

Et ceci se généralise à des entiers naturels quelconques (pas seulement ceux dont l’écriture décimale comporte quatre chiffres !). C’est ce que dit la proposition suivante :

Proposition

Etant donné un entier naturel $n,$ dont le chiffre des unités est $c$ :

$5\mid n\Leftrightarrow c\in\left\{0,5\right\}$

ce qui se lit : « $n$

est multiple de 5 si, et seulement si, son chiffre des unités est 0 ou 5″.

Maintenant, mettons en place un peu de théorie et nous reprendrons la question [Q] à la section 4.

2 – Un mot sur les congruences

Imaginons un fil infiniment long, sur toute la longueur duquel sont placées de petites perles, régulièrement espacées :

A côté de chaque perle, on inscrit un nombre entier : l’une des perles porte le numéro 0 et, en parcourant le fil dans un sens à partir de cette position, on voit défiler les entiers positifs 1, 2, 3, etc …

Dans le sens inverse, ce sont les entiers négatifs -1, -2, -3, etc … qui apparaissent :

Imaginons maintenant un fil hélicoïdal :

Disposons les perles sur cette hélice, de telle sorte qu’elles soient toutes sur une même verticale :

A présent, aplatissons notre fil hélicoïdal en le projetant sur un plan horizontal.

Fatalement, les perles vont toutes se retrouver au même endroit :

Et maintenant, multiplions par 5 la densité des perles sur le fil hélicoïdal :

Cette fois, on observe en projection cinq zones de regroupements pour les perles… c’est-à-dire pour les entiers relatifs.

Les entiers …, -5, 0, 5, … seront tous regroupés au même endroit.

Même chose pour …, -4, 1, 6, … tout comme pour …, -3, 2, 7, … et aussi pour …, -2, 3, 8, … et enfin pour …, -1, 4, 9, …

Lorsque deux entiers se retrouvent au même endroit du cercle, on dit qu’il sont congrus l’un à l’autre modulo 5.

Cela signifie que la longueur de fil qui sépare les perles correspondantes est un multiple de la circonférence, autrement dit que la différence entre ces deux entiers est un multiple de 5.

On peut bien sûr généraliser, en remplaçant 5 par un quelconque entier $n\geqslant1$ …

Et hop ! On peut maintenant donner la :

Définition

Etant donnés un entier $n\in\mathbb{N}^{\star}$ et deux entiers $a,b\in\mathbb{Z},$ on dit que « $a$ est congru à $b$ modulo $n$ « , ce qu’on note $a\equiv b\pmod{n},$ lorsque $a-b$ est multiple de $n.$

C’est ainsi que, par exemple :

$75\equiv5\pmod{10}$

$231\equiv1\pmod{23}$

$65\thinspace536\equiv1098\pmod{1111}$

La première congruence résulte de $75-5=7\times10.$
La seconde résulte de $231-1=10\times23.$
La troisième résulte, quant à elle, de $65\thinspace536-1\thinspace098=58\times1111.$

Lorsqu’on effectue la division euclidienne d’un entier $a\in\mathbb{Z}$ par un entier $b\in\mathbb{N}^{\star},$ on écrit :

$a=bq+r\qquad\text{avec }0\leqslant r<b$

Il est alors clair que $a\equiv r\pmod{b}.$

Mais attention à la réciproque ! Si trois entiers $a,b,r$ (avec $b\in\mathbb{N}^{\star})$ vérifient $a\equiv r\pmod{b},$ on ne peut pas en déduire que $r$ est le reste de la division euclidienne de $a$ par $b.$ C’est toutefois le cas si l’on ajoute l’hypothèse $0\leqslant r<b.$

Terminons cette section en présentant les règles de « compatibilité » de la congruence modulo $n$ avec l’addition et la multiplication.

Règle 1 – Compatibilité avec l’addition

Etant donné $n\in\mathbb{N}^{\star}$ et $\left(a,b,c,d\right)\in\mathbb{Z}^{4},$ si

$\left\{ \begin{array}{cc}a'\equiv a & \pmod{n}\\b'\equiv b & \pmod{n}\end{array}\right.$

alors :

$a'+b'\equiv a+b\pmod{n}$

Preuve (cliquer pour déplier / replier)

Par hypothèse, il existe des entiers $k,\ell$ tels que $a'-a=kn$ et $b'-b=\ell n.$ En ajoutant membre à membre ces deux égalités, il apparaît que :

$a'+b'-\left(a+b\right)=\left(k+\ell\right)n$

ce qui donne la conclusion.

Autrement dit, on peut ajouter membre à membre deux congruences, mais modulo un même entier !

Bien entendu, cela fonctionne tout aussi bien avec un nombre quelconque de congruences (toujours modulo un même entier).

En symboles, si $a_{1}\cdots,a_{r}$ et $b_{1},\cdots,b_{r}$ sont des entiers tels que, pour un certain $n\in\mathbb{N}^{\star}$ :

$\forall i\in\llbracket1,r\rrbracket,\;a_{i}\equiv b_{i}\pmod{n}$

alors :

$\sum_{i=1}^{r}a_{i}\equiv\sum_{i=1}^{r}b_{i}\pmod{n}$

Si vous n’êtes pas à l’aise avec le symbole $\Sigma,$

je vous suggère d’aller faire un petit tour par ici

Règle 2 – Compatibilité avec la multiplication

Etant donné $n\in\mathbb{N}^{\star}$ et $\left(a,b,c,d\right)\in\mathbb{Z}^{4},$ si

$\left\{\begin{array}{cc}a'\equiv a & \pmod{n}\\b'\equiv b & \pmod{n}\end{array}\right.$

alors :

$a'b'\equiv ab\pmod{n}$

Preuve (cliquer pour déplier / replier)

Par hypothèse, il existe des entiers $k,\ell$ tels que $a'-a=kn$ et $b'-b=\ell n.$ Il s’ensuit que :

$a'b'-ab=\left(a+kn\right)\left(b+\ell n\right)-ab=\left(a\ell+bk+k\ell n\right)n$

ce qui donne la conclusion.

On peut donc multiplier membre à membre des congruences modulo un même entier.

Plus généralement, l’hypothèse :

$\forall i\in\llbracket1,r\rrbracket,\;a_{i}\equiv b_{i}\pmod{n}$

entraîne :

$\prod_{i=1}^{r}a_{i}\equiv\prod_{i=1}^{r}b_{i}\pmod{n}$

Et en particulier, si $a\equiv b\pmod{n},$

alors $a^{r}\equiv b^{r}\pmod{n}$

pour tout exposant $r\in\mathbb{N}.$

Un exemple historique

On observe que :

$641=5\times128+1=5\times2^{7}+1$

donc :

$5\times2^{7}\equiv-1\pmod{641}$

et donc (en élevant à la puissance quatrième) :

$5^{4}\times2^{28}\equiv1\pmod{641}\qquad\left(\clubsuit\right)$

Par ailleurs :

$641=625+16=5^{4}+2^{4}$

donc :

$-5^{4}\equiv2^{4}\pmod{641}\qquad\left(\spadesuit\right)$

A présent, si l’on combine les relations $\left(\clubsuit\right)$

et $\left(\spadesuit\right),$

on obtient :

$2^{32}=2^{4}\times2^{28}\equiv-5^{4}\times2^{28}\equiv-1\pmod{641}$

ce qui signifie que le cinquième nombre de Fermat $F_{5}=2^{2^{5}}+1$

est multiple de 641 et, en particulier, qu’il n’est pas premier. Pierre de Fermat (1601 (?) – 1665) avait conjecturé – à tort – que les nombres de la forme $2^{2^{n}}+1$

sont premiers pour tout $n\in\mathbb{N}.$

C’est à Leonhard Euler (1707 – 1783) que l’on doit le contre-exemple ci-dessus.

Il aura fallu attendre près un siècle entre la formulation par Fermat de cette conjecture et sa réfutation par Euler !..

3 – Un mot sur l’écriture décimale des entiers positifs

A l’école, nous avons appris à écrire les nombres (entiers positifs) en utilisant les dix chiffres, de 0 à 9.

De manière précise, la possibilité pour n’importe quel $n\in\mathbb{N}^{\star}$ d’être représenté par son écriture décimale ou – plus généralement – dans une quelconque base de numération, constitue un théorème important dont voici l’énoncé :

Théorème

Etant donné un entier $B\geqslant2$ (la « base de numération »), tout entier $n\geqslant1$ peut s’écrire :

$n=\sum_{k=0}^{r}c_{k}B^{k}\qquad\text{avec :}$

$r\in\mathbb{N}$
Pour tout $k\in\llbracket0,r\rrbracket,$ $c_{k}$ est un entier compris entre 0 et $B-1$ inclus.
$c_{r}\neq0$

En outre, cette écriture est unique.

Les entiers $c_{0},\cdots,c_{r}$ sont appelés les chiffres de l’écriture de $n$ en base $B.$

Pour celles et ceux que ça intéresse, j’ai réalisé deux petites vidéos dans lesquelles :

ce théorème est expliqué et illustré d’exemples (vidéo 1) puis démontré rigoureusement (vidéo 2)
l’algorithme de conversion qui en découle est expliqué en Python.

Vous pouvez visionner ces vidéos dès maintenant, si vous le souhaitez.

Ce théorème va nous servir, dès la section suivante, à formuler et / ou démontrer certaines règles de divisibilité.

4 – Règles usuelles de divisibilité

Abordons à présent le cœur du sujet.

J’en vois qui rouspètent … « c’était bien long avant de démarrer !!… ».

C’est un peu vrai, mais il fallait bien rassembler les outils appropriés pour aborder sereinement ces questions.

Etant donné un entier $n\geqslant1,$ nous disposons de son écriture décimale (voir section précédente) :

$n=\sum_{k=0}^{r}c_{k}10^{k}$

avec $r\in\mathbb{N},$

les chiffres $c_{0},\cdots,c_{r}$

dans $\llbracket0,9\rrbracket$

et $c_{r}\neq0.$

Tout d’abord, énonçons quelques règles, sans démonstration.

Trois règles portant sur le chiffre des unités seulement

[ $R_{10}$ ] $n$ est divisible par 10 si, et seulement si $c_{0}=0.$
[ $R_{2}$ ] $n$ est divisible par 2 si, et seulement si $c_{0}$ l’est, c’est-à-dire si $c_{0}\in\left\{ 0,2,4,6,8\right\} .$
[ $R_{5}$ ] $n$ est divisible par 5 si, et seulement si $c_{0}$ l’est, c’est-à-dire si $c_{0}\in\left\{ 0,5\right\} .$

Une règle portant sur les deux derniers chiffres

[ $R_{4}$ ] $n$ est divisible par 4 si, et seulement si $c_{0}+10c_{1}$ l’est, c’est à dire si l’entier formé par le chiffre des dizaines et celui des unités est multiple de 4.

Une règle portant sur les trois derniers chiffres

[ $R_{8}$ ] $n$ est divisible par 8 si, et seulement si $c_{0}+10c_{1}+100c_{2}$ l’est, c’est à dire si l’entier formé par le chiffre des centaines, celui des dizaines et celui des unités est multiple de 8.

Trois règles portant sur l’ensemble des chiffres

[ $R_{3}$ ] $n$ est divisible par 3 si, et seulement si $c_{0}+\cdots+c_{r}$ l’est.
[ $R_{9}$ ] $n$ est divisible par 9 si, et seulement si $c_{0}+\cdots+c_{r}$ l’est.
[ $R_{11}$ ] $n$ est divisible par 11 si, et seulement si $c_{0}-c_{1}+\cdots+\left(-1\right)^{r}c_{r}$ l’est (autrement dit si la somme alternée des chiffres est multiple de 11).

L’intérêt de ce genre de critère est clair : ils nous permettent de savoir si un entier est multiple de 3 (ou de 9, ou de 11, etc…) en effectuant considérablement moins de calculs que si l’on posait la division. Et cet écart est d’autant plus marqué que l’écriture décimale de l’entier testé comporte davantage de chiffres.

Pour les preuves des règles [ $R_3$ ] et [ $R_9$ ], je vous renvoie à la fiche n° 1 sur la divisibilité.
La règle [ $R_{11}$ ] est établie à la section 5 … mais n’y allez pas tout de suite !
Cherchez un peu 🙂

Les autres règles sont très simples à démontrer.

5 – L’affaire 1001

Tout d’abord, un constat :

$\boxed{1001=7\times11\times13}$

Nous allons nous appuyer sur cette égalité pour élaborer deux tests de divisibilité, l’un par 7 et l’autre par 13.

Considérons un entier positif $n$ et son écriture en base 1000.

C’est vrai que, dit comme ça, c’est un peu étrange … Mais après tout, le théorème énoncé à la section 3 est valable en particulier pour $B=1000$ .

On écrit donc :

$n=\sum_{k=0}^{s}p_{k}\thinspace1000^{k}\qquad\left(\heartsuit\right)$

Les entiers $p_{k}$

sont tous compris entre 0 et 999 inclus.

Ce sont les chiffres de l’écriture de $n$ en base 1000. Par exemple, si $n=7\thinspace616\thinspace135\thinspace413$ (écriture décimale), alors $s=3$ et :

$p_{0}=413,\qquad p_{1}=135,\qquad p_{2}=616,\qquad p_{3}=7$

On forme donc simplement des « paquets » en groupant, de droite à gauche, les chiffres trois par trois. Le « paquet » le plus à gauche comporte, selon le cas, un, deux ou trois chiffres.

Mais revenons au cas général. Comme $1000\equiv-1\pmod{7},$ on déduit de $\left(\heartsuit\right)$ que :

$n\equiv\sum_{k=0}^{s}\left(-1\right)^{k}p_{k}\pmod{7}$

Et l’on peut faire exactement le même calcul modulo 13, puisque $1000\equiv-1\pmod{13}.$

Il en découle les deux règles suivantes :

Règles de divisibilité par 7 et 13

[ $R_{7}$ ] $n$ est divisible par 7 si, et seulement $p_{0}-p_{1}+\cdots+\left(-1\right)^{s}p_{s}$ l’est
[ $R_{13}$ ] $n$ est divisible par 13 si, et seulement $p_{0}-p_{1}+\cdots+\left(-1\right)^{s}p_{s}$ l’est

Voyons un exemple. Considérons l’entier $n=47\thinspace069\thinspace160\thinspace229,$ pour lequel $s=3$ et

$p_{0}=229,\qquad p_{1}=160,\qquad p_{2}=69,\qquad p_{3}=47$

Calculons :

$\begin{eqnarray*}p_{0}-p_{1}+p_{2}-p_{3} & = & 229-160+69-47\\ & = & 91\end{eqnarray*}$

Comme $91=7\times13,$

on peut affirmer que $47\thinspace069\thinspace160\thinspace229$

est multiple de $7$

et de $13.$

Encore un exemple, avec $n=43\thinspace130\thinspace155\thinspace914\thinspace636.$
Cette fois, $s=4$ et :

$p_{0}=636,\qquad p_{1}=914,\qquad p_{2}=155,\qquad p_{3}=130,\qquad p_{4}=43$

donc :

$\begin{eqnarray*}p_{0}-p_{1}+p_{2}-p_{3}+p_{4} & = & 636-914+155-130+43\\& = & -210\\& = & 7\times\left(-30\right)\end{eqnarray*}$

ce qui prouve que $43\thinspace130\thinspace155\thinspace914\thinspace636$

est multiple de 7 (mais pas de 13, puisque $13\nmid210).$

Un dernier mot à ce sujet : la congruence $1000\equiv-1\pmod{11}$ est aussi vraie. Alors pourquoi ne pas énoncer un test similaire de divisibilité par $11$ ?

Tout simplement parce qu’il y a plus simple. Il suffit de voir que $10\equiv-1\pmod{11}$ et donc, en utilisant l’écriture décimale :

$n=\sum_{k=0}^{r}c_{k}\thinspace10^{k}$

on voit que :

$n\equiv\sum_{k=0}^{r}\left(-1\right)^{k}c_{k}$

ce qui donne la règle $R_{11}$

énoncée à la fin de la section précédente.

6 – Les tests itérés

Etant un donné un entier naturel $n,$ notons $d$ le nombre des dizaines et $u$ le chiffre des unités, de sorte que $n=10d+u.$

Par exemple si $n=2\thinspace019,$ alors $d=201$ et $u=9.$

On décrit ici un ensemble de règles ayant en commun de ramener la question « $n$ est-il divisible par $N$ » à la question « $d+\lambda u$ est-il divisible par $N$ « , où $\lambda$ désigne un entier convenablement choisi et qui dépend de $N.$

J’ai adopté la terminologie de « tests itérés » car, en principe, on aura $\left|d+\lambda u\right|<n,$ ce qui va nous conduire à itérer le mécanisme, c’est-à-dire à construire une séquence décroissante d’entiers :

$n_{0}>n_{1}>\cdots>n_{q}$

tels que :

$n_{0}=n$

et pour tout $i\in\left\{ 1,\cdots,q\right\}$

$N\mid n_{i}\Leftrightarrow N\mid n_{i-1}$

L’idée est que $n_{q}$

soit assez petit pour que la question de savoir s’il est divisible par $N$

soit évidente.

Si vous connaissez une dénomination officielle pour ce type de règle, je vous remercie par avance de m’en informer (en passant par exemple par le formulaire de contact).

Avant de présenter cette méthode dans le cas général, examinons quatre cas particuliers (divisibilité par 7, par 13, par 17 ou par 19) :

Règle itérée pour 7

Le cas $N=7$

On constate que :

$\begin{eqnarray*}n & = & 10d+u\\& = & 10\left(d-2u\right)+21u\end{eqnarray*}$

d’où l’on déduit que si $7\mid d-2u$

alors $7\mid n.$

Par ailleurs :

$\begin{eqnarray*}d-2u & = & d-2\left(n-10d\right)\\& = & 21d-2n\end{eqnarray*}$

d’où l’on déduit que si $7\mid n$

alors $7\mid d-2u.$

Ainsi :

$\boxed{7\mid n\Leftrightarrow7\mid d-2u}$

Exemple

$\begin{eqnarray*}573\thinspace461\\\downarrow\\57\thinspace344\\\downarrow\\5\thinspace726\\\downarrow\\560\\\downarrow\\56\end{eqnarray*}$

or $7\mid56$

et donc $7\mid573\thinspace461.$

Remarque

lorsque l’un des entiers de la séquence se termine par un 0, on peut directement supprimer ce chiffre et passer à l’entier suivant (ici, de 560 à 56). En effet, $10$ et $7$ sont premiers entre eux, donc $7\mid m\Leftrightarrow7\mid10m$ pour tout entier $m$ .

Règle itérée pour 13

Le cas $N=13$

On constate que :

$\begin{eqnarray*}n & = &10d+u\\& = & 10\left(d+4u\right)-39u\end{eqnarray*}$

d’où l’on déduit que si $13\mid d+4u$

alors $13\mid n.$

Par ailleurs :

$\begin{eqnarray*}d+4u & = & d+4\left(n-10d\right)\\& = & 4n-39d\end{eqnarray*}$

d’où l’on déduit que si $13\mid n$

alors $13\mid d+4u.$

Ainsi :

$\boxed{13\mid n\Leftrightarrow13\mid d+4u}$

Exemple

$\begin{eqnarray*}54\thinspace098\thinspace603\\\downarrow\\5\thinspace409\thinspace872\\\downarrow\\540\thinspace995\\\downarrow\\54\thinspace119\\\downarrow\\5\thinspace447\\\downarrow\\572\\\downarrow\\65\\\downarrow\\26\end{eqnarray*}$

or $13\mid26$

et donc $13\mid54\thinspace098\thinspace603.$

Remarque

A partir de l’entier 26, l’itération de produit rien de neuf, puisque
$26\rightarrow2+4\times6=26.$

Règle itérée pour 17

Le cas $N=17$

On constate que :

$\begin{eqnarray*}n & = & 10d+u\\& = & 10\left(d-5u\right)+51u\end{eqnarray*}$

d’où l’on déduit que si $17\mid d-5u$

alors $17\mid n.$

Par ailleurs :

$\begin{eqnarray*}d-5u & = & d-5\left(n-10d\right)\\& = & 51d-5n\end{eqnarray*}$

d’où l’on déduit que si $17\mid n$

alors $17\mid d-5u.$

Ainsi :

$\boxed{17\mid n\Leftrightarrow17\mid d-5u}$

Exemple

$\begin{eqnarray*}12\thinspace106\thinspace482\\\downarrow\\1\thinspace210\thinspace638\\\downarrow\\121\thinspace023\\\downarrow\\12\thinspace087\\\downarrow\\1\thinspace173\\\downarrow\\102\\\downarrow\\0\end{eqnarray*}$

or $17\mid0$

et donc $17\mid12\thinspace106\thinspace482.$

Règle itérée pour 19

Le cas $N=19$

On constate que :

$\begin{eqnarray*}n & = & 10d+u\\& = & 10\left(d+2u\right)-19u\end{eqnarray*}$

d’où l’on déduit que si $19\mid d+2u$

alors $19\mid n.$

Par ailleurs :

$\begin{eqnarray*}d+2u & = & d+2\left(n-10d\right)\\& = & 2n-19d\end{eqnarray*}$

d’où l’on déduit que si $19\mid n$

alors $19\mid d+2u.$

Ainsi :

$\boxed{19\mid n\Leftrightarrow19\mid d+2u}$

Exemple

$\begin{eqnarray*}51\thinspace570\thinspace389\\\downarrow\\5\thinspace157\thinspace056\\\downarrow\\515\thinspace717\\\downarrow\\51\thinspace585\\\downarrow\\5\thinspace168\\\downarrow\\532\\\downarrow\\57\\\downarrow\\19\end{eqnarray*}$

or $19\mid19$

et donc $19\mid51\thinspace570\thinspace389.$

Plus généralement, si $N$ est un entier premier avec $10,$ alors l’identité de Bézout garantit l’existence de deux entiers relatifs $\lambda,\mu$ tels que $10\lambda-\mu N=1.$ On voit alors que :

$\begin{eqnarray*}n & = & 10d+u\\& = & 10\left(d+\lambda u\right)-\mu Nu\end{eqnarray*}$

ce qui montre déjà que $N\mid d+\lambda u\Rightarrow N\mid n.$

Par ailleurs :

$\begin{eqnarray*}d+\lambda u & = & d+\lambda\left(n-10d\right)\\& = & \lambda n-\mu Nd\end{eqnarray*}$

ce qui prouve l’implication réciproque. Bref :

$\boxed{N\mid n\Leftrightarrow N\mid d+\lambda u}$

Remarque

Ce critère n’a d’intérêt que si l’entier testé est remplacé par un entier plus petit, c’est-à-dire si $\left|d+\lambda u\right|<n$ , condition qui est effectivement remplie dans chacun des quatre cas détaillés plus haut.

Annexe : Réponses aux Vrai / Faux

54 possède plus de diviseurs que 24.

C’est FAUX, il en possède autant !

Diviseurs de $24$ :

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

Diviseurs de $54$

$1,\:2,\:3,\:6,\:9,\:18,\:27,\:54$

D’une manière générale, étant donné un entier $n\geqslant2,$

on peut le décomposer en produit de nombres premiers :

$n=p_{1}^{\alpha_{1}}\cdots p_{r}^{\alpha_{r}}$

où $p_{1},\cdots,p_{r}$

sont des nombres premiers tous distincts et où $r$

et $\alpha_{1},\cdots,\alpha_{r}$

sont des entiers naturels non nuls.

Avec ces notations, le nombre de diviseurs de $n$ est donné par le produit :

$D\left(n\right)=\left(1+\alpha_{1}\right)\cdots\left(1+\alpha_{r}\right)$

Ainsi, comme $24=2^{3}\times3$

$D\left(24\right)=\left(3+1\right)\left(1+1\right)=8$

et comme $54=2\times3^{3}$

$D\left(54\right)=\left(1+1\right)\left(3+1\right)=8$

7 est un diviseur de 343.

C’est VRAI, puisque :

$7^{3}=7\times49=343$

1001 est un nombre premier.

C’est FAUX. On constate que :

$1\thinspace001=7\times11\times13$

Le test de divisibilité par $7$ ou par $13$ permettait de le découvrir, puisque la somme alternée des chiffres en base $1\thinspace000$ est nulle (voir section 5) !

Il existe des entiers naturels possédant exactement trois diviseurs.

C’est VRAI. En effet, si $p$ est un nombre premier et si $n\geqslant1,$ alors les diviseurs de $p^{n}$ sont les $p^{k}$ pour $0\leqslant k\leqslant n.$ En particulier, les diviseurs de $p^{2}$ sont $1,$ $p$ et $p^{2}.$

Les carrés de nombres premiers sont d’ailleurs les seuls entiers qui possèdent exactement trois diviseurs ! En effet, d’après la formule vue plus haut (voir le premier « Vrai ou Faux »), il faut que $\left(1+\alpha_{1}\right)\cdots\left(1+\alpha_{r}\right)=3,$ ce qui impose que l’un des $\alpha_{i}$ vaut $2$ et tous les autres valent $0,$ autrement dit que $n$ est de la forme $p^{2},$ avec $p$ premier.

Si un entier $n$ divise simultanément deux entiers $a$ et $b,$ alors $n\mid a+b.$

C’est VRAI. En effet, si $a=kn$ et $b=k'n,$ alors $a+b=\left(k+k'\right)n.$ Tout simplement.

La somme des diviseurs de 512 est inférieure à 1000.

C’est FAUX.

On peut certainement faire le calcul « bêtement ».

Mais on peut aussi observer que $512=2^{9}$ et que, par conséquent, les diviseurs de $512$ sont les $2^{k}$ pour $0\leqslant k\leqslant9.$

En utilisant la formule donnant la somme d’une progression géométrique (programme de première), on trouve :

$1+2+4+8+16+32+64+128+256+512=\sum_{k=0}^{9}2^{k}=2^{10}-1=1\thinspace023$

Merci de m’avoir lu jusqu’au bout 🙂

Si vous souhaitez chercher des exercices en rapport avec le thème de la divisibilité, vous pouvez jeter un coup d’œil par ici.

Vos questions ou remarques sont les bienvenues. Vous pouvez laisser un commentaire ci-dessous ou bien passer par le formulaire de contact.

Partager cet article

Cet article a 3 commentaires

Martin Barts--Bérard 23 Mar 2020 Répondre

Merci beaucoup, des techniques très intéressantes et des découvertes pour ma part! 🙂
errard.serge@sfr.fr 30 Juin 2019 Répondre

toujours très bon mais souhaite d autres domaines d intérêt: ex méthode et tech de recherche de plans stables par un endomorphisme de R »3……….
1. René Adad 30 Juin 2019 Répondre
  
  Merci pour ce commentaire. Mon prochain article sera donc consacré à une question d’algèbre linéaire 🙂