Connaître les diviseurs... sans diviser


Élisabeth Busser (avec la participation de Daniel Lignon)

Reconnaître, presque à vue d'œil, si un entier est divisible par un autre relève parfois de la gageure. Il existe cependant des méthodes tout à fait fiables pour cela, même avec des nombres assez grands !

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 : 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  \( \mathbb{Z}\)  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  \( \{\dot{0}, \dot{1}, \dot{2}%E2%80%A6 \dot{(b-1)} \}.\)  

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 ... 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.