Méthodes en arithmétique

Critères de divisibilité

d Critère de divisibilité d'un entier naturel n par d
2

Le dernier chiffre de n est pair (0, 2, 4, 6 ou 8).

3

La somme des chiffres de n est divisible par 3.

5

Le dernier chiffre de n est 0 ou 5.

7

La division euclidienne de n par 7 donne un reste nul.

11

La somme alternée des chiffres de n est un multiple de 11.

D'autres critères existent, notamment pour tester la divisibilité par 9 ou par 10, mais ils servent moins que ceux de la divisibilité par des facteurs premiers.

Plus généralement, pour déterminer la divisibilité d'un entier naturel n par un entier naturel d non nul, on peut calculer le reste dans la division euclidienne de n par d.

Décomposition en facteurs premiers

Pour décomposer un entier naturel non nul en produit de facteurs premiers, on divise autant de fois que possible par 2, par 3, par 5, par 7. Si on obtient un quotient inférieur ou égal à 120 (juste avant le carré de 11), ce quotient est nécessairement premier. Au delà, on peut tester la divisibilité par 11, 13, 17 et 19, ce qui permet de détecter tous les nombres premiers inférieurs à 528 (juste avant le carré de 23).