Con i primi giorni di novembre, su questo blog, si è dato inizio ad una nuova rubrica che pone al centro dell’attenzione le olimpiadi della matematica, fornendo ai lettori (docenti, studenti, semplici curiosi,…) qualche spunto su come prepararsi alle gare. Vogliamo ribadire che l’idea di fondo è quella di raggiungere quante più persone possibili, e non solo i pochi “addetti ai lavori”. Resta ferma la convinzione che la matematica delle gare di matematica possa essere compresa, con un minimo di sforzo, da tutti, ed eventualmente maneggiata con disinvoltura anche da coloro i quali, con un discreto allenamento e un pizzico di buona volontà, si dilettano a studiarne i principali aspetti.

In questo articolo riprenderemo alcuni concetti base di teoria dei numeri, come i numeri primi, la fattorizzazione di un intero e i quadrati perfetti.

Un momento della gara distrettuale del 20 febbraio 2020 a Roma

Numeri primi, fattorizzazione e quadrati perfetti

Nello scorso articolo avevamo fornito la definizione di numero primo e visto alcuni esercizi a riguardo. E’ lecito chiedersi come poter determinare se un numero $n$ sia primo o meno (e quindi composto). Il problema non è banale, specie se ci riferiamo a numeri molto grandi. Supporremo pertanto di trattare quei numeri sui quali le operazioni di seguito indicate possono essere svolte in maniera sufficientemente agevole. Si potrebbe pensare di dividere $n$ per tutti i valori $k$ compresi tra $2$ e $n-1$ (estremi inclusi); se tale divisione non da mai resto zero, allora $n$ è primo. In realtà ci si può limitare a verificare la divisione per i soli valori $d$ tali che $1<d\leq \sqrt{n}$. Infatti se $n$ è composto, può essere scritto come prodotto di due fattori (primi o meno) maggiori di 1, vale a dire $n=d_{1} \cdot d_{2} $, e uno di essi deve essere minore di $\sqrt{n}$ (o uguale a $\sqrt{n}$ nel caso di quadrati perfetti). Diversamente, se fossero entrambi maggiori di $\sqrt{n}$, accadrebbe che $d_{1} \cdot d_{2} > \sqrt{n} \cdot \sqrt{n}=n$, il che è assurdo. Più semplicemente, ci si può limitare a cercare un divisore primo di $n$ fra i valori $p$ tali che $1<p\leq \sqrt{n}$. A titolo di esempio, consideriamo il numero 143, la cui radice quadrata è poco meno di 12 (infatti il valore successivo, 144, è il quadrato di 12). Allora almeno un fattore primo della sua scomposizione deve essere 2 o 3 o 5 o 7 o 11. In effetti 143 è pari al prodotto fra 11 e 13. Viceversa, se consideriamo il numero 139, poiché non è divisibile né per 2, per 3, per 5, per 7 e per 11, e $13^{2}=169$ (maggiore di 139), ne discende che 139 è primo.

Ogni numero intero $n \geq 2$ può essere scritto in modo unico (a meno dell’ordine dei fattori) come prodotto di numeri primi. Sfruttando la simbologia matematica, si avrà $n=p^{\alpha_1}_{1} \cdot p^{\alpha_2}_{2} \cdot…\cdot p^{\alpha_k}_{k} $. Per chi ha confidenza con il simbolo di produttoria, risulta $n=\prod_{i=1}^{k}p^{\alpha_i}_i$. L’unicità discende dal fatto che 1, per definizione, non è un numero primo. Diversamente, nella fattorizzazione di $n$ avremmo potuto inserirlo come fattore, assegnandogli un esponente qualsiasi ed ottenendo così infinite diverse scomposizioni.

La fattorizzazione in numeri primi ci permette di calcolare il numero totale di divisori di un certo intero positivo $n$, che indicheremo con $d(n)$. Tale valore si ottiene moltiplicando tra loro gli esponenti della fattorizzazione aumentati di 1. Pertanto, se $n=p^{\alpha_1}_{1} \cdot p^{\alpha_2}_{2} \cdot…\cdot p^{\alpha_k}_{k} $, allora $d(n)=(\alpha_1+1)\cdot(\alpha_2+1)\cdot…\cdot(\alpha_k+1)$. A titolo di esempio, $20=2^{2}\cdot5$, pertanto $d(20)=3\cdot2=6$ e in effetti i divisori di 20 sono 6 (1, 2, 4, 5, 10 e 20). Appare chiaro che $d(n)=1$ solo per $n=1$ e gli unici numeri per i quali $d(n)=2$ sono i numeri primi; inoltre $d(n)<n$ per ogni $n \geq 3$. Osserviamo che $d(n)$ non dipende da quali sono i fattori di $n$, ma da quanti sono e con quali esponenti figurano. La relazione così trovata ci permette di calcolare il numero dei divisori positivi; se volessimo anche quelli negativi, allora bisognerebbe moltiplicare $d(n)$ per 2. Ora la giustificazione di tale relazione discende dal fatto che se nella fattorizzazione di $n$ compare $p^{\alpha_1}_{1}$, allora $n$ è banalmente divisibile per tutti i valori $p^{i}_{1}$, con $0 \leq i \leq \alpha_1$, che sono in totale $(\alpha_1+1)$. Ripetendo il ragionamento sui rimanenti fattori $p^{\alpha_2}_{2},…,p^{\alpha_k}_{k}$, e combinandoli opportunamente, otteniamo la relazione mostrata.

Si definisce quadrato perfetto un intero tale che risulti essere la potenza seconda di un altro intero. Un numero $n$ è un quadrato perfetto (o, più semplicemente, un quadrato) se e solo se tutti gli esponenti della sua fattorizzazione sono numeri pari (in generale: un numero è una potenza k-sima se e solo se tutti gli esponenti della sua fattorizzazione sono multipli di k). Ad esempio $144$ è il quadrato di $12$ e $144=2^{4}\cdot3^{2}$. Il fatto che i quadrati abbiano esponenti pari, implica che quando si va a calcolare il numero di divisori ottengo, in virtù della precedente relazione, un prodotto di tutti e soli numeri dispari (gli esponenti aumentati di 1), che da un numero dispari (ad esempio, i divisori di $2^{2}=4$ sono tre: 1, 2 e 4). Un altro modo di vedere i quadrati perfetti è osservare che essi sono tutti della forma $4k$ o $4k+1$ (o equivalentemente, in quest’ultimo caso, $4k-3$) per qualche intero $k$. Infatti ogni intero può essere scritto nella forma $2a$ o $2a+1$ (a seconda che sia pari o dispari) da cui, elevando al quadrato, ottengo $(2a)^{2}=4a^{2}$ e $(2a+1)^{2}=4a^{2}+4a+1=4(a^{2}+a)+1$. Con il linguaggio delle congruenze, si può affermare che $n$ è un quadrato perfetto se $n \equiv 0\hspace{0,2cm} (mod\hspace{0,2cm}4)$ o $n \equiv 1 \hspace{0,2cm}(mod\hspace{0,2cm}4)$, dove i due casi si hanno rispettivamente se si considera il quadrato di un numero pari o di un numero dispari.

E’ possibile calcolare anche il valore della somma di tutti i divisori (positivi) di $n$. Indichiamo tale somma con il simbolo $\sigma (n)$. Per chi stavolta ha dimestichezza con il simbolo di sommatoria, ricordando che la scrittura $d|n$ sta ad indicare che $d$ è un divisore di $n$, risulta $\sigma (n)=\sum_{d|n}d$. Nel caso in cui $n$ fosse pari alla potenza di un singolo numero primo $p$ (cioè $n=p^{k}$), allora $\sigma(n)=1+p+p^{2}+…+p^{k}=\sum_{i=0}^{k}p^i= \frac{ p^{k+1}-1 }{p-1}$, ove l’ultima uguaglianza è una diretta conseguenza della scomposizione del binomio $p^{k+1}-1$. Nel caso più generale in cui $n=p^{\alpha_1}_{1} \cdot p^{\alpha_2}_{2} \cdot…\cdot p^{\alpha_k}_{k} $, allora la somma di tutti i divisore è possibile ottenerla combinando fra loro quanto visto nel caso di un singolo fattore primo, vale a dire $\sigma(n)=(1+p_{1}+…+p^{\alpha_1}_{1})\cdot(1+p_{2}+…+p^{\alpha_2}_{2})\cdot…\cdot(1+p_{k}+…+p^{\alpha_k}_{k})=\prod_{i=1}^{k}\frac{(p^{\alpha_i+1}_{i}-1)}{(p_{i}-1)}$. Ad esempio, la somma dei divisori di $20$ è pari a $(1+2+2^{2})\cdot(1+5)=7\cdot6=42$. Tra l’altro, se moltiplico ciascun addendo all’interno della prima coppia di parentesi con ciascun addendo all’interno della seconda coppia di parentesi, ottengo un elenco completo di tutti i divisori di $20$.

Le funzioni $d(n)$ e $\sigma (n)$ sopra mostrate sono due funzioni moltiplicative, vale a dire che se applicate a due interi positivi $n, m$ primi fra loro (cioè senza divisori comuni diversi da 1 e -1), allora $d(nm)=d(n) \cdot d(m)$ e $\sigma(nm)=\sigma(n) \cdot \sigma(m)$, con $d(1)=\sigma(1)=1$.

I lettori più curiosi potranno svolgere ulteriori approfondimenti, su tali argomenti, sfruttando dispense o testi specifici. A riguardo, un ottimo sussidio è rappresentato dal libro di Salvatore Damantino “Teoria dei numeri”, edito da Scienza Express. Si tratta di uno dei 12 libri attualmente disponibili della collana U Math, di cui gli ultimi tre attualmente in campagna di lancio, scritti da docenti e membri della commissione olimpiadi dell’UMI e di facile accesso per tutti.

Un momento della finale nazionale del 25 settembre 2020 a Roma. Diversamente dal passato, nel 2020 si è svolta non a Cesenatico ma all’interno dei singoli distretti a causa della situazione legata all’emergenza Covid-19

Mostriamo di seguito alcuni esercizi su quanto appena esposto. Parte dei quesiti proposti sono tratti da alcuni stage tenuti in passato dal prof. Francini, membro della Commissione Olimpiadi dell’UMI.

Trovare tutti i numeri primi $p$ tali che $p+11$ sia anch’esso un numero primo.

Soluzione: è ben noto che, tranne il numero 2, tutti i numeri primi sono dispari. Una proprietà banale, ma che si applica spesso in molti esercizi delle gare, è che la somma di due pari è di due dispari da un numero pari, mentre la somma di un pari e di un dispari da un numero dispari (altrettanto semplice, ma importante, è l’analoga proprietà relativa alla moltiplicazione: il prodotto di due pari o di un pari e un dispari da un numero pari mentre il prodotto di due dispari da un numero dispari). Dunque, tranne il caso in cui $p=2$, per il quale $p+11=2+11=13$ che è primo, in tutti gli altri casi $p+11$ da un numero pari e quindi non primo. Ne consegue che esiste un solo valore che verifica la proprietà richiesta.

Osservazione: come applicazione di quanto appena mostrato, si suggerisce di provare a risolvere il seguente quesito (hint: ragionare sulla parità di $n$ e $n^{3}+3$): La professoressa di italiano entra in una classe di 24 studenti, tutti presenti, per un’ora di interrogazione. Decide di interrogare gli studenti a cui corrisponde sul registro un numero $n$ che sia primo e tale che anche $n^{3}+3$ sia primo. Quanti studenti interroga? (A) uno (B) tre (C) quattro (D) sette (E) nove (Giochi di Archimede 2009, biennio, quesito 15).

Quanti sono i numeri primi che possono essere espressi nella forma $n^{n+1}+1$, con $n$ intero positivo? (A) 0 (B) 1 (C) 2 (D) più di 2, ma in numero finito (E) infiniti (Gara distrettuale del 10/02/2011, quesito 4)

Soluzione: se $n$ è dispari, allora anche una sua qualunque potenza, come $n^{n+1}$, è dispari e pertanto $n^{n+1}+1$ è pari. Ora l’unico primo pari è 2, e la relazione $n^{n+1}+1=2$ è banalmente verificata per $n=1$. Se $n$ è pari, $n+1$ è dispari e $n^{n+1}+1$ si scompone come $(n+1)\cdot(n^{n}-n^{n-1}+…-n+1)$. In particolare se $n\geq2$ tanto il primo quanto il secondo fattore della scomposizione di $n^{n+1}+1$ sono maggiori di 1, e dunque il loro prodotto non può essere un numero primo. Ne consegue che la risposta corretta è la B.

Dimostrare che esistono 1000 interi positivi consecutivi non primi.

Soluzione: preso il numero $n=1001!$ (ove con il simbolo $k!$ si indica il fattoriale di un $k$, vale a dire il prodotto di tutti gli interi positivi minori o uguali a $k$), esso è multiplo di tutti i numeri interi da 2 a 1001 (estremi inclusi). Pertanto $1001!+2$ è divisibile per $2$, $1001!+3$ è divisibile per $3$ e così via fino a $1001!+1001$ che è divisibile per $1001$.

Per quali valori di $n$ l’espressione $n^{2}-8n+12$ da un numero primo?

Soluzione: scomponendo il trinomio, si ottiene $n^{2}-8n+12=(n-2)\cdot(n-6)$. Affinché l’espressione assegnata sia un numero primo, uno dei due fattori deve essere pari a $1$ o $-1$. Se $n-2=1$, cioè $n=3$, otteniamo come risultato $-3$ (non accettabile) mentre se $n-6=1$, cioè $n=7$, otteniamo come risultato $5$ (accettabile). Se $n-2=-1$, cioè $n=1$, otteniamo come risultato $5$ (accettabile) mentre se $n-6=-1$, cioè $n=5$, otteniamo come risultato $-3$ (non accettabile). Pertanto gli unici valori accettabili di $n$ sono $1$ e $7$.

Osservazione: si provi ad applicare lo stesso ragionamento nel caso in cui l’espressione è pari a $n^{4}+4$ (Ricordiamo che per scomporlo può essere utile procedere nel seguente modo: $n^{4}+4=n^{4}+4+4n^{2}-4n^{2}=(n^{2}+2)^{2}-4n^{2}=(n^{2}+2+2n)\cdot(n^{2}+2-2n)$).

Quanti sono i divisori positivi dispari di 8100 che sono multipli di 5? (A) 9 (B) 10 (C) 12 (D) 15 (E) 18 (F) 30 (Gara delle classi prime, 2019)

Soluzione: 8100 si scompone banalmente in $2^{2}\cdot3^{4}\cdot5^{2}$ (ricordiamo che quando un numero termina con $k$ zeri, allora nella sua scomposizione compaiono come fattori 2 e 5 con esponente almeno pari a $k$). Se voglio i divisori dispari e multipli di 5, allora essi non devono avere il 2 come fattore primo, ma devono possedere o $5$ o $5^{2}$. In altre parole, i divisore cercati sono della forma $5^{h}\cdot3^{k}$ con $h=1,2$ e $k=0,1,2,3,4$. Dunque in totale ho 10 possibilità. La risposta corretta pertanto è la B.

Dimostrare che non esistono quadrati perfetti della forma 11, 111, 1111, 11111, ecc.

Soluzione: poiché nessuno di questi numeri è multiplo di 4 o possiede resto 1 nella divisione per 4 (vale a dire non sono della forma $4k$ o $4k+1$), come si evince osservando la cifra delle decine e delle unità, ma sono tutti del tipo $4k-1$, ne consegue che nessuno di essi può essere un quadrato perfetto.

Quanti sono i numeri interi positivi $n$ tali che $n^{3}+2n^{2}+n$ sia un quadrato perfetto? (A) nessuno (B) almeno 1, ma non più di 4 (C) almeno 5, ma non più di 9 (D) almeno 10, ma non più di 20 (E) nessuna delle precedenti (Giochi di Archimede 2005, triennio quesito 2)

Soluzione: scomponendo $n^{3}+2n^{2}+n$ si ottiene $n\cdot(n^{2}+2n+1)=n\cdot(n+1)^{2}$. Ora $(n+1)^{2}$ è già un quadrato; basta che lo sia anche $n$, cioè che $n=k^{2}$ affinché l’intera espressione sia un quadrato perfetto. E ciò può accadere in infiniti modi, ottenendo $k^{2}\cdot(k^{2}+1)^{2})=(k\cdot(k^{2}+1))^{2}$. Dunque la risposta corretta è la E.

Qual è il più piccolo intero positivo il cui quadrato è divisibile per 504? (A) 84 (B) 504 (C) 42 (D) 126 (E) 252 (F) nessuna delle altre risposte è esatta (Gara delle classi prime, 2020)

Soluzione: 504 si può fattorizzare come $2^{3}\cdot3^{2}\cdot7$. Un numero divisibile per 504 deve avere nella sua scomposizione tutti i fattori primi di 504. Affinché sia anche il più piccolo quadrato, tali fattori dovranno avere come esponente il più piccolo numero pari maggiore o uguale agli esponenti della fattorizzazione di 504, e non dovranno esserci altri fattori primi. Ne consegue che il valore cercato è pari a $2^{4}\cdot3^{2}\cdot7^{2}$, il quale è banalmente il quadrato di $2^{2}\cdot3\cdot7=84$. Pertanto la risposta corretta è la A.

Determinare: a) il più piccolo intero positivo con esattamente 10 divisori; b) il più grande intero positivo con esattamente 10 divisori; c) il più piccolo intero positivo con esattamente 11 divisori; d) il numero di multipli di 11 con 11 divisori; e) il numero di multipli di 22 con 22 divisori; f) il numero di multipli di 44 con 44 divisori.

Soluzione: a) ricordando la relazione che lega numero di divisori ed esponenti della fattorizzazione, e poiché $10=1\cdot10=2\cdot5$, allora la quantità cercata è del tipo $p^{9}$ o $p\cdot q^{4}$, con $p,q$ numeri primi. Nel primo caso il più piccolo valore cercato si ottiene per $p=2$ e dunque $p^{9}=2^{9}=512$. Nel secondo caso il più piccolo valore cercato si ottiene per $p=3$ e $q=2$ (ad esponente maggiore corrisponde primo minore), con $p\cdot q^{4}=3\cdot2^{4}=3\cdot16=48$. Dunque la soluzione è 48.

b) Il fatto che i numeri primi siano infiniti, implica che non è possibile determinare il più grande intero positivo con esattamente 10 divisori (nella scomposizione $p^{9}$ o $p\cdot q^{4}$ posso mettere primi grandi a piacere)

c) Discorso analogo a quanto fatto per il punto a), con la differenza che stavolta l’unico caso possibile è $p^{10}$ e pertanto la soluzione è pari a $2^{10}=1024$.

d) Affinché un numero con $p$ divisori sia multiplo di $p$, allora deve essere della forma $p^{p-1}$, in questo caso $11^{10}$.

e) Un numero con 22 divisori è della forma $p^{21}$ o $p\cdot q^{10}$, con $p,q$ numeri primi. Ora $p^{21}$ non potrà mai dare un multiplo di 22 qualunque sia il numero primo $p$ scelto, mentre nel secondo caso è possibile ottenere un multiplo di 22 in due modi: o scegliendo $p=2$ e $q=11$, o viceversa $p=11$ e $q=2$.

f) Esistono infiniti multipli di 44 con 44 divisori. Infatti uno dei modi possibili per ottenere un intero con 44 divisori è scrivere l’espressione $2^{10}\cdot11\cdot p$, con $p$ un qualunque primo diverso da 2 e da 11.

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.