Souvenez-vous de vos jeunes années (on aime bien les retours dans le temps par ici). On vous avait appris une règle super-trop-bien pour savoir si un nombre était multiple de \(3\) : on somme tous ses chiffres, et on regarde si la somme est un multiple de \(3\). Par exemple, pour \(518\) on obtient \(5 + 1 + 8 = 14\), or \(14\) n'est pas un multiple de \(3\), donc \(518\) non plus. Y a pas à dire, c'était pratique !
Quel dommage que l'astuce ne fonctionne que pour \(3\) et \(9\) !
Et c'est à cet instant que le mathématicien tapi au fond de moi se révèle : ça ne marche que pour \(3\) et pour \(9\) ? Pourquoi ? Et comment ?
Je vais être sympa, et plutôt que de vous imposer mon raisonnement tortueux je vais vous expliquer pas à pas comment globaliser les critères de divisibilité à tous les nombres. Malheureusement, ce ne sera pas aussi simple que pour \(3\) et \(9\)… mais à la fin, on pourra vérifier que la règle générale fonctionne aussi pour les cas particuliers que seront devenus \(3\) et \(9\) !

L'idée donc, c'est de trouver « une somme coefficientée des chiffres de \(n\) telle que \(n\) soit un multiple de \(p\) si et seulement si la somme obtenue est un multiple de \(p\) aussi » (à relire lentement : en gros trouver une somme qui soit multiple si le nombre original est un multiple).
Normalement, une idée de somme vient directement à l'esprit : \(n = 1n_0 + 10n_1 + 100n_2 + 1000n_3 + \ldots\), \(n_i\) désignant comme vous l'aurez compris le ième chiffre dans l'écriture décimale de \(n\). On a trouvé notre somme, mais ça ne nous avance pas vraiment ! Car si elle vérifie bien la propriété demandée (\(n\) est un multiple si la somme est un multiple), c'est exactement le nombre original.

Quoi, tu te fiches de nous Neamar ? Une question aussi simple mérite une réponse concise : oui.
Mais ne vous inquiétez pas, nous n'avons pas fait tout ça pour rien. Dites bonjour à mon amie la congruence (bonjour congruence). La congruence, c'est un opérateur mathématique noté \(\equiv\) qui indique que les nombres de bouts de chaque côté du signe ont le même reste dans une division. Vous n'avez rien compris ? C'est normal, rien ne vaut l'apprentissage par l'exemple :

  • \(2 \equiv 9 (mod 7)\) car le reste de 2 divisé par 7 est 2 (oh !) et le reste de 9 divisé par 7 est 2 : les deux restes sont égaux, on peut utiliser la notation \(\equiv\).
  • Un autre exemple ? \(19 \equiv 10 (mod 9)\) : je divise 19 par 9, il y va deux fois (on s'en fiche) et il reste 1 (ça nous intéresse) ; je divise 10 par 9 il y va une fois (idem) et il reste 1 : les restes sont égaux.

Ce qui va nous intéresser aujourd'hui, c'est une des propriétés du modulo : si \(a \equiv b (mod n)\) alors \(ka \equiv kb (mod n)\)(1) – un peu comme « si \(a = b\) alors \(xa = xb\) ».
Deuxièmement, il faut dire que \(a = a\) implique que \(a \equiv a (mod x)\), avec x prenant n'importe quelle valeur entière. Logique après tout, que le reste de la division de \(a\) par \(x\) soit le même que le reste de la division de \(a\) par \(x\)…

Revenons à nos moutons. Nous nous étions arrêtés à une égalité (pour rappel, on cherchait un critère de divisibilité par \(p\)), remplaçons cette égalité par une congruence comme on vient de le voir : \(n \equiv 1n_0 + 10n_1 + 100n_2 + 1000n_3 + \ldots (mod p)\).
Prenons un terme à part pour l'analyser, par exemple \(10n_1\). On va essayer de simplifier cela ; et pour cela on va chercher un nombre \(a\) tel que \(a \equiv 10 (mod p)\). Le but, c'est bien évidemment de prendre \(a\) le plus petit possible pour simplifier le calcul ! Puis on remplace \(10\) par \(a\) dans la somme, et on procède de même pour 100 (\(a_2 \equiv 100 (mod p)\)), 1 000, et ainsi de suite : on a notre somme ! Encore une fois, j'ai peur d'en avoir lâché la moitié en route ; prenons un exemple concret : les critères de divisibilité par 7 (insérer une musique héroïque ici).

  1. Première étape : trouver nos différents coefficients. On va s'arrêter à 1 000, si vous avez compris la suite ça viendra tout seul. On cherche donc un nombre \(a\) congru à la puissance de 10 courante :

    • \(1 \equiv 1 (mod 7)\) (c'est pas le plus dur !) ;
    • \(10 \equiv 3 (mod 7)\) ;
    • \(100 \equiv 2 (mod 7)\) (la méthode est toujours la même : trouver le multiple de 7 le plus proche – ici, 98 – puis faire la différence) ;
    • \(1000 \equiv 6 \equiv -1 (mod 7)\) (eh oui, les nombres négatifs peuvent être intéressants aussi si ils sont petits).
  2. Deuxième étape : construire notre somme. Il suffit de remplacer les puissances de 10 par leurs congruences : \(n \equiv 1n_0 + 3n_1 + 2n_3 - 1n_4 + \ldots (mod 7)\).
  3. Et enfin, profiter du résultat : pour reprendre l'exemple de \(518\), on a notre somme qui vaut \(1\times8 + 3\times1 + 2\times5 = 10 + 3 + 8 = 21\), qui est multiple de 7… prouvant ainsi que \(518\) l'est aussi.

Petit bonus pour ceux qui sont arrivés jusque là sans basculer en mode « visionnage de petits caractères ressemblant à des lettres formant un assemblage hétéroclite et incompréhensible » : avec cette méthode, on retrouve :

  • le critère de divisibilité par \(3\) : toutes les puissances de 10 sont congrues à 1 modulo 3, on obtient bien une somme dont tous les coefficients sont de 1 ;
  • le critère de divisibilité par \(2\) et \(5\) : au delà de 1, toutes les puissances de 10 sont des multiples de 2 (resp. 5) ; donc le coefficient associé est 0 et on se retrouve à regarder uniquement l'unité.
  1. (1) ↑ Ceux qui aiment mettre des mots sur les notions pourront dire que cette propriété est vraie car \(\mathbb{Z}/n\mathbb{Z}\) est un groupe pour +, et que \((\mathbb{Z}/n\mathbb{Z},+,\times)\) est un anneau commutatif. Très aidant d'ailleurs.