Vers la fin du XIXe siècle, Édouard Lucas a trouvé le moyen de faire du calcul modulo 7 avec l'échiquier de Neper. Modulo 7, ça veut dire qu'une fois la multiplication effectuée, on divise par 7 (division euclidienne) et on ne garde que le reste. Ce reste est nul si et seulement si le produit est divisible par 7.
Pour calculer 3×2, on dispose les pions ainsi :
L'averse à 45° de Neper ne fait bouger que le pion du haut puisque celui du bas est déjà en bas. On obtient alors ce produit :
Effectivement, le nombre représenté en bas est 4+2+0=6 et on a bien 2×3=6. En fait, en effectuant la division euclidienne de 6 par 7, on a un quotient nul et un reste de 6: L'égalité 2×3=6 reste vraie modulo 7.
Mais si on veut effectuer 2×4, on a un problème de place (8 est plus grand que 7, et la division euclidienne de 8 par 7 donne un reste de 1, donc modulo 7, 2×4=1):
Le pion ne peut pas aller à 45° vers la gauche parce que ça le ferait sortie de l'échiquier. Dans ce cas, Édouard Lucas propose cette règle :
Le produit 2×4 devient alors
Effectivement, modulo 7, 2×4 vaut 1 parce que 8=7+1. Si on veut maintenant calculer 3×3 modulo 7 :
Après l'averse à 45°, aucun pion n'est sorti par la gauche. En effet le pion le plus à gauche est en position "4". Mais il y a deux pions de 2g, et lorsqu'on veut les remplacer par un pion de 4g, on aboutit à 2 pions de 4g, et lorsqu'on veut remplacer à leur tour ces deux pions de 4g, par un seul, ce n'est pas de 8g puisqu'il n'y a pas de case à 8g: Ce pion sort par la gauche (même si ce n'est pas à 45°), et revient par la droite. Alors il reste deux pions de 1g, que l'on va remplacer par un pion de 2g:
Vérification sans le binaire: 3×3=9, et 9=7+2: La division euclidienne de 9 par 7 donne un reste de 2. Modulo 7, on a donc bien 3×3=9.
| 4 | ||||
| 2 | ||||
| 1 | ||||
| 4 | 2 | 1 | ||
|
|
|
|
|
| × | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 0 | 2 | 4 | 6 | 1 | 3 | 5 |
| 3 | 0 | 3 | 6 | 2 | 5 | 1 | 4 |
| 4 | 0 | 4 | 1 | 5 | 2 | 6 | 3 |
| 5 | 0 | 5 | 3 | 1 | 6 | 4 | 2 |
| 6 | 0 | 6 | 5 | 4 | 3 | 2 | 1 |
On peut se servir de cette table pour s'exercer (effectuer les multiplications modulo 7) sur l'échiquier, puis vérifier le résultat dans le tableau). En particulier, pour la suite, s'exercer à calculer des carrés. Et plus particulièrement, une opération importante pour Édouard Lucas est la soustraction de 2 à un carré.
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| x²-2 | 5 | 6 | 2 | 0 | 0 | 2 | 6 |
Le fait qu'en partant de 4, on aboutisse à 0 (échiquier vide) illustre l'algorithme de Lucas-Lehmer pour tester la primalité d'un nombre de Mersenne (du type 2p-1 où p est premier) comme ici, 7=23-1. Voici comment fonctionne l'algorithme :
On prend le nombre 4 comme nombre de départ; puis on répète p-1 fois au maximum l'opération consistant à
Ici dès la première itération, l'échiquier est vide donc 7 est bien un nombre premier. L'algorithme est plus efficace que le recherche de diviseurs potentiels de 2p-1 lorsque p devient grand (ici p=3 n'est pas vraiment grand). Voir les cas où