Due proprietà dei divisori dei numeri naturali

Prerequisiti:

In questo articolo presenteremo due proprietà dei divisori dei numeri naturali, iniziando dal caso più semplice, in cui prenderemo in considerazione i numeri che sono il prodotto di due fattori primi distinti. Prendiamo ad esempio il numero 10, che è il prodotto di 2 per 5. Quindi gli unici suoi divisori non banali, ossia diversi dal numero stesso e da 1, sono proprio 2 e 5. Si può osservare che il numero dei divisori banali (1 e 10) è uguale al numero di quelli non banali (2 e 5), ed anche il loro prodotto è uguale: 1 \cdot 10 = 2 \cdot 5. Il nostro obiettivo sarà quello di generalizzare queste due semplici proprietà per numeri che non sono necessariamente il prodotto di due fattori primi distinti.

Per cominciare, possiamo considerare qualunque numero intero positivo n al posto di 10:

Due proprietà da generalizzare

Sia n un numero intero positivo. Se n = pq, con p e q umeri primi distinti, allora i suoi divisori sono 1, p, q ed n, per cui:

  • i divisori non banali sono due, p e q, proprio come quelli banali, che sono 1 ed n;
  • il prodotto dei divisori banali è uguale a quello dei divisori non banali: 1 \cdot n = p \cdot q.

Quindi possiamo dire che l’esempio del 10 può essere facilmente esteso a tutti i numeri che sono prodotto di due fattori primi distinti.
A questo punto, il passo successivo sarebbe tentare di generalizzare queste due proprietà per classi di numeri più ampie. Ad esempio, si potrebbe vedere cosa succede per i numeri che sono il prodotto di tre numeri primi distinti, ad esempio 30 = 2 \cdot 3 \cdot 5. I divisori di 30 sono 1, 2, 3, 5, 6, 10, 15, 30. I divisori banali, come per qualsiasi numero intero, sono sempre due (1 e 30), mentre in questo caso ci sono più divisori non banali, e si vede ad occhio che 1 \cdot 30 \neq 2 \cdot 3 \cdot 5 \cdot 6 \cdot 10 \cdot 15. Sembrerebbe quindi che le due proprietà valgano solo per il caso molto particolare dei numeri che sono il prodotto di due fattori primi distinti, ma non è così: esiste infatti un modo per generalizzarle, come vedremo nei paragrafi seguenti.

D’ora in poi, quando parleremo di “divisori” di un numero intero positivo, intenderemo sempre i divisori positivi. Infatti, studieremo le proprietà di \mathbb{N} e non di \mathbb{Z}.

Generalizzazione ai numeri privi di quadrati

Riprendiamo l’esempio del numero 30. Per capire come generalizzare le due proprietà, è utile disporre i divisori di 30 in un diagramma chiamato diagramma di Hasse, costruito in modo tale che due qualsiasi divisori d_1 e d_2 sono collegati da un segmento se e solo se d_1 \mid d_2 e non esiste nessun altro divisore d_3 intermedio tra i due, ossia tale che d_1 \mid d_3 \mid d_2:

Figura 1: il diagramma di Hasse del numero 30


In un diagramma di questo tipo, i divisori del numero di partenza vengono naturalmente a disporsi su vari livelli, a seconda del numero dei loro fattori primi. Ad esempio, nella Figura 1:

  • 1 è il prodotto di zero fattori primi, per cui si trova sul livello più basso (chiamiamolo “livello zero”);
  • sul primo livello ci sono i fattori primi di 30: 2, 3 e 5;
  • sul secondo livello ci sono i divisori di 30 che sono prodotto di due e solo due fattori primi: 6, 10 e 15;
  • 30, prodotto di tre fattori primi, è l’unico divisore del terzo livello, quello più alto.

Possiamo osservare che:

  • Il numero dei divisori sui livelli dispari è uguale al numero di quelli sui livelli pari. Si tratta infatti di quattro divisori in entrambi i casi: 1, 6, 10 e 15 si trovano sui livelli pari, mentre 2, 3, 5 e 30 si trovano sui livelli dispari.
  • Il prodotto dei divisori sui livelli dispari è uguale al prodotto di quelli sui livelli pari: 1 \cdot (6 \cdot 10 \cdot 15) = (2 \cdot 3 \cdot 5) \cdot 30.
I diagrammi di Hasse non vengono utilizzati solo per rappresentare l’insieme dei divisori di un numero intero, ma in generale per rappresentare qualsiasi insieme finito sul quale è definita una relazione d’ordine (nel caso dei divisori di un numero intero, la relazione d’ordine è quella di divisibilità).

Queste ultime due osservazioni sono un modo corretto di generalizzare le due proprietà che abbiamo visto inizialmente per i numeri che sono il prodotto di due fattori primi distinti. Ciò è evidente se si disegna il diagramma di Hasse di un numero di questo tipo. Ad esempio, per il numero 10 abbiamo:

Figura 2: il diagramma di Hasse del numero 10

Possiamo notare che i due divisori banali si dispongono sui due livelli pari, mentre i due non banali si trovano sull’unico livello dispari; quindi, tra i livelli pari e quelli dispari, è uguale sia il conteggio, sia il prodotto dei divisori.

Questo discorso si può estendere a numeri che sono il prodotto di un numero arbitrario di numeri primi distinti. Ad esempio, consideriamo il numero 210, che è il più piccolo numero che è il prodotto di quattro numeri primi distinti, essendo pari a 2 \cdot 3 \cdot 5 \cdot 7. In questo caso il diagramma di Hasse è composto da cinque livelli:

Figura 3: il diagramma di Hasse del numero 210

Ancora una volta, le due proprietà sono verificate:

  • Ci sono 1 + 6 + 1 = 8 divisori sui livelli pari e 4 + 4 = 8 divisori sui livelli dispari.
  • Il prodotto dei divisori sui livelli pari è uguale al prodotto dei divisori sui livelli dispari (provare per credere!):
    1 \cdot (6 \cdot 10 \cdot 14 \cdot 15 \cdot 21 \cdot 35) \cdot 210 = (2 \cdot 3 \cdot 5 \cdot 7) \cdot (30 \cdot 42 \cdot 70 \cdot 105)

Negli esempi finora considerati, si può osservare che:

  • se ci sono tre livelli, allora c’è 1 divisore sul primo livello, ce ne sono 2 sul secondo ed 1 sul terzo (come accade per il numero 10);
  • se ci sono quattro livelli, allora c’è 1 divisore sul primo livello, ce ne sono 3 sul secondo, 3 sul terzo ed 1 sul quarto (come accade per il numero 30);
  • se ci sono cinque livelli, allora c’è 1 divisore sul primo livello, ce ne sono 4 sul secondo, 6 sul terzo, 4 sul quarto ed 1 sul quinto (come accade per il numero 210).

Non è un caso che le sequenze 1 2 1, 1 3 3 1 e 1 4 6 4 1 così determinate sono anche delle righe del triangolo di Tartaglia, che abbiamo visto nell’articolo Stime dei binomiali. Infatti, si può dimostrare che questa proprietà del conteggio dei divisori discende da una analoga proprietà dei coefficienti binomiali: per qualsiasi intero positivo n, la somma dei coefficienti binomiali del tipo \binom{n}{k}, con k pari, è uguale alla somma dei coefficienti binomiali dello stesso tipo, con k dispari.

I numeri interi che sono il prodotto di numeri primi distinti sono una classe di numeri abbastanza importante, che a questo punto conviene approfondire. Esiste infatti un concetto equivalente, che è quello di numero intero privo di quadrati:

Numero intero privo di quadrati

Un numero intero si dice privo di quadrati (o libero da quadrati) se non è divisibile per nessun numero quadrato maggiore di 1.

Caratterizzazione dei numeri interi privi di quadrati

Un numero intero è privo di quadrati se e solo se nella sua fattorizzazione compaiono solo fattori primi distinti.

Dimostriamo l’enunciato equivalente che si ottiene per negazione di ambo i membri: “Un numero intero non è privo di quadrati se e solo se nella sua fattorizzazione compare almeno un fattore primo ripetuto”.
La dimostrazione è immediata:

  • Se n non è privo di quadrati, esiste un numero quadrato a^2 \gt 1 tale che a^2 \mid n. Allora ciascun fattore primo di a, essendo presente almeno due volte nella fattorizzazione di a^2, sarà presente almeno due volte anche nella fattorizzazione di n, quindi in quest’ultima non possono comparire solamente fattori primi distinti.
  • Se nella fattorizzazione di n compare un fattore primo p ripetuto, allora p^2 \mid n, quindi n non è privo di quadrati.

Quindi, per la Proprietà N.7, nel seguito potremo dire indifferentemente che un numero intero è “prodotto di fattori primi distinti” o che è “privo di quadrati”.

Ricapitolando, abbiamo visto attraverso vari esempi che le due proprietà che stiamo studiando – che nel seguito chiameremo anche “proprietà del conteggio” e “proprietà del prodotto” – si verificano entrambe per numeri privi di quadrati con un numero di fattori primi crescente, a partire da 2. Per i numeri primi, che si possono considerare come il prodotto di un solo fattore primo, vale invece solo la prima proprietà. Ad esempio, il diagramma di Hasse del numero 3 è il seguente:

Figura 4: il diagramma di Hasse del numero 3

Esiste un divisore sull’unico livello pari ed un altro divisore sull’unico livello dispari, perciò la proprietà del conteggio è rispettata. Tuttavia, i prodotti dei divisori su ciascun livello sono diversi; infatti, essendo prodotti di un solo numero, coincidono col numero stesso, ma i due numeri sono diversi.
Se invece i fattori primi, tutti distinti, sono almeno due, essi non devono necessariamente essere consecutivi. Ad esempio, vi invitiamo a verificare che le due proprietà valgono anche per il numero 330 = 2 \cdot 3 \cdot 5 \cdot 11, anche se i divisori primi non sono tutti i numeri primi fino a 11, perché manca il 7.

I problemi cominciano quando consideriamo dei numeri che nella loro fattorizzazione hanno un numero primo ripetuto più volte (oppure, equivalentemente, un numero primo elevato ad un esponente maggiore di 1). Ad esempio, se invece di 30 = 2 \cdot 3 \cdot 5 considerassimo il numero 60 = 2 \cdot 2 \cdot 3 \cdot 5, dove il 2 è presente due volte, per quanto riguarda il numero di divisori ci ritroveremmo, ma passando al prodotto i conti non tornerebbero più. Infatti, il diagramma di Hasse dei divisori di 60 è il seguente:

Figura 5: il diagramma di Hasse del numero 60

Ci sono 1 + 4 + 1 = 6 divisori sui livelli pari e 3 + 3 = 6 sui livelli dispari, dunque la proprietà del conteggio è verificata; tuttavia il prodotto dei fattori sui livelli pari è 1 \cdot 4 \cdot 6 \cdot 10 \cdot 60 = 14.400, mentre il prodotto di quelli sui livelli dispari è 2 \cdot 3 \cdot 5 \cdot 12 \cdot 20 \cdot 30 = 216.000.
Potremmo pensare che il problema sia che la ripetizione del 2 crea uno squilibrio tra i divisori, perché non tutti sono presenti nella fattorizzazione lo stesso numero di volte, ma in realtà non è così. Infatti, se considerassimo il numero 2 \cdot 2 \cdot 3 \cdot 3 = 36, dove entrambi i fattori primi sono ripetuti due volte, sarebbe anche peggio, in quanto non solo non varrebbe la proprietà del prodotto, ma neanche quella del conteggio:

Figura 6: il diagramma di Hasse del numero 36

Infatti in questo caso ci sono 1 + 3 + 1 = 5 divisori sui livelli pari e 2 + 2 = 4 sui livelli dispari, ed i loro prodotti sono diversi: 1 \cdot 4 \cdot 6 \cdot 9 \cdot 36 \neq 2 \cdot 3 \cdot 12 \cdot 18.

Questa è una buona domanda: infatti è lecito pensare che esista un modo diverso per organizzare i divisori in livelli, per far quadrare i conti che non tornano per numeri come 60 o 36. Non conosciamo una risposta generale a questa domanda, possiamo però dire che non è così semplice.
Ad esempio, una scelta sensata potrebbe essere quella di intendere ogni livello l non come l’insieme dei divisori nella cui fattorizzazione compaiono l fattori primi, ma quelli nella cui fattorizzazione compaiono l fattori primi distinti, ignorando quindi le ripetizioni di uno stesso fattore primo.
Se provassimo a suddividere i divisori di 60 in questo modo, avremmo che:

  • 1 è sempre l’unico prodotto di 0 fattori primi, per cui rimarrebbe l’unico divisore del livello 0
  • 2, 3, e 5 sono il prodotto di un unico fattore primo, quindi come prima entrerebbero a far parte del livello 1; però ora anche il 4 rientrerebbe nel livello 1, perché nella sua fattorizzazione compare esclusivamente il fattore primo 2: ignorando la ripetizione, si tratta sempre di un singolo fattore primo.
  • 6, 10 e 15 sono il prodotto di due fattori primi distinti, per cui come prima entrerebbero a far parte del livello 2; però ora anche 12 e 20 rientrerebbero nel livello 2, perché anche nelle loro fattorizzazioni compaiono due fattori primi distinti: 2 e 3 nel caso del 12; 2 e 5 nel caso del 20.
  • Sia nella fattorizzazione di 30 che in quella di 60 compaiono tre fattori primi distinti: 2, 3 e 5; perciò entrambi apparterrebbero al livello 3.

Riorganizzando il diagramma di Hasse di 60 in questo modo, otteniamo la seguente figura:

Figura 7: il diagramma di Hasse del numero 60 con una diversa suddivisione dei divisori in livelli

Ora i conti tornano: il conteggio dei divisori è 1 + 5 = 6 per i livelli pari e 4 + 2 = 6 per i livelli dispari; inoltre il prodotto dei divisori dei livelli pari è uguale al prodotto di quelli dei livelli dispari: 1 \cdot 12 \cdot 6 \cdot 20 \cdot 10 \cdot 15 = 216.000 = 4 \cdot 2 \cdot 3 \cdot 5 \cdot 60 \cdot 30. Sembra quindi che abbiamo trovato la maniera giusta di ripartire i divisori di un numero intero positivo in livelli pari e livelli dispari. Questo metodo però non funziona con tutti i numeri. Ad esempio, per il numero 36 otterremmo il seguente diagramma, che non soddisfa nessuna delle due proprietà:

Figura 8: il diagramma di Hasse del numero 36 con una diversa suddivisione dei divisori in livelli

Come si può facilmente verificare, il conteggio dei divisori è 4 per i livelli pari e 5 per quelli dispari, ed il prodotto dei divisori del livelli pari è diverso dal prodotto di quelli dei livelli dispari.
La domanda se ci sia un metodo più generale per riorganizzare i divisori in livelli, in modo tale da soddisfare le proprietà che stiamo studiando anche in presenza di fattori primi ripetuti, deve restare dunque aperta. Possiamo dire con certezza, però, che se esistesse un tale metodo, certamente non sarebbe valido per tutti i numeri. Infatti, una condizione necessaria perché tale metodo esista è che il prodotto di tutti i divisori di n sia un numero quadrato. Infatti, indicando con P_n il prodotto dei divisori dei livelli pari, con D_n il prodotto di quelli dei livelli dispari, e con T_n il prodotto di tutti i divisori di n, essendo per ipotesi P_n = D_n, si deve avere che T_n = P_n \cdot D_n = P_n \cdot P_n = P_n^2, per cui T_n deve essere un numero quadrato. Questo però non è vero ad esempio per 36, perché il prodotto dei suoi divisori, 1 \cdot 4 \cdot 2 \cdot 3 \cdot 9 \cdot 12 \cdot 6 \cdot 18 \cdot 36, non è un numero quadrato.

Generalizzazione per qualsiasi numero intero maggiore di 1

Data la difficoltà di generalizzare queste proprietà per numeri interi positivi qualsiasi, possiamo ricorrere ad un semplice artificio per ricondurci al caso dei numeri privi di quadrati: basta eliminare, nel diagramma di Hasse, tutti i divisori non privi di quadrati (ossia, per la Proprietà N.7, nella cui fattorizzazione è presente almeno un primo ripetuto più di una volta). Ad esempio, partendo dal diagramma di Hasse di 60, dobbiamo togliere i divisori 4, 12, 20 e 60, perché nella loro fattorizzazione il 2 è ripetuto due volte: 4 = 2 \cdot 2, 12 = 2 \cdot 2 \cdot 3, 20 = 2 \cdot 2 \cdot 5 e 60 = 2 \cdot 2 \cdot 3 \cdot 5. Così facendo, si ottiene il diagramma di Hasse di 30, che è un numero privo di quadrati, essendo il prodotto dei fattori primi distinti di 60:

Figura 9: cancellando dal diagramma di Hasse di 60 i divisori non privi di quadrati, si ottiene il diagramma di Hasse di 30

Analogamente, partendo dal diagramma di Hasse di 36 ed effettuando la medesima operazione, si ottiene il diagramma di Hasse di 6, che è privo di quadrati essendo il prodotto dei fattori primi distinti di 36:

Figura 10: cancellando dal diagramma di Hasse di 36 i divisori non privi di quadrati, si ottiene il diagramma di Hasse di 6

Se invece il numero di partenza è una potenza di un numero primo con un esponente maggiore di 1, come 81 = 3^4, togliere i divisori non privi di quadrati equivale a togliere tutte le potenze con esponente maggiore di 1, perciò nel caso di 81 resteremmo con un diagramma di Hasse contenente solamente 1 e 3, che è il diagramma di Hasse di 3:

Figura 11: cancellando dal diagramma di Hasse di 81 i divisori non privi di quadrati, si ottiene il diagramma di Hasse di 3

Abbiamo visto che in questo caso è verificata solo la proprietà del conteggio, e non quella del prodotto. Quindi in generale possiamo dire che, eliminando i divisori non privi di quadrati (cioè con fattori primi ripetuti), la proprietà del prodotto è verificata quando nella fattorizzazione del numero di partenza compaiono almeno due numeri primi distinti; invece, la proprietà del conteggio è verificata anche quando nella fattorizzazione vi è un solo numero primo, eventualmente ripetuto più volte.

Il numero 1 è un caso degenere, perché si può considerare come il prodotto di 0 fattori primi, mentre numeri che ci interessano hanno invece almeno un fattore primo, eventualmente ripetuto. Scegliamo di trascurare il caso del numero 1 un po’ per questo motivo, un po’ perché le proprietà non sono verificate secondo la regola generale. Infatti la proprietà del conteggio non è verificata (l’unico divisore 1 è prodotto di un numero pari (0) di fattori primi, e non vi sono divisori che sono prodotto di un numero dispari di fattori primi) mentre quella del prodotto sì (1 è il prodotto dell’insieme \{1\} dei divisori che sono il prodotto di un numero pari di fattori primi distinti, ma anche il prodotto dell’insieme vuoto dei divisori che sono il prodotto di un numero dispari di fattori primi distinti).

Possiamo quindi enunciare la proprietà del conteggio e quella del prodotto come segue:

Una proprietà del conteggio dei divisori di un numero intero maggiore di 1

Sia n \gt 1 un numero intero. Siano P_n e D_n i seguenti insiemi:

P_n := \left\{ \begin{gathered} \text{divisori di $n$ privi di quadrati,} \\ \text{che sono il prodotto di un numero pari di fattori primi} \end{gathered}\right\}
D_n := \left\{ \begin{gathered} \text{divisori di $n$ privi di quadrati,} \\ \text{che sono il prodotto di un numero dispari di fattori primi} \end{gathered}\right\}

Allora

|P_n| = |D_n|

Potremmo ricondurre la dimostrazione di questa proprietà ad una analoga proprietà degli insiemi: dato un qualsiasi insieme di n elementi, il numero di sottoinsiemi con un numero pari di elementi è uguale al numero di sottoinsiemi con un numero dispari di elementi. Se si assume come nota questa proprietà, diventa molto semplice dimostrare la Proprietà N.8. Noi però faremo la dimostrazione da zero, con lo stesso tipo di ragionamento che si userebbe nel caso degli insiemi, perché poi modificandola leggermente potremo dimostrare anche la proprietà che riguarda il prodotto dei divisori.

Chiamiamo k il numero di fattori primi distinti di n e procediamo per induzione su k. Il caso base è k = 1, che si verifica quando nella fattorizzazione di n compare un solo fattore primo distinto, che possiamo chiamare q, cioè quando n è una potenza di q con esponente positivo. Per un tale n, gli unici divisori privi di quadrati sono 1 (prodotto di 0 primi) e q (prodotto di un solo fattore primo), perché qualunque altro divisore di n sarebbe una potenza di q con esponente maggiore di 1, la cui fattorizzazione conterrebbe quindi il primo q ripetuto più volte. Quindi P_n = \{1\} e D_n = \{q\}, per cui il caso base è verificato, essendo |P_n| = |D_n| = 1.

Supponiamo ora che la proprietà sia verificata per k - 1 e dimostriamola per k, con k \geq 2.
Per fare ciò, dobbiamo chiederci quali sono gli elementi di P_n e di D_n per un numero n che ha k fattori primi distinti, riconducendoci in qualche modo ad un numero che ha k - 1 fattori primi distinti, per poter usare l’ipotesi di induzione. Questo modo consiste nell’eliminare dalla fattorizzazione di n uno qualunque dei suoi fattori primi, che chiameremo p, comprese le sue eventuali ripetizioni. Otterremo così un nuovo numero n^{\prime}, nella cui fattorizzazione compaiono k - 1 fattori primi distinti, per cui a questo numero potremo applicare l’ipotesi di induzione, ottenendo che |P_{n^{\prime}}| = |D_{n^{\prime}}|. Ma quale relazione hanno gli insiemi P_n e D_n con gli insiemi P_{n^{\prime}} e D_{n^{\prime}}?
Cominciamo da P_n. Per prima cosa, osserviamo che un divisore d di n appartenente a P_n può contenere o no p nella sua fattorizzazione:

  • Se la fattorizzazione di d non contiene p, allora d è anche un divisore di n^{\prime}, perché quest’ultimo ha gli stessi fattori primi di n, eccetto solamente p e le sue eventuali ripetizioni. Quindi d \in P_{n^{\prime}}.
  • Se la fattorizzazione di d contiene p (ed in tal caso, per definizione di P_n e per la Proprietà N.7, lo contiene solo una volta), possiamo dividere d per p, ottenendo il numero \frac{d}{p} che sarà quindi un prodotto di fattori primi distinti, tutti diversi da p. Allora, come prima, essendo n^{\prime} il prodotto di tutti i fattori primi di n diversi da p, certamente \frac{d}{p} \mid n^{\prime}. Inoltre, \frac{d}{p} è prodotto di un numero dispari di fattori primi distinti (perché inizialmente erano in numero pari e abbiamo tolto p), per cui, sempre per Proprietà N.7, \frac{d}{p} \in D_{n^{\prime}}. Equivalentemente, possiamo dire che d = p \cdot a, per qualche a \in D_{n^{\prime}}, o ancora che d \in p \cdot D_{n^{\prime}}, dove l’insieme p \cdot D_{n^{\prime}} è l’insieme ottenuto da D_{n^{\prime}} moltiplicandone tutti gli elementi per p, cioè p \cdot D_{n^{\prime}} := \{p \cdot a | a \in D_{n^{\prime}}\}.

Considerando queste due possibilità complessivamente, abbiamo che d \in P_{n^{\prime}} oppure d \in p \cdot D_{n^{\prime}}, quindi d \in P_{n^{\prime}} \cup p \cdot D_{n^{\prime}}. Ma questo è vero per ogni d \in P_n, per cui

P_n \subseteq P_{n^{\prime}} \cup \left( p \cdot D_{n^{\prime}} \right) \tag{1}
Se n = 2 \cdot 2 \cdot 3 \cdot 5 e p = 2, allora:

  • n^{\prime} = 3 \cdot 5
  • P_n = \{1,\ 2 \cdot 3,\ 2 \cdot 5,\ 3 \cdot 5\} (in particolare 2 \cdot 2 \notin P_n e 2 \cdot 2 \cdot 3 \cdot 5 \notin P_n perché questi divisori di n non sono privi di quadrati)
  • P_{n^{\prime}} = \{1,\ 3 \cdot 5\}
  • D_{n^{\prime}} = \{3,\ 5\}
  • 2 \cdot D_{n^{\prime}} = \{2 \cdot 3,\ 2 \cdot 5\}
  • 1 è il prodotto di 0 fattori primi (diversi da p) \Rightarrow 1 \in P_{n^{\prime}}
  • 2 \cdot 3 è il prodotto di 2 fattori primi distinti, tra cui p \Rightarrow 2 \cdot 3 \in 2 \cdot D_{n^{\prime}}
  • 2 \cdot 5 è il prodotto di 2 fattori primi distinti, tra cui p \Rightarrow 2 \cdot 5 \in 2 \cdot D_{n^{\prime}}
  • 3 \cdot 5 è il prodotto di 2 fattori primi distinti diversi da p \Rightarrow 2 \cdot 3 \in P_{n^{\prime}}

Si può ripetere il ragionamento precedente guardando la relazione (1) nel senso opposto. Infatti, se partiamo da un divisore d^{\prime} di n^{\prime}, abbiamo due possibilità:

  • Se d^{\prime} \in P_{n^{\prime}}, innanzitutto d^{\prime} è il prodotto di un numero pari di fattori primi; inoltre d^{\prime} è un divisore di n^{\prime} che a sua volta è un divisore di n, per cui d^{\prime} è anche un divisore di n; considerando entrambe le cose, d^{\prime} \in P_n.
  • Se d^{\prime} \in p \cdot D_{n^{\prime}}, d^{\prime} è il prodotto di p per un numero dispari di fattori primi distinti diversi da p, dunque è il prodotto di un numero pari di fattori primi distinti. Inoltre è un divisore di n, in quanto \frac{n^{\prime}}{p} \in D_{n^{\prime}} \Rightarrow \frac{n^{\prime}}{p} \mid n^{\prime}, da cui n^{\prime} \mid (p \cdot n^{\prime}) \mid n, quindi n^{\prime} \mid n. Riassumendo, essendo n^{\prime} un divisore di n e prodotto di un numero pari di fattori primi distinti, tenendo sempre conto della Proprietà N.7, anche in questo caso d^{\prime} \in P_n.

Abbiamo ottenuto quindi la relazione opposta alla (1), ossia

P_{n^{\prime}} \cup \left( p \cdot D_{n^{\prime}} \right) \subseteq P_n \tag{2}

Combinando la (1) e la (2), si ottiene la seguente relazione fondamentale:

P_n = P_{n^{\prime}} \cup \left( p \cdot D_{n^{\prime}} \right) \tag{3}

Si può ripetere lo stesso ragionamento per D_n, ottenendo alla fine:

D_n = D_{n^{\prime}} \cup \left( p \cdot P_{n^{\prime}} \right) \tag{4}

Ora non resta che calcolare la cardinalità di P_n e D_n partendo dalle formule (3) e (4). Per farlo, dobbiamo prima osservare alcune cose:

  • Gli insiemi di cui si fa l’unione sono disgiunti, perché l’insieme di destra ha come elementi solamente multipli di p, mentre gli elementi dell’insieme di sinistra non possono esserlo, perché sono divisori di n^{\prime}, e p non compare nella fattorizzazione di n^{\prime}.
  • Gli insiemi p \cdot D_{n^{\prime}} e p \cdot P_{n^{\prime}} hanno rispettivamente la stessa cardinalità di D_{n^{\prime}} e P_{n^{\prime}}. Infatti, guardando per esempio gli insiemi p \cdot D_{n^{\prime}} e D_{n^{\prime}}, il primo si ottiene moltiplicando per p tutti gli elementi del secondo; così facendo, partendo da elementi distinti di D_{n^{\prime}} si ottengono elementi distinti di p \cdot D_{n^{\prime}} (in altri termini, la moltiplicazione per p è una funzione iniettiva), per cui |p \cdot D_{n^{\prime}}| = |D_{n^{\prime}}|.
  • Per ipotesi di induzione, |P_{n^{\prime}}| = |D_{n^{\prime}}|, perciò possiamo porre entrambi pari ad una costante C.

Combinando queste osservazioni, dalla formula (3) otteniamo che:

\begin{aligned} |P_n| & = \text{[formula (3)]} \\ |P_{n^{\prime}} \cup p \cdot D_{n^{\prime}}| & = \text{[unione disgiunta]} \\ |P_{n^{\prime}}| + |p \cdot D_{n^{\prime}}| &= \text{[iniettività della moltiplicazione per $p$]} \\ |P_{n^{\prime}}| + |D_{n^{\prime}}| &= \text{[ipotesi di induzione]} \\ C + C \end{aligned}

Mentre dalla (4) otteniamo:

\begin{aligned} |D_n| & = \text{[formula (4)]} \\ |D_{n^{\prime}} \cup p \cdot P_{n^{\prime}}| & = \text{[unione disgiunta]} \\ |D_{n^{\prime}}| + |p \cdot P_{n^{\prime}}| &= \text{[iniettività della moltiplicazione per $p$]} \\ |D_{n^{\prime}}| + |P_{n^{\prime}}| &= \text{[ipotesi di induzione]} \\ C + C \end{aligned}

Quindi |P_n| = |D_n|, che è quello che volevamo dimostrare.

Una proprietà del prodotto dei divisori di un numero intero positivo avente almeno due fattori primi distinti

Sia n un numero intero positivo avente almeno due fattori primi distinti. Siano P_n e D_n gli insiemi definiti nella Proprietà N.8. Allora

\prod_{a \in P_n} a = \prod_{b \in D_n} b

Si deve prestare attenzione alla differenza tra le espressioni “avente almeno due fattori primi distinti” e “prodotto di almeno due fattori primi distinti”. Nel primo caso, che è l’ipotesi della Proprietà N.9, si intende che n può avere nella sua fattorizzazione fattori primi anche ripetuti, ma devono essercene almeno due distinti: ad esempio 12 = 2 \cdot 2 \cdot 3 va bene ma 4 = 2 \cdot 2 no. Nel secondo caso, si intende che nella fattorizzazione di n ci sono solo fattori primi distinti, ed il numero di questi fattori è almeno due. La seconda espressione è quindi un caso particolare della prima, e i due concetti non vanno confusi. Per questo motivo abbiamo definito gli elementi degli insiemi P_n e D_n come “privi di quadrati”, evitando così l’abuso dell’espressione “fattori primi distinti”.

Come anticipato, la dimostrazione di questa proprietà è solo una leggera modifica di quella della proprietà precedente. Anche in questo caso di procede per induzione su k, il numero di fattori primi distinti di n, però in questo caso il passo base è k = 2.

Se k = 2, nella fattorizzazione di n compaiono esattamente due fattori primi distinti. Allora i divisori contenuti nell’insieme P_n, per definizione, possono essere il prodotto o di 0 o di 2 fattori primi distinti, perché questi sono gli unici numeri pari minori o uguali di k = 2. L’unico prodotto di 0 fattori primi è 1, per cui 1 \in P_n e tutti gli altri elementi di P_n sono i prodotti di due fattori primi distinti. Ma n ha solamente due fattori primi distinti, che possiamo chiamare p e q, quindi l’unico prodotto possibile di questo tipo è pq (dobbiamo scartare per definizione eventuali divisori non privi di quadrati, come p^2). Allora P_n = \{1, pq\}. Per quanto riguarda invece D_n, gli unici elementi possibili per definizione sono i divisori che sono il prodotto di un solo numero primo, perché 1 è l’unico numero dispari minore o uguale di k = 2. Ma il prodotto di un unico numero primo è il numero primo stesso, per cui gli elementi di D_n sono semplicemente i fattori primi di n, ossia D_n = \{p, q\}. Il caso base è quindi verificato, essendo \prod_{a \in P_n} a = 1 \cdot pq = p \cdot q e \prod_{b \in D_n} b = p \cdot q.

Supponiamo ora che la proprietà sia verificata per k - 1 e dimostriamola per k, con k \geq 3.
Ripartiamo dalle equazioni (3) e (4) viste nella dimostrazione della proprietà precedente:

P_n = P_{n^{\prime}} \cup \left( p \cdot D_{n^{\prime}} \right) \tag{3}
D_n = D_{n^{\prime}} \cup \left( p \cdot P_{n^{\prime}} \right) \tag{4}

Per la (3), essendo l’unione disgiunta, il prodotto degli elementi di P_n è uguale al prodotto degli elementi di P_{n^{\prime}} per il prodotto di quelli dell’insieme p \cdot D_{n^{\prime}}. Inoltre, essendo p \cdot D_{n^{\prime}} = \{p d_1^{\prime}, p d_2^{\prime}, \ldots, p d_{|D_n^{\prime}|}^{\prime}\}, dove d_1^{\prime}, d_2^{\prime}, \ldots, d_{|D_n^{\prime}|}^{\prime} sono gli elementi di D_{n^{\prime}}, raccogliendo a sinistra tutti i fattori p si ha che il prodotto degli elementi di p \cdot D_{n^{\prime}} è uguale a p^{|D_n^{\prime}|} per il prodotto degli elementi di D_{n^{\prime}}:

\begin{aligned} \prod_{a \in P_n} a & = \prod_{a^{\prime} \in P_{n^{\prime}}} a^{\prime} \cdot \prod_{x \in p \cdot D_{n^{\prime}}} x \\ & = \prod_{a^{\prime} \in P_{n^{\prime}}} a^{\prime} \cdot \left( p^{|D_n^{\prime}|} \prod_{b^{\prime} \in D_{n^{\prime}}} b^{\prime} \right) \end{aligned}

Ma, per ipotesi di induzione, il prodotto degli elementi di P_{n^{\prime}} è uguale al prodotto degli elementi di D_{n^{\prime}}, perciò possiamo porli entrambi pari ad una costante P:

\prod_{a \in P_n} a = P \cdot \left( p^{|D_n^{\prime}|} \cdot P \right) \tag{5}

Partendo dalla formula (4) si può fare un ragionamento analogo, ottenendo:

\prod_{b \in D_n} b = \prod_{b^{\prime} \in D_{n^{\prime}}} b^{\prime} \cdot \left( p^{|P_n^{\prime}|} \prod_{a^{\prime} \in P_{n^{\prime}}} a^{\prime} \right)

Da cui:

\prod_{b \in D_n} b = P \cdot \left( p^{|P_n^{\prime}|} \cdot P \right) \tag{6}

Ora, confrontando le formule (5) e (6), ed osservando che, per la Proprietà N.8, |D_n^{\prime}| = |P_n^{\prime}|, otteniamo l’uguaglianza tra il prodotto degli elementi di P_n e quello degli elementi di D_n:

\begin{aligned} \prod_{a \in P_n} a & = \\ P \cdot \left( p^{|D_n^{\prime}|} \cdot P \right) & = \\ P \cdot \left( p^{|P_n^{\prime}|} \cdot P \right) & = \\ \prod_{b \in D_n} b \end{aligned}

Nel prossimo articolo vedremo che le Proprietà N.8 ed N.9 giustificano la definizione di un’importante funzione della teoria dei numeri: la funzione di Möbius.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.