Connaître les diviseurs... sans diviser

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 $m a t h b b 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 $d o t 0, d o t 1, d o t 2 \hat{a} ¦ d o t (b - 1) . {dot{0},dot{1},dot{2}â¦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 deux nombres est congru, modulo b, à la somme de leurs restes ; de même, le reste d’un produit est congru, modulo b, au produit des restes.

On traduit en particulier, en utilisant le vocabulaire des congruences, la notion de divisibilité : « a est divisible par b » équivaut à dire que le reste dans la division de a par b est nul, ce qui s’écrit a ≡ 0 [ b ].

Lorsque b est un nombre premier, de nouvelles propriétés s’ajoutent. Tout élément N non congru à 0 admet un inverse pour la multiplication, c’est-à-dire une famille de nombres (égaux modulo b) qui, multipliés par N, donnent un nombre congru à 1 modulo b. Par exemple, si b = 5, on se convainc aisément que 1 et 4 sont leur propre inverse : 1 $d G l t Z X M =$ 1 ≡ 1 [5], 4 $d G l t Z X M =$ 4 ≡ 16 ≡ 1 [5]. De même, 2 et 3 sont inverses l’un de l’autre : 2 $d G l t Z X M =$ 3 ≡ 6 ≡ 1 [5].

Révisez vos classiques !

Pour savoir si un entier est divisible par 2 ou 5, les propriétés des congruences ne sont même pas nécessaires. Un nombre N est divisible par 2 si son chiffre des unités u est pair. En effet, en séparant le chiffre des unités u de N, et N, amputé de ce chiffre, que l’on nomme d, alors N = 10 d + u. Comme 10 est un multiple de 2, N est divisible par 2 si, et seulement si, u l’est, c’est-à-dire est pair.

De même pour la divisibilité par 5. Comme 10 est aussi multiple de 5, N est divisible par 5 si, et seulement si, u l’est, c’est-à-dire est égal à 0 ou 5. Avec le vocabulaire des congruences, N ≡ u \[2\] et N ≡ u \[5\]. On reconnaît donc la divisibilité de N par 2, ou par 5, à celle de son chiffre des unités.