Conoscere i divisori... senza dividere

Fin dalla scuola primaria sappiamo riconoscere se un numero è divisibile per 2, 3, 4, 5, 6, 8, 10 o 11. Per divisori come 7, 13, 17, 23, 29… o perfino 271, invece, sembra un esercizio da funamboli. Eppure esistono modi per riuscirci. Passiamo dunque in rassegna, dai più semplici ai più complessi, i criteri di divisibilità nel regno dei numeri interi. Ora, quando si parla di divisibilità, la nozione di congruenza (vedi riquadro) facilita molto spesso il compito.

Avete detto «congruenze»?

L’esistenza stessa del numero r permette di definire sull’insieme ℤ dei numeri interi una relazione di equivalenza: a e a’ si dicono equivalenti se hanno lo stesso resto nella divisione per b. Si dice anche: «a è congruo a a’ modulo b», e si scrive a ≡ a’ [ b ]. Si ottiene così una partizione di $m a t h b b Z$ in b parti disgiunte, dette classi: quelle dei b resti possibili nella divisione per b. Ogni classe corrisponde a un valore del resto, da 0 a b – 1; le indichiamo con $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 relazione «è congruo a» è compatibile con l’addizione, la sottrazione, la moltiplicazione e l’elevamento a potenza.

L’applicazione che associa a un intero il suo valore modulo b è un omomorfismo: il resto della somma di due numeri è infatti congruo, modulo b, alla somma dei loro resti; analogamente, il resto di un prodotto è congruo, modulo b, al prodotto dei resti.

In particolare, con il linguaggio delle congruenze si esprime la nozione di divisibilità: «a è divisibile per b» equivale a dire che il resto della divisione di a per b è nullo, e si scrive a ≡ 0 [ b ].

Quando b è un numero primo, si aggiungono nuove proprietà. Ogni elemento N non congruo a 0 ammette un inverso moltiplicativo, cioè una classe di numeri congrui modulo b che, moltiplicati per N, danno un numero congruo a 1 modulo b. Per esempio, se b = 5, si vede facilmente che 1 e 4 sono inversi di sé stessi: 1 $d G l t Z X M =$ 1 ≡ 1 [5], 4 $d G l t Z X M =$ 4 ≡ 16 ≡ 1 [5]. Analogamente, 2 e 3 sono inversi l’uno dell’altro: 2 $d G l t Z X M =$ 3 ≡ 6 ≡ 1 [5].

Ripassate i classici!

Per sapere se un intero è divisibile per 2 o per 5, le proprietà delle congruenze non sono nemmeno necessarie. Un numero N è divisibile per 2 se la sua cifra delle unità u è pari. Infatti, separando da N la cifra delle unità u e chiamando d il numero N privato di tale cifra, si ha N = 10 d + u. Poiché 10 è un multiplo di 2, N è divisibile per 2 se e solo se lo è u, cioè se è pari.

Lo stesso vale per la divisibilità per 5. Poiché 10 è anche multiplo di 5, N è divisibile per 5 se e solo se lo è u, cioè se è uguale a 0 o a 5. Nel linguaggio delle congruenze, N ≡ u \[2\] e N ≡ u \[5\]. La divisibilità di N per 2 o per 5 si riconosce dunque da quella della sua cifra delle unità.