ARITMETICA E ALGEBRA KEYWORDS K m massimo comune divisore / Greatest Common Divisor (GCD) minimo comune multiplo / Least Common Multiple (LCM) Talvolta è necessario individuare i divisori o i multipli comuni a due numeri naturali. In particolare, come già sai, è spesso utile trovare il massimo comune divisore (MCD) di due numeri, che è il più grande tra i loro divisori comuni, o il loro minimo comune multiplo (mcm), che è il più piccolo tra i loro multipli. Due numeri il cui massimo comune divisore è 1, si dicono primi tra loro. Per esempio, 14 e 15 sono primi tra loro perché il MCD (14, 15) = 1. Ricorda che si definisce numero primo qualunque numero naturale diverso da 0 e da 1 divisibile soltanto per sé stesso e per 1. Sono numeri primi 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, Per determinare il MCD e il mcm tra due o più numeri naturali è necessario scomporli in fattori primi (scrivere i numeri come prodotto di numeri primi) e poi: Q il MCD si ottiene moltiplicando i numeri primi comuni a tutte le scomposizioni (tutti i fattori primi comuni considerati una sola volta con il minimo esponente); se non ci sono numeri primi comuni e quindi divisori diversi da 1 in comune, cioè se i numeri considerati sono primi tra loro, il MCD = 1; Q il mcm si ottiene moltiplicando tutti i fattori primi comuni e non comuni considerati una sola volta con il massimo esponente. Per esempio: MCD (16, 24) = 4 FISSA I CONCETTI Q Q Q a è multiplo di b se a = b n a è sottomultiplo di b se b = n a b è divisore di a se a = b n, con b 0 mcm (16, 24) = 48 MCD (4, 25) = 1 mcm (4, 25) = 100 perché 16 = 2 2 2 2 = 24 24 = 2 2 3 = 22 3 i divisori comuni sono 2 2 = 22 = 4 perché 16 = 24, 24 = 22 3 i divisori comuni e non comuni sono 24 3 = 48 perché 4 = 22, 25 = 52 non ci sono divisori comuni perché i divisori comuni e non comuni sono 22 52 = 100 1.4 L operazione modulo KEYWORDS K resto / rest re Tra i numeri naturali possiamo anche eseguire l operazione modulo, indicata con mod. Dati due numeri a e b, con b 0, l operazione a mod b dà come risultato il resto della divisione intera di a per b: a mod b = r con r = resto di a div b Per esempio: 13 mod 3 = 1 perché 13 div 3 = 4 con resto 1. ATTENZIONE! A L L operazione modulo tra due numeri naturali richiede il calcolo della divisione intera. Per questo il secondo numero deve essere diverso da 0. esempio O Calcola. a. 256 div 4 = 64, con resto 0; quindi 256 mod 4 = 0 b. 33 div 7 = 4, con resto 5; quindi 33 mod 7 = 5 c. 375 div 11 = 34, con resto 1; quindi 375 mod 11 = 1 Utilizziamo quotidianamente l operazione modulo perché è alla base della «aritmetica dell orologio . Se adesso il tuo orologio segnasse le 10 del mattino, che ora segnerebbe fra 67 ore? Addizionando abbiamo: 10 + 67 = 77 = 24 + 24 + 24 + 5 FISSA I CONCETTI mod: è il resto della divisione intera. L orologio segnerebbe quindi le ore 5 del mattino, ma di 3 giorni dopo. Usando le operazioni mod e div otteniamo lo stesso risultato, infatti: 77 mod 24 = 5 e 78 77 div 24 = 3, con resto 5