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
références
• Dossier « Les secrets du calcul mental ».
Tangente 163, 2015.
• Dossier « Calculer plus vite ».
Tangente 184, 2018 et
Tangente 188, 2019.
• Dossier « Promenades au pays des nombres ».
Tangente 177, 2017.