Indice
La teoria dei numeri
La teoria dei numeri, nella classificazione dei problemi olimpici, si occupa dello studio delle proprietà dei numeri interi; e quindi di divisibilità, primalità, ed equazioni a valori interi.
La divisione con resto
Tra i numeri interi si possono svolgere le operazioni di somma, sottrazione e prodotto senza incontrare particolari difficoltà, nei modi noti a tutti. Più delicato è il problema della divisione, poiché è in generale impossibile svolgerla, se non si vuole sconfinare nei numeri razionali. Viene quindi introdotta una nuova operazione, la divisione con resto, per esprimere la divisione tra soli numeri interi.
Dati gli interi a ≠ 0 e b, la divisione con resto di b per a associa a questi due numeri gli interi q ed r tali che:
b = a ·q + r, 0 ≤ r < a
Qualunque siano a e b, gli interi q ed r che soddisfano queste relazioni esistono e sono unici;q è detto quoziente ed r è detto resto.
Per meglio comprendere il significato della divisione con resto è utile immaginarsi l’operazione in un modo alternativo. L’intero q può essere ottenuto come il risultato della divisione esatta di b per a arrotondato per difetto, e considerando che la divisione esatta richiede di trovare il numero q tale che aq = b, il resto r rappresenta intuitivamente la misura dell’errore commesso nell’arrotondamento per difetto: infatti r = b − aq, cioè quanto i due lati dell’uguaglianza precedente discostano tra loro.
Dato che la divisione con resto restituisce due valori, per indicarla vengono usate due distinte scritture. Mantenendo le lettere della definizione, avremo che b div a = q restituisce il quoziente (divisione intera), mentre b mod a = r restituisce il resto (modulo).
ESEMPIO 1
7 div 3 = 2,
7 mod 3 = 1.
Infatti 7 = 6 + 1 = 3 · 2 + 1, come nella definizione. Più intuitivamente 7/3 ≅ 2.33 da cui per difetto q = 2, e infine il resto è dato da r = 7 − 3 · 2 = 7 − 6 = 1, l’errore commesso.
ESEMPIO 2
37569 div 100 = 375, 37569 mod 100 = 69
ESEMPIO 3
60 div 7 = 8, 60 mod 7 = 4
−60 div 7 = −9, −60 mod 7 = 3
−60 div −7 = 9, −60 mod −7 = 3
60 div −7 = −8, 60 mod −7 = 4
Divisibilità e primalità
Si dice che a divide b, o che a è divisore di b, o che b è multiplo di a (in simboli a | b) se effettuando la divisione con resto di b per a si ottiene che r = 0. Più esplicitamente, a | b se esiste un intero q tale che b = aq. Notare che tra i divisori di un numero b sono sempre presenti 1 e b stesso e che tutti i numeri dividono lo 0. Com’è facile verificare, la caratteristica
di “essere multipli” si preserva con le combinazioni lineari: in altre parole se a,b sono multipli di d allora h · a + k ·b è anche multiplo di d per qualsiasi scelta di h,k interi.
Si dice inoltre che p è un numero primo se ogniqualvolta divide un prodotto divide anche almeno uno dei fattori, cioè
p | ab ⇒ p | a∨p | b.
Ai nostri fini, questa definizione è equivalente a quella più nota, secondo cui un numero è primo se non ha divisori all’infuori di 1 e se stesso.
Notare che 1 non è considerato un numero primo.
I numeri primi hanno un ruolo particolare nella teoria dei numeri, soprattutto poiché ogni intero è scrivibile in modo unico come prodotto di potenze di numeri pi primi distinti:
Come verificare se un numero è primo
Verificare se un numero a è primo o meno è un problema complesso, tuttavia sono note alcune strategie per farlo.
Una prima strategia (utile anche per trovare la fattorizzazione di un numero non primo) consiste nel dividere il numero a per tutti i primi noti in ordine crescente, fino ad arrivare a √a. A quel punto, se nessuno dei primi che abbiamo provato era un divisore esatto di a, allora a è certamente primo (infatti se possiede un divisore d >√a, possiede anche il divisore a/d<√a).
La seconda strategia (nota con il nome di crivello di Eratostene) serve invece per trovare tutti i primi da 2 fino a un certo limite prefissato L. Si scrivono in tabella tutti i numeri da 2 a L, poi si parte da 2, si dice che è primo e si cancellano dalla tabella tutti i suoi multipli (che certamente non sono primi). A questo punto si prende il successivo numero non ancora cancellato (che è il 3), e si cancellano tutti i suoi multipli, e così via cancellando i multipli di tutti i primi che si trovano con questo procedimento. I numeri primi, alla fine, saranno proprio quelli che non sono stati cancellati.
Il crivello di Eratostene in Python
(70)