\chapter{Divisibilità MCD e mcm}\label{cap:AA-004} \citazioneinizio{% Si dice che un numero misura un altro numero quando il primo, contato un numero di volte, lo riproduce esattamente.% }{Euclide, \emph{Elementi}, libro VII, def.\ 3 (\textsc{iii} sec.\,a.C.)} % ============================================================ \section{Introduzione motivazionale}\label{sec:aa-004-01-introduzione-motivazionale} % ============================================================ Quando dividiamo $12$ per $3$ otteniamo un risultato intero, $4$, senza ``avanzi''. Quando invece dividiamo $14$ per $3$, qualcosa avanza: il quoziente è $4$, ma rimane un resto di $2$. La distinzione fra divisioni ``esatte'' e divisioni ``con resto'' è il punto di partenza dell'\emph{aritmetica modulare} e di tutta la teoria dei numeri. In questo capitolo studiamo a fondo questa distinzione. Introdurremo la relazione di \emph{divisibilità} fra numeri interi, alcuni \emph{criteri} pratici per decidere rapidamente se un numero è divisibile per un altro (per $2$, $3$, $5$, $9$, $11$, ecc.), il \emph{massimo comune divisore} (MCD) e il \emph{minimo comune multiplo} (mcm) di due o più numeri, e infine l'\emph{algoritmo di Euclide} per calcolare l'MCD in modo veloce anche per numeri grandi. Queste nozioni saranno la chiave per ridurre le frazioni ai minimi termini (capitolo \ref{cap:AA-006}), per semplificare scomposizioni e raccoglimenti (capitolo \ref{cap:AA-013}), e per discutere la \emph{fattorizzazione unica} dei numeri naturali (capitolo \ref{cap:AA-005}). % ============================================================ \section{Divisori e multipli}\label{sec:aa-004-01-divisori-e-multipli} % ============================================================ \begin{definizione}[Divisibilità] Siano $a,b\in\Z$ con $b\neq 0$. Si dice che $b$ \textbf{divide} $a$ (oppure: $a$ \textbf{è multiplo} di $b$) se esiste un intero $k\in\Z$ tale che $a=b\cdot k$. Si scrive \[ b\mid a \quad\text{(``$b$ divide $a$'')}. \] Se invece nessun $k$ realizza l'uguaglianza, si scrive $b\nmid a$. \end{definizione} \begin{esempio} $3\mid 12$ perché $12=3\cdot 4$; $3\nmid 14$ perché non esiste $k\in\Z$ con $14=3k$. Inoltre $(-3)\mid 12$ (con $k=-4$) e $5\mid 0$ (con $k=0$): \textbf{ogni intero non nullo divide $0$}. \end{esempio} \begin{nota}[Convenzioni] \begin{itemize} \item Per ogni $a\in\Z$, $1\mid a$ e $-1\mid a$. \item Per ogni $a\in\Z\setminus\{0\}$, $a\mid a$ e $a\mid -a$. \item Il caso $b=0$ è escluso: ``divisione per zero'' non è definita. Equivalentemente, $0\nmid a$ per ogni $a$. \end{itemize} \end{nota} \begin{teorema}[Proprietà elementari della divisibilità] Per ogni $a,b,c\in\Z$: \begin{itemize} \item se $a\mid b$ e $b\mid c$, allora $a\mid c$ \emph{(transitiva)}; \item se $a\mid b$ e $a\mid c$, allora $a\mid(b+c)$ e $a\mid(b-c)$; \item se $a\mid b$, allora $a\mid b\cdot c$ per ogni $c\in\Z$; \item se $a\mid b$ e $b\neq 0$, allora $|a|\le|b|$. \end{itemize} \end{teorema} \textit{Dimostrazione (idea).} Tutte si verificano sostituendo le definizioni. Ad esempio, se $a\mid b$ (cioè $b=a k$) e $a\mid c$ (cioè $c=a h$), allora $b+c=a(k+h)$, dunque $a\mid b+c$. \begin{definizione}[Divisori e multipli di un numero] Per $n\in\N^*$, l'insieme dei \textbf{divisori} (positivi) di $n$ è \[ D(n)=\{\,d\in\N^*\mid d\mid n\,\}. \] L'insieme dei \textbf{multipli} (positivi) di $n$ è \[ M(n)=\{\,k\cdot n \mid k\in\N^*\,\}. \] $D(n)$ è \emph{finito} ($D(12)=\{1,2,3,4,6,12\}$); $M(n)$ è \emph{infinito} ($M(3)=\{3,6,9,12,\ldots\}$). \end{definizione} \begin{teorema}[Divisione euclidea in $\Z$] Per ogni $a\in\Z$ e ogni $b\in\N^*$, esistono e sono unici $q,r\in\Z$ tali che \[ a = b\cdot q + r, \qquad 0\le r < b. \] Il numero $q$ si dice \textbf{quoziente} e $r$ \textbf{resto} della divisione di $a$ per $b$. \end{teorema} \textit{Dimostrazione (idea).} L'idea è di sottrarre $b$ ripetutamente da $a$ (o sommarlo, se $a<0$) finché si rientra nell'intervallo $[0,b-1]$: il numero di sottrazioni è $q$, ciò che resta è $r$. L'unicità si dimostra per assurdo supponendo due rappresentazioni e sottraendole. \begin{esempio} Dividendo $a=47$ per $b=5$: $47=5\cdot 9+2$, quoziente $q=9$, resto $r=2$. La condizione $0\le 2<5$ è verificata. Dividendo $a=-47$ per $b=5$: $-47=5\cdot(-10)+3$, quoziente $q=-10$, resto $r=3$. \emph{Non} si scrive $-47=5\cdot(-9)-2$ perché si vuole il resto positivo. \end{esempio} \begin{nota}[Divisibilità in termini di resto] $b\mid a$ se e solo se la divisione euclidea di $a$ per $b$ ha resto $r=0$. È la definizione operativa usata in tutti i criteri di divisibilità che seguono. \end{nota} \begin{figure}[H] \centering \begin{tikzpicture}[scale=0.85] % Visualizzazione divisione euclidea 47:5 = 9 resto 2 % 47 quadretti, raggruppati in 9 gruppi da 5 + 2 \foreach \g in {0,1,2,3,4,5,6,7,8} { \foreach \c in {0,1,2,3,4} { \draw[BLU, fill=BLU!20] ({\g*1.3+\c*0.25}, 0) rectangle ({\g*1.3+\c*0.25+0.20}, 0.30); } } % I 2 di resto, separati \foreach \c in {0,1} { \draw[ROSSO, fill=ROSSO!30] ({9*1.3+\c*0.25}, 0) rectangle ({9*1.3+\c*0.25+0.20}, 0.30); } % etichette \node[BLU, below] at (5.0, -0.2) {\small 9 gruppi da 5 (quoziente $q=9$)}; \node[ROSSO, below] at (11.95, -0.2) {\small resto $r=2$}; \node[above] at (6, 0.6) {$47 = 5\cdot 9 + 2$}; \end{tikzpicture} \caption{Visualizzazione geometrica della divisione euclidea: i $47$ quadretti si raggruppano in $9$ gruppi da $5$ (quoziente, in blu) più $2$ quadretti che ``avanzano'' (resto, in rosso). In simboli: $47 = 5\cdot 9 + 2$.} \label{fig:aa-004-divisione-euclidea} \end{figure} % ============================================================ \section{Criteri di divisibilità}\label{sec:aa-004-02-criteri-di-divisibilita} % ============================================================ Per molti divisori piccoli esistono \emph{criteri}: regole rapide che permettono di stabilire la divisibilità senza eseguire la divisione completa. \begin{teorema}[Criteri di divisibilità] Sia $n$ un numero naturale. \begin{itemize} \item \emph{Per $2$}: $2\mid n$ se e solo se l'ultima cifra di $n$ è pari (cioè $0,2,4,6,8$). \item \emph{Per $5$}: $5\mid n$ se e solo se l'ultima cifra di $n$ è $0$ o $5$. \item \emph{Per $10$}: $10\mid n$ se e solo se l'ultima cifra di $n$ è $0$. \item \emph{Per $3$}: $3\mid n$ se e solo se la somma delle cifre di $n$ è divisibile per $3$. \item \emph{Per $9$}: $9\mid n$ se e solo se la somma delle cifre di $n$ è divisibile per $9$. \item \emph{Per $4$}: $4\mid n$ se e solo se il numero formato dalle ultime due cifre di $n$ è divisibile per $4$. \item \emph{Per $25$}: $25\mid n$ se e solo se le ultime due cifre di $n$ sono $00$, $25$, $50$ o $75$. \item \emph{Per $11$}: $11\mid n$ se e solo se la differenza fra la somma delle cifre di posto dispari e la somma delle cifre di posto pari (partendo da destra) è divisibile per $11$ (incluso $0$). \end{itemize} \end{teorema} \textit{Dimostrazione (criterio del $3$).} Sia $n=a_k\cdot 10^k+a_{k-1}\cdot 10^{k-1}+\cdots+a_1\cdot 10+a_0$. Poiché $10\equiv 1\pmod 3$, ogni $10^i\equiv 1\pmod 3$. Allora \[ n \equiv a_k+a_{k-1}+\cdots+a_1+a_0 \pmod 3, \] cioè $n$ e la somma delle sue cifre danno lo stesso resto nella divisione per $3$. In particolare $3\mid n$ se e solo se $3$ divide la somma delle cifre. La dimostrazione del criterio del $9$ è identica (anche $10\equiv 1\pmod 9$). \begin{esempio}[Applicazione dei criteri] Stabilire i divisori di $n=\num{37 845}$ tra $\{2,3,4,5,9,10,11\}$. \textit{Soluzione.} \begin{itemize} \item L'ultima cifra è $5$: $5\mid n$, ma $2\nmid n$ e $10\nmid n$. \item Somma cifre: $3+7+8+4+5=27$; $3\mid 27$ e $9\mid 27$, dunque $3\mid n$ e $9\mid n$. \item Ultime due cifre: $45$; $4\nmid 45$, dunque $4\nmid n$. \item Differenza ``cifre alternate'' (da destra): $(5+8+3)-(4+7)=16-11=5$; $11\nmid 5$, dunque $11\nmid n$. \end{itemize} Divisori di $n$ nell'insieme proposto: $\{3,5,9\}$. \end{esempio} % ============================================================ \section{MCD: definizione e calcolo}\label{sec:aa-004-03-mcd-definizione-e-calcolo} % ============================================================ \begin{definizione}[Massimo comune divisore] Dati $a,b\in\N^*$, il \textbf{massimo comune divisore} di $a$ e $b$, indicato $\mcd(a,b)$ o $(a,b)$, è il più grande naturale che divide sia $a$ sia $b$: \[ \mcd(a,b) = \max\bigl(D(a)\cap D(b)\bigr). \] \end{definizione} \begin{esempio} $D(12)=\{1,2,3,4,6,12\}$, $D(18)=\{1,2,3,6,9,18\}$. Divisori comuni: $\{1,2,3,6\}$. Il massimo è $6$: $\mcd(12,18)=6$. \end{esempio} \begin{definizione}[Numeri coprimi] Due numeri $a,b\in\N^*$ si dicono \textbf{coprimi} (o \emph{primi tra loro}) se $\mcd(a,b)=1$. \end{definizione} \begin{esempio} $\mcd(8,15)=1$, dunque $8$ e $15$ sono coprimi. Lo sono anche $7$ e $20$, ma non $6$ e $10$ (che hanno $\mcd=2$). \end{esempio} \begin{procedura}[MCD per scomposizione in fattori primi] Per calcolare $\mcd(a,b)$: \begin{enumerate} \item Si scrive ciascuno dei due numeri come prodotto di fattori primi (capitolo \ref{cap:AA-005}). \item Si prendono i fattori \emph{comuni} ai due (cioè quelli che compaiono in entrambe le scomposizioni), \emph{ciascuno con l'esponente più piccolo}. \item Il prodotto di questi fattori (con i loro esponenti minimi) è $\mcd(a,b)$. \end{enumerate} \end{procedura} \begin{esempio} Calcolare $\mcd(72, 60)$. \textit{Soluzione.} $72 = 2^3\cdot 3^2$,\ $60=2^2\cdot 3\cdot 5$. Fattori comuni: $2$ e $3$. Esponenti minimi: $2^2$ e $3^1$. Quindi \[ \mcd(72,60) = 2^2\cdot 3 = 12. \] \end{esempio} % ============================================================ \section{mcm: definizione e calcolo}\label{sec:aa-004-04-mcm-definizione-e-calcolo} % ============================================================ \begin{definizione}[Minimo comune multiplo] Dati $a,b\in\N^*$, il \textbf{minimo comune multiplo} di $a$ e $b$, indicato $\mcm(a,b)$ o $[a,b]$, è il più piccolo naturale non nullo che è multiplo sia di $a$ sia di $b$: \[ \mcm(a,b) = \min\bigl(M(a)\cap M(b)\bigr). \] \end{definizione} \begin{esempio} $M(4)=\{4,8,12,16,20,\ldots\}$, $M(6)=\{6,12,18,24,\ldots\}$. Multipli comuni: $\{12,24,36,\ldots\}$. Il minimo è $12$: $\mcm(4,6)=12$. \end{esempio} \begin{procedura}[mcm per scomposizione in fattori primi] Per calcolare $\mcm(a,b)$: \begin{enumerate} \item Si scrivono i due numeri come prodotto di fattori primi. \item Si prendono \emph{tutti} i fattori primi che compaiono in almeno una delle due scomposizioni, \emph{ciascuno con l'esponente più grande}. \item Il prodotto di questi fattori (con esponenti massimi) è $\mcm(a,b)$. \end{enumerate} \end{procedura} \begin{esempio} Calcolare $\mcm(72, 60)$. \textit{Soluzione.} $72=2^3\cdot 3^2$,\ $60=2^2\cdot 3\cdot 5$. Fattori che compaiono almeno in una: $2$, $3$, $5$. Esponenti massimi: $2^3$, $3^2$, $5^1$. Quindi \[ \mcm(72,60) = 2^3\cdot 3^2\cdot 5 = 360. \] \end{esempio} \begin{teorema}[Relazione fra MCD e mcm] Per ogni $a,b\in\N^*$: \[ \mcd(a,b)\cdot\mcm(a,b) = a\cdot b. \] \end{teorema} \textit{Dimostrazione (idea).} Per ogni primo $p$ che compare nelle due scomposizioni, sia $\alpha$ il suo esponente in $a$ e $\beta$ quello in $b$. L'esponente di $p$ in $\mcd(a,b)$ è $\min(\alpha,\beta)$, quello in $\mcm(a,b)$ è $\max(\alpha,\beta)$. La loro somma è $\alpha+\beta$, che è proprio l'esponente di $p$ in $a\cdot b$. \begin{formulabox} \[ \mcm(a,b) = \dfrac{a\cdot b}{\mcd(a,b)}. \] \end{formulabox} Questa identità è utilissima: una volta calcolato $\mcd$, $\mcm$ si ottiene senza ricalcolare le scomposizioni. \begin{esempio}[Conferma] Con $a=72$, $b=60$: $\mcd\cdot\mcm = 12\cdot 360 = 4320$, e $a\cdot b = 72\cdot 60 = 4320$. \checkmark \end{esempio} \begin{figure}[H] \centering \begin{tikzpicture} % Diagramma Eulero: D(12) e D(18) con divisori comuni evidenziati \draw[thick, BLU, fill=BLU!10] (-1.2, 0) ellipse (2.4cm and 1.5cm); \draw[thick, VERDE, fill=VERDE!10] (1.2, 0) ellipse (2.4cm and 1.5cm); \node[BLU] at (-3.2, 1.2) {$D(12)$}; \node[VERDE] at ( 3.2, 1.2) {$D(18)$}; % Divisori esclusivi \node at (-2.0, 0.4) {$4$}; \node at (-2.0,-0.4) {$12$}; \node at ( 2.0, 0.4) {$9$}; \node at ( 2.0,-0.4) {$18$}; % Divisori comuni nella zona intersezione \node[BLU!70!black] at (0, 0.6) {$1$}; \node[BLU!70!black] at (-0.4, 0) {$2$}; \node[BLU!70!black] at ( 0.4, 0) {$3$}; \node[BLU!70!black] at (0, -0.6) {$6 \;\leftarrow$ \small MCD}; % Etichetta zona comune \node[GRIGIO] at (0, -2.0) {\small divisori comuni: $\{1,2,3,6\}$, max $= 6 = \mcd(12,18)$}; \end{tikzpicture} \caption{Lettura insiemistica del massimo comune divisore: nell'intersezione $D(12)\cap D(18)$ ci sono i divisori comuni dei due numeri; il \emph{massimo} di questi è $\mcd(12,18)=6$. Specularmente, $\mcm(12,18)$ è il \emph{minimo} dell'intersezione di $M(12)$ e $M(18)$.} \label{fig:aa-004-mcd-eulero} \end{figure} % ============================================================ \section{Algoritmo di Euclide}\label{sec:aa-004-05-algoritmo-di-euclide} % ============================================================ Per numeri grandi, scomporre in fattori primi può essere lungo. Esiste un metodo molto più rapido per calcolare l'MCD, noto fin dall'antichità: l'\emph{algoritmo di Euclide}. Si basa su una sola osservazione, di una semplicità sorprendente. \begin{teorema}[Lemma di Euclide] Per ogni $a,b\in\N^*$ con $a\ge b$, se $r$ è il resto della divisione di $a$ per $b$, allora \[ \mcd(a,b) = \mcd(b,r). \] In particolare, se $r=0$, allora $\mcd(a,b)=b$. \end{teorema} \textit{Dimostrazione (idea).} Scriviamo $a=bq+r$. Un divisore comune di $a$ e $b$ deve dividere anche $r=a-bq$ (proprietà della divisibilità); viceversa, un divisore comune di $b$ e $r$ divide anche $a=bq+r$. Quindi $D(a)\cap D(b) = D(b)\cap D(r)$, e in particolare i massimi coincidono. \begin{procedura}[Algoritmo di Euclide] Per calcolare $\mcd(a,b)$ con $a\ge b > 0$: \begin{enumerate} \item Si esegue la divisione $a:b$, ottenendo quoziente $q$ e resto $r$. \item Se $r=0$, l'MCD è $b$, e ci si ferma. \item Altrimenti si pone $a\leftarrow b$, $b\leftarrow r$ e si ripete dal punto 1. \end{enumerate} L'algoritmo termina in un numero finito di passi perché i resti formano una successione strettamente decrescente di numeri naturali. \end{procedura} \begin{esempio}[Algoritmo di Euclide passo-passo] Calcolare $\mcd(252, 198)$. \textit{Soluzione.} Divisioni successive: \begin{align*} 252 &= 198\cdot 1 + 54 \\ 198 &= 54\cdot 3 + 36 \\ 54 &= 36\cdot 1 + 18 \\ 36 &= 18\cdot 2 + 0 \end{align*} L'ultimo resto non nullo è $18$. Quindi $\mcd(252,198)=18$. \end{esempio} \begin{nota}[Confronto con la scomposizione] Con la scomposizione: $252=2^2\cdot 3^2\cdot 7$, $198=2\cdot 3^2\cdot 11$. Fattori comuni: $2$ e $3$, esponenti minimi $1$ e $2$. Quindi $\mcd=2\cdot 3^2=18$. \checkmark Lo stesso risultato si ottiene molto più rapidamente con Euclide quando i fattori sono difficili da trovare. \end{nota} \begin{nota}[Estensione a più numeri] Per calcolare $\mcd(a,b,c)$ basta osservare che $\mcd(a,b,c)=\mcd(\mcd(a,b),c)$: si applica l'algoritmo a coppie. Idem per $\mcm$. \end{nota} % ============================================================ \section{Esempi svolti}\label{sec:aa-004-07-esempi-svolti} % ============================================================ \begin{esempio}[Applicazione dei criteri di divisibilità] Stabilire, senza fare le divisioni, se $n=\num{27 720}$ è divisibile per $2,3,4,5,8,9,10,11$. \textit{Soluzione.} \begin{itemize} \item Ultima cifra $0$: $2\mid n$, $5\mid n$, $10\mid n$. \item Somma cifre: $2+7+7+2+0=18$; $3\mid 18$, $9\mid 18$: $3\mid n$, $9\mid n$. \item Ultime due cifre: $20$; $4\mid 20$: $4\mid n$. \item Ultime tre cifre: $720$; $720=8\cdot 90$: $8\mid n$. \item Cifre alternate da destra: $(0+7+2)-(2+7)=9-9=0$; $11\mid 0$: $11\mid n$. \end{itemize} Sorprendentemente, $n$ è divisibile per tutti i numeri proposti. È un esempio classico: $\num{27 720} = 2^3\cdot 3^2\cdot 5\cdot 7\cdot 11$. \end{esempio} \begin{esempio}[Calcolo di MCD e mcm con la scomposizione] Calcolare $\mcd$ e $\mcm$ di $84$ e $126$. \textit{Soluzione.} Scomponiamo: $84=2^2\cdot 3\cdot 7$, $126=2\cdot 3^2\cdot 7$. \begin{align*} \mcd(84,126) &= 2^1\cdot 3^1\cdot 7^1 = 42, \\ \mcm(84,126) &= 2^2\cdot 3^2\cdot 7 = 252. \end{align*} Verifica: $\mcd\cdot\mcm = 42\cdot 252 = 10\,584$ e $a\cdot b = 84\cdot 126 = 10\,584$. \checkmark \end{esempio} \begin{esempio}[Algoritmo di Euclide per numeri grandi] Calcolare $\mcd(\num{1071}, \num{462})$. \textit{Soluzione.} Divisioni successive: \begin{align*} \num{1071} &= 462\cdot 2 + 147 \\ 462 &= 147\cdot 3 + 21 \\ 147 &= 21 \cdot 7 + 0 \end{align*} L'ultimo resto non nullo è $21$. Quindi $\mcd(\num{1071}, 462)=21$. \end{esempio} \begin{esempio}[Problema concreto: la corsa] Due tapis roulant compiono un giro rispettivamente ogni $\num{24}$ e $\num{36}$ secondi. Se vengono fatti partire insieme, dopo quanti secondi si ritroveranno entrambi al punto di partenza? \textit{Soluzione.} Cerchiamo il primo istante \emph{comune}: è $\mcm(24,36)$. Scomposizioni: $24=2^3\cdot 3$, $36=2^2\cdot 3^2$. Esponenti massimi: $2^3$, $3^2$. Quindi \[ \mcm(24,36) = 2^3\cdot 3^2 = 72. \] Si ritroveranno insieme al punto di partenza dopo $\SI{72}{\second}$ (ossia $1\,\text{minuto e}\,12\,\text{secondi}$). \end{esempio} \begin{esempio}[Frazione ai minimi termini] Ridurre la frazione $\dfrac{252}{198}$ ai minimi termini. \textit{Soluzione.} Dividere numeratore e denominatore per il loro MCD. Dall'esempio precedente, $\mcd(252,198)=18$. Allora \[ \frac{252}{198} = \frac{252:18}{198:18} = \frac{14}{11}. \] La forma ridotta è $\tfrac{14}{11}$ (numeratore e denominatore ora coprimi). \end{esempio} % ============================================================ \section{Esercizi proposti}\label{sec:aa-004-08-esercizi-proposti} % ============================================================ \begin{eserciziobox} \begin{enumerate} \item Stabilisci, applicando i criteri, se i seguenti numeri sono divisibili per $2,3,4,5,9,11$:\quad (a) $\num{4 320}$;\quad (b) $\num{18 711}$;\quad (c) $\num{50 050}$;\quad (d) $\num{121 121}$. \item Esegui la divisione euclidea, dando quoziente e resto:\quad (a) $137:12$;\quad (b) $1\,000:7$;\quad (c) $-58:5$;\quad (d) $\num{1234}:11$. \item Calcola $\mcd$ e $\mcm$ con il metodo della scomposizione:\quad (a) $24$ e $36$;\quad (b) $45$ e $75$;\quad (c) $84$ e $90$;\quad (d) $120$ e $180$. \item Per ciascuna coppia calcolata nell'esercizio precedente, verifica la relazione $\mcd\cdot\mcm = a\cdot b$. \item Calcola $\mcd$ con l'algoritmo di Euclide:\quad (a) $\mcd(216, 144)$;\quad (b) $\mcd(\num{1001}, 777)$;\quad (c) $\mcd(\num{2024}, 506)$;\quad (d) $\mcd(\num{4096}, \num{2730})$. \item Per ciascun caso del punto 5, ricava poi $\mcm$ usando la formula $\mcm = \tfrac{ab}{\mcd}$. \item Riduci ai minimi termini, usando l'MCD:\quad (a) $\tfrac{45}{75}$;\quad (b) $\tfrac{84}{126}$;\quad (c) $\tfrac{1\,000}{375}$. \item Problema: due lampade lampeggiano rispettivamente ogni $15$ secondi e $20$ secondi. Se cominciano insieme, dopo quanti secondi torneranno a lampeggiare contemporaneamente? \item (Discussione.) Un compagno afferma: ``se $a\mid c$ e $b\mid c$, allora $a\cdot b\mid c$''. È vero in generale? Trova un controesempio. Sotto quale condizione (su $a$ e $b$) la frase diventa vera? \end{enumerate} \end{eserciziobox} % ============================================================ \section{Riepilogo del capitolo}\label{sec:aa-004-09-riepilogo-del-capitolo} % ============================================================ \begin{riepilogo} \begin{itemize} \item $b\mid a$ significa: esiste $k\in\Z$ con $a=bk$. Equivalentemente, la divisione euclidea di $a$ per $b$ ha resto $r=0$. \item \emph{Divisione euclidea}: per ogni $a\in\Z$ e $b\in\N^*$, esistono e sono unici $q,r\in\Z$ con $a=bq+r$ e $0\le r