On sait, depuis l’école primaire, reconnaître si un nombre est divisible par 2, 3, 4, 5, 6, 8, 10 ou 11. Pour des diviseurs comme 7, 13, 17, 23, 29… ou même 271, cela semble en revanche relever de la haute voltige. Pourtant, il existe des façons d’y parvenir. Faisons donc le tour, des plus simples aux plus compliqués, des critères de divisibilité dans le royaume des nombres entiers. Or, quand on parle de divisibilité, la notion de congruence (voir encadré) va très souvent faciliter la tâche.
Vous avez dit « congruences » ?
L’existence même du nombre r permet de définir sur l’ensemble ℤ des entiers relatifs une relation d’équivalence : a et a’ sont dits équivalents s’ils ont même reste dans la division par b. On dit encore « a est congru à a’ modulo b », ce que l’on écrit a ≡ a’ [ b ]. On fait ainsi une partition de en b parties disjointes appelées classes, celles des brestes possibles dans la division par b. Chaque classe correspond à une valeur du reste, de 0 à b – 1 ; on les note
La relation « est congru à » est compatible avec l’addition, la soustraction, la multiplication et l’élévation à une puissance.
L’application qui à un entier associe sa valeur modulo b est un homomorphisme, c’est-à-dire que le reste d’une somme de deux nombres est congru, ... Lire la suite