En réfléchissant à un sujet d’examen pour mes étudiants (en architecture des ordinateurs) je suis tombé sur cet algorithme qui permet de déterminer la divisibilité d’un nombre N par D en opérant (presque) seulement des divisions par 2 (en fait, il faut aussi pouvoir faire des additions simples ou des soustractions, mais comme les soustractions sont souvent moins simples, dans la suite, on se limitera à faire des additions “simples”).
Supposons donc que l’on veuille trouver si N (un nombre quelconque positif) est multiple de D (un nombre quelconque positif), par exemple, on veut trouver si 1789 (N) est multiple de 13 (D) :
- (Cas 1 : N pair, D pair) : Si N et D sont tous les deux pairs, on peut les diviser tous les deux par 2 (ce qui est assez facile en décimal et immédiat sur machine ou quand on pense binaire). Le nouveau N sera multiple du nouveau D ssi le précédent N était multiple du précédent D. Le problème est donc réduit à un problème plus petit. On peut répéter cette opération jusqu’à ce que N ou D soient impairs.
Supposons donc maintenant que N ou D, ou les deux sont impairs.
- (Cas 2 : N impair, D pair) : Si N est impair et D pair, alors N ne sera pas multiple de D. En effet, si N était multiple de D, comme D est pair, N serait pair, ce qu’il n’est pas. Donc N n’est pas multiple de D. Le problème est clos.
- (Cas 3 : N pair, D impair) : Si N est pair et D impair, alors on peut diviser N par 2. Comme D est impair, ce n’est pas la parité de N qui permet N d’être multiple de D. On peut donc répéter cette opération jusqu’à ce que N soit impair.
On arrive donc à la situation où l’on cherche si un nombre impair N est multiple d’un nombre impair D.
- (Cas 4 : N impair, D impair) : On peut additionner D de N (ou le soustraire), cela ne change pas le critère de divisibilité de N par D. Le nouveau N est pair (par addition de deux nombres impairs), ce qui nous ramène au cas précédent (cas 3).
Comment cela se termine ?
- cela se termine par la négative dans le cas 2 : N n’est pas multiple de D.
- cela peut aussi se terminer si on arrive à un moment à N=0 ou N=D. Dans ce cas, N est (trivialement) multiple de D.
- cela peut aussi se terminer si on arrive à un moment avec N entre 1 et D-1. Dans ce cas, N n’est pas multiple de D.
Dans tous les cas cela se termine parce que l’un des deux nombres est réduit dans les étapes 1, 2 et 3, et que dans le cas 4, il N n’est pas réduit immédiatement, puisqu’il y a une addition N+D remplaçant N, mais à l’étape suivante, on a le cas 3 qui réduit N en le divisant par 2. (cas 4 suivi de 3 : N <= (N+D)/2, cela réduit N si N>D, car si N>D, N+N>N+D, donc (N>(N+D)/2, le nouveau N sera plus petit que le précédent)
Exemple pour 1789 et 13 :
- cas 4 (1789 impair/ 13 impair) : 1789+13=1802 (pair), on se retrouve dans le cas 3
- cas 3 (1802 pair/ 13 impair) : 1802 divisé par 2 égal 901 (impair), on se retrouve dans le cas 4
- cas 4 (901 impair/ 13 impair) : 901+13=914 (pair), on se retrouve dans le cas 3
- cas 3 (914 pair/ 13 impair) : 914 divisé par 2 égal 457 (impair), on se retrouve dans le cas 4
- cas 4 (457 impair/ 13 impair) : 457+13=470 (pair), on se retrouve dans le cas 3
- cas 3 (470 pair/ 13 impair) : 470 divisé par 2 égal 235 (impair), on se retrouve dans le cas 4
- cas 4 (235 impair/ 13 impair) : 235+13=248 (pair), on se retrouve dans le cas 3
- cas 3 (248 pair/ 13 impair) : 248 divisé par 2 égal 124 (pair), on se retrouve dans le cas 3
- cas 3 (124 pair/ 13 impair) : 124 divisé par 2 égal 62 (pair), on se retrouve dans le cas 3
- cas 3 (62 pair/ 13 impair) : 62 divisé par 2 égal 31 (impair), on se retrouve dans le cas 4
- cas 4 (31 impair/ 13 impair) : 31+13=44 (pair), on se retrouve dans le cas 3
- cas 3 (44 pair/ 13 impair) : 44 divisé par 2 égal 22 (pair), on se retrouve dans le cas 3
- cas 3 (22 pair/ 13 impair) : 22 divisé par 2 égal 11 (impair)
On est arrivé à la fin, 11 est plus petit que 13, il est clair qu’il n’est pas divisible par 13.
Donc 1789 n’est pas divisible par 13.
Pour en savoir plus : voir ici