primalité de 2⁵-1=31

Pour calculer 4², on dispose les pions ainsi :

		♟

Après l'averse à 45°, le pion est encore du côté gauche (il n'y a pas eu de dépassement) :

♟

Mais on ne peut pas soustraire 2 parce que la case "2" est vide (il n'y a pas de pion à enlever). On va donc successivement

• remplacer le pion de 16g par deux pions de 8g;
• remplacer un des deux pions de 8g par deux pions de 4g;
• remplacer un des deux pions de 4g par deux pions de 2g;
• enlever un des deux pions de 2g.

On obtient alors le nombre suivant qui est 14 :

	♟	♟	♟

C'est ce nombre qu'on va élever au carré à l'étape suivante :

	♟	♟	♟
	♟	♟	♟
	♟	♟	♟

Cette fois-ci, il y a des pions qui, en descendant à 45°, sont reportés sur le côté droit de l'échiquier, et les groupements-échanges vident nettement l'échiquier puisqu'au bout du compte il ne reste qu'un seul pion :

	♟

Pour élever ce nombre au carré, on le met ici :

	♟

Il n'y a donc qu'un seul pion à déplacer à 45°, mais il revient par la droite et aboutit ici:

			♟

Pour effectuer la soustraction de 2, il suffit d'enlever ce pion en position 2, et l'échiquier est maintenant vide: On a fini !

On a donc calculé successivement les nombres

1. 4
2. 14
3. 8
4. 0

et comme il a fallu moins de 5 itérations pour que l'échiquier soit vide, on a la preuve que 2⁵-1=31 est premier.

Remarque

Pour tester la primalité de 31, il y a plus court que l'algorithme de Lucas-Lehmer: Comme 31<36, les seuls diviseurs potentiels de 31 à tester sont 2, 3 et 5:

• 31 se termine par 1 et n'est donc divisible ni par 2, ni par 5;
• 3+1=4 donc 31 n'est pas divisible par 3 non plus.

Par contre, pour quelqu'un qui ne connaîtrait que le binaire, les critères de divisibilité par 11 3 et par 101 5 sont plus compliqués qu'en base 10.