1.9 Divisibilità e numeri primi

1.9.1 Quoziente intero e resto

La divisione esatta nei numeri naturali, \(m\) e \(n\), non è sempre possibile: si può fare solo se \(m\) è multiplo di \(n\). Con i numeri naturali però è sempre possibile eseguire la divisione con il resto. La divisione con resto è una funzione che dà due risultati: il quoziente e il resto. Questa è una funzione che ha due argomenti e per risultato una coppia ordinata di numeri.

Definizione 1.10:

Dati due numeri naturali \(m\) e \(n\), con \(n\neq ~0\), esistono due numeri \(q\) e \(r\) con \(0 \leqslant r < n\) tali che: \[m = n \cdot q + r\] \(q\) si dice quoziente e \(r\) si dice resto della divisione.

Esempio 1.11:

Calcola: \(25:7\)

Nella divisione con resto tra 25 e 7 si ha quoziente 3 (infatti \(7 \cdot 3 = 21\), mentre \(7 \cdot 4 = 28\) supera il dividendo) e resto 4 (infatti \(3 \cdot 7 + 4 = 25\)).

Esempio 1.12:

Alcune semplici divisioni con il resto:

Un’operazione che dà due risultati a volte è scomoda quindi i matematici hanno ricavato, dalla divisione con resto, due nuove operazioni: la divisione intera e il resto modulo o modulo.

Definizione 1.11:

Dati due numeri naturali \(m\) e \(n\), con \(n \neq 0\), la divisione intera dà come risultato il più grande numero intero \(q\) tale che: \[q \cdot n \leqslant m\] \(q\) si dice quoziente intero della divisione.

Esempio 1.13:

Alcune semplici divisioni intere:

Definizione 1.12:

Dati due numeri naturali \(m\) e \(n\), con \(n\neq ~0\), l’operazione che restituisce il resto della divisione intera tra \(m\) e \(n\) si chiama modulo di \(m\) rispetto a \(n\) e viene indicata con \(m\, \Mod {n}\).

Esempio 1.14:

Alcuni esempi di resto delle divisioni:

1.9.2 Algoritmo della divisione in \(\N \)

Ripassiamo l’algoritmo della divisione tra numeri naturali; questo algoritmo risulterà particolarmente utile nel seguito.

Vediamo assieme i vari passi dell’algoritmo:

1.
Non ci sono abbastanza migliaia per dividerle per 7, ma ci sono 15 centinaia. Il 7 nelle 15 centinaia è contenuto 2 centinaia di volte:
2.
riporto a fianco del resto delle centinaia la cifra delle decine, ripeto lo stesso procedimento calcolando quante decine di volte 7 è contenuto in 12 decine e calcolo sotto alle decine il resto ottenuto: 5;
3.
riporto a fianco il numero di unità, ripeto lo stesso meccanismo ottenendo alla fine il resto di unità.

In definitiva, nel 1523 il 7 è contenuto 217 volte con il resto di 4.:
\(1523:7 \quad \srarrow \quad Q=217 \text { e } R=4\) Infatti: \(217 \cdot 7 + 4 = 1519 + 4 = 1523\) e: \(4 \leqslant 7\)

Alcuni altri esempi:

1.9.3 Divisori, numeri primi, numeri composti

Definizione 1.13:

Il numero \(n\) si dice divisore di \(m\), e \(m\) multiplo di \(n\), se il resto della divisione intera è zero: \[m\, \Mod n = 0\]

Prima di proseguire, disegna nel quaderno la seguente tabella e completala.

Nella prima colonna scrivi i numeri fino al 50, nella seconda scrivi tutti i divisori di quel numero ordinati dal minore al maggiore, nella terza scrivi quanti sono i divisori.




numero

divisori

numero di divisori



0

tutti i numeri naturali

\(\infty \)



1

1

1



2

1, 2

2



3

1, 3

2



4

1, 2, 4

3



5

1, 5

2






50




(a)
Quale sarà il prossimo numero con un numero dispari di divisori? (facile)
(b)
Quale sarà il prossimo numero con esattamente 2 divisori? (difficile)

Guardando la tabella dei divisori si può osservare che ogni numero è divisibile per 1 e per se stesso. Poi può avere altri divisori, questi altri divisori si chiamano divisori propri.

Definizione 1.14:

Chiamiamo divisore proprio di un numero un divisore diverso dal numero stesso e dall’unità.

Per quanto riguarda il numero dei divisori possiamo anche osservare che due numeri sono particolari:

Dopo queste osservazioni possiamo dare le seguenti definizioni:

Definizione 1.15:

Un numero si dice primo se ha esattamente due divisori.

Definizione 1.16:

Un numero si dice composto se ha più di due, ma non infiniti, divisori.

Osservazioni 1.8:

Ma quanti sono i numeri primi? La risposta a questa domanda venne data da Euclide con il seguente teorema che porta il suo nome:

Teorema 1.2 (di Euclide):

I numeri primi sono infiniti.

La dimostrazione è ingegnosa ed è semplice: cercala e presentala ai tuoi compagni.

Criteri di divisibilità

Per vedere se un numero divide un altro basta eseguire la divisione e osservare se si ottiene un resto uguale a zero. Ma questo non sempre è comodo da fare, i matematici hanno scoperto dei trucchi per capire se un numero divide un altro senza dover eseguire la divisione: sono i criteri di divisibilità. Di seguito sono riportati i criteri relativi ai primi numeri naturali.

0: 

Nessun numero è divisibile per 0.

1: 

Tutti i numeri sono divisibili per 1.

2: 

0, 2, 4, 6, 8 sono divisibili per 2 e un numero è divisibile per 2 se e solo se il numero formato dalla sua ultima cifra è divisibile per 2.

3: 

0, 3, 6, 9 sono divisibili per 3 e un numero è divisibile per 3 se e solo se la somma delle sue cifre è un numero divisibile per 3.

4: 

0, 4, 8, 12, 16, 20, 24, 28, 32, 36, …, 96, sono divisibili per 4 e un numero è divisibile per 4 se e solo se il numero formato dalle sue ultime 2 cifre, è divisibile per 4.

5: 

0, 5 sono divisibili per 5 e un numero è divisibile per 5 se e solo se il numero formato dalla sua ultima cifra è divisibile per 5.

6: 

Un numero è divisibile per 6 se è divisibile per 2 e per 3.

7: 

0, 7 sono divisibili per 7 e un numero maggiore di 10 è divisibile per 7 se la differenza, in valore assoluto, fra il numero ottenuto togliendo la cifra delle unità e il doppio della cifra delle unità è divisibile per 7.
Il numero 273 è divisibile per 7, infatti \( \valass {27 -2 \cdot 3} = 21\) che è multiplo di 7.
Il numero 887 non è divisibile per 7, infatti \(\valass {88 -2 \cdot 7}= 74\) che non è divisibile per 7.

8: 

0, 8, 16, 24, 32, …, 200, …, 992, sono divisibili per 8 e un numero è divisibile per 8 se e solo se il numero formato dalle sue ultime 3 cifre, è divisibile per 8.

9: 

0, 9 sono divisibili per 9, e un numero è divisibile per 9 se e solo se la somma delle sue cifre è un numero è divisibile per 9.

10: 

0 è divisibile per 10 e un numero è divisibile per 10 se e solo se il numero formato dalla sua ultima cifra è divisibile per 10.

11: 

0 è divisibile per 11 e un numero è divisibile per 11 se e solo se la differenza, in valore assoluto, fra la somma delle cifre di posto pari e la somma delle cifre di posto dispari è un numero divisibile per 11.
Il numero 8261 è divisibile per 11, infatti \(\valass {(8+6)-(2+1)} = 11\);
Il numero 887 non è divisibile per 11, infatti \(\valass {8-(8+7)}=~7\).

12: 

Un numero è divisibile per 12 se è divisibile per 3 e per 4.

un numero qualunque: 

Un numero \(a\) è divisibile per un numero \(d\) se e solo se \(a - n \cdot d\) è divisibile per \(d\) (dove \(n\) è un numero naturale qualsiasi).
Il numero 253 è divisibile per 23 perché \(253 - 10 \cdot 23 = 253 - 230 = 23\) che è divisibile per 23.
Il numero 1894 è divisibile per 17 se e solo se lo è anche \(1894 - 100 \cdot 17 = 1894 - 1700 = 194\) che è divisibile per 17 se e solo se lo è anche \(194 - 10 \cdot 17 = 194 - 170 = 24\). Poiché 24 non è divisibile per 17 non lo sarà neppure 1894.