Lezione 5 (13 marzo 2000 h. 9-11)

   
Scrittura in base arbitraria dei naturali.

Teorema 5.1 (scrittura dei naturali in base arbitraria)   Sia $b\ge2$ un intero. Allora per ogni $n\in\mathbb N$ esiste una successione $\{\varepsilon_i\}_{i\in\mathbb N}$ di interi tali che:

1.

  $\{\varepsilon_i\}$ è definitivamente nulla (i.e. esiste $i_0\in\mathbb N$ tale che $\varepsilon_i=0$ per ogni i>i₀);

2.

  $0\le\varepsilon_i<b$ per ogni $i\in\mathbb N$;

3.

  $n=\sum_{i=0}^\infty \varepsilon_i b^i$.

Tale successione è unica, ovvero se $\{\varepsilon_i\}_{i\in\mathbb N}$ e $\{\varepsilon'_i\}_{i\in\mathbb N}$ verificano la 1, 2, 3 allora $\varepsilon_i=\varepsilon'_i$ per ogni $i\in\mathbb N$.

Dimostrazione.  Dimostriamo l'esistenza per induzione su n. Se n=0 basta prendere $\varepsilon_i=0$ per ogni $i\in\mathbb N$. Supponiamo ora n>0 e che la tesi sia vera per ogni k<n. Siano q,r tali che n=bq+r con $0\le r<b$. Dato che $b\ge2$ si ha che $0\le q<bq\le bq+r=n$ e quindi per ipotesi di induzione esiste una successione definitivamente nulla $\{\delta_i\}$, costituita di interi tali che $0\le\delta_i<b$ per ogni i e tale che $q=\sum\limits_{i=0}^\infty \delta_i b^i$. Ma allora

$$n=bq+r=b\sum\limits_{i=0}^\infty \delta_i b^i+r=\sum\limits_{... ...ty\delta_{i-1}b^i+r=\sum\limits_{i=0}^\infty \varepsilon_i b^i$$

dove si è posto $\varepsilon_0=r$ e $\varepsilon_i=\delta_{i-1}$ per ogni i>0. La successione $\{\varepsilon_i\}$ è definitivamente nulla, dato che lo è $\{\delta_i\}$ ed inoltre $0\le\varepsilon_i=\delta_{i-1}<b$ per ogni i>0 e $0\le\varepsilon_0=r<b$.

Dimostriamo ora l'unicità. Procediamo per induzione su n. Se $n=0=\sum_i\varepsilon_ib^i$ allora ogni addendo della somma essendo nonnegativo, deve essere nullo e quindi $\varepsilon_i=0$ per ogni i.

Supponiamo ora n>0 e che l'espressione in base b sia unica per tutti i numeri k<n. Sia n tale che $n=\sum\limits_{i=0}^\infty \varepsilon_i b^i=\sum\limits_{i=0}^\infty \varepsilon'_i b^i$. Allora possiamo scrivere

$$n=b\sum\limits_{i=1}^\infty \varepsilon_i b^{i-1}+\varepsilon... ...\sum\limits_{i=1}^\infty \varepsilon'_i b^{i-1}+\varepsilon'_0$$

ma per l'unicità della divisione euclidea si ha che $\varepsilon_0=\varepsilon'_0$ e $q=\sum\limits_{i=1}^\infty \varepsilon_i b^{i-1}=\sum\limits_{i=1}^\infty \varepsilon'_i b^{i-1}$. Come prima q<n e quindi per ipotesi di induzione si ha anche che $\varepsilon_i=\varepsilon'_i$ per ogni $i\ge1$.     $\square$

Divisibilità e sue prime proprietà

Definizione 5.2   Dati due interi n,m si dice che n è un divisore di m (o che m è un multiplo di n) se esiste un $k\in\mathbb Z$ tale che m=nk. Si indica con $n\mathrel{\big\vert}m$ (si legge n divide m).

Esempio 5.3   $n\mathrel{\big\vert}0$ per ogni n mentre se $n\ne 0$ allora $0\not\mathrel{\big\vert}n$, si ha inoltre che $\pm1\mathrel{\big\vert}n$ e $\pm n\mathrel{\big\vert}n$ per ogni n.

Proposizione 5.4  

1.

  Se $n\mathrel{\big\vert}m$ e $m\mathrel{\big\vert}q$ allora $n\mathrel{\big\vert}q$.

2.

  Se $n\mathrel{\big\vert}m$ e $m\mathrel{\big\vert}n$ allora $n=\pm m$.

Dimostrazione.  1. Se m=kn e q=hm allora q=hkm=(hk)m ossia $n\mathrel{\big\vert}q$.

2. Se n=mk e m=nh allora m=hkm e quindi m(1-hk)=0 e quindi o m=0 e quindi anche n=0, oppure 1-hk=0 ma allora o h=k=1 e quindi n=m oppure n=m=-1 e quindi n=-m.     $\square$

Definizione 5.5   Il numero n si dice primo se i suoi unici divisori sono $\pm1,\pm n$.

Il massimo comun divisore: definizione, esistenza e unicità

Definizione 5.6   Dati due interi n,m non entrambi nulli, si dice che d è un massimo comun divisoretra n e m se:

1.

$d\mathrel{\big\vert}n$ e $d\mathrel{\big\vert}m$;

2.

Se $c\mathrel{\big\vert}n$ e $c\mathrel{\big\vert}m$ allora $c\mathrel{\big\vert}d$.

Proposizione 5.7   Se d e d' sono due massimi comun divisori tra n e m allora $d'=\pm d$.

Dimostrazione.  d è un divisore comune di n e m, quindi poiché d'è un massimo comun divisore si ha che $d\mathrel{\big\vert}d'$. Scambiando i ruoli di d e d' si ha allora che anche $d'\mathrel{\big\vert}d$ e quindi per 5.4 si ha che $d'=\pm d$.     $\square$

Definizione 5.8   Diremo che d è il massimo comun divisore di n e m se è un massimo comun divisore positivo. La proposizione precedente garantisce che se esiste il massimo comun divisore è unico. Esso verrà indicato con (n,m).

Teorema 5.9   Dati due numeri $n,m\in\mathbb Z$ non entrambi nulli esiste il massimo comun divisore di n ed m.

Dimostrazione.  Si consideri l'insieme $S=\{s\in\mathbb Z\mid s>0,\ \exists\,x,x\in\mathbb Z: s=nx+my\}$. $S\ne\varnothing$ dato che nn+mm>0 (dato che n e mnon sono entrambi nulli). Sia $d=nx+my=\min S$, dimostriamo che dè il massimo comun divisore. Se $c\mathrel{\big\vert}n$ e $c\mathrel{\big\vert}m$ allora n=ck e m=ch, quindi d=nx+my=ckx+chy=c(kx+hy) ossia $c\mathrel{\big\vert}d$. Dimostriamo ora che $d\mathrel{\big\vert}n$. Consideriamo la divisione euclidea tra n e d ossia n=dq+r con $0\le r<d$, se r>0 allora r=n-dq=n-(nx+my)q=n(1-qx)+(-m)y è un elemento di S. Ciò è assurdo perché r<d e $d=\min S$. Quindi r=0 ossia $d\mathrel{\big\vert}n$. In modo analogo si prova che $d\mathrel{\big\vert}m$.     $\square$

Osservazione 5.10   Dalla dimostrazione precedente segue che dati $n,m\in\mathbb Z$ esistono $x,y\in\mathbb Z$ tali che (n,m)=nx+my e che gli interi della forma nx+my con $x,y\in\mathbb Z$ sono tutti e soli i multipli di (n,m).

Definizione 5.11   $n,m\in\mathbb Z$ non entrambi nulli si dicono coprimi se (n,m)=1.

Osservazione 5.12   (n,m)=1 se e solo se esistono $x,y\in\mathbb Z$ tali che nx+my=1. Ad esempio (n,n+1)=1 per ogni n. Infatti 1=(n+1)1+n(-1).

Proposizione 5.13   Sia d=(n,m), allora $(\frac nd,\frac md)=1$.

Dimostrazione.  d=nx+my e quindi $1=\frac nd x+\frac md y$.     $\square$

   
Il coefficiente binomiale

Definizione 5.14   Siano n, $k\in \mathbb N$ con $k \le n$ si pone

$${n \choose k}= \frac {n!}{(n-k)! k !}$$

Esercizio 5.1    Provare che

$${n+1 \choose k} = {n \choose k}+{n \choose k-1}.$$

Soluzione

   
k-sottinsiemi

Definizione 5.15   Sia X un insieme e $k\in \mathbb N$, un sottinsieme $A\subseteq X$ sarà detto un k-sottinsieme se $\left\vert A\right\vert =k$. Denoteremo con ${X \choose k}$ l'insieme dei k-sottinsiemi di X. I k-sottinsiemi sono anche chiamati k-combinazioni semplici.

Proposizione 5.16   Se X è finito, allora

$$\left\vert{X \choose k}\right\vert={\left\vert X\right\vert \choose k}.$$

Dimostrazione. 

    $\square$

Definizione 5.17   Una k-combinazione con ripetizione di un insieme X è la scelta di k elementi di X, che possono essere anche ripetuti, indipendentemente dall'ordine.

Esempio 5.18   In altri termini una k combinazione di X è il risultato di k scelte indipendenti di elementi di X. Se $X=\{a,b,c,d\}$ le seguenti sono delle 3-combinazioni: aaa, abb, abc. Si osservi che aab e aba danno la stessa combinazione, dato che non ci interessa l'ordine in cui viene effettuata la scelta, ma soltanto il risultato complessivo.

Esercizio 5.2    Si elenchino tutte le 3 combinazioni dell'insieme $X=\{a,b,c,d\}$.
Soluzione

Proposizione 5.19   Se $\left\vert X\right\vert=n$ allora il numero di k-combinazioni con ripetizione di X è dato da:

$${n+k-1 \choose k}={n+k-1 \choose n-1}.$$

Esercizio 5.3    Provare che

$${n \choose 0}+{n \choose 1}+\dots+{n \choose n-1}+{n \choose n}=2^n$$

Soluzione

   
Il binomio di Newton

Proposizione 5.20   Siano a,b numeri reali, allora

$$(a+b)^n=\sum_{i=0}^n {n \choose k}a^k b ^{n-k}$$

Dimostrazione. 

    $\square$

Esercizio 5.4    Si provi che

$${n \choose 0}-{n \choose 1}+\dots+(-1)^{n-1}{n \choose n-1}+ (-1)^n{n \choose n}=0$$

Soluzione

Perché non gioco al Superenalotto!

Una sestina al Superenalotto, è un sottinsieme di 6 elementi dell'insieme dei numeri naturali da 1 a 90, quindi, per la proposizione 5.16 il numero di sestine possibili è dato da:

$${90 \choose 6}=622614630$$

Pertanto, la probabilità di vincere giocando una sestina è pari a $1/622614630=0.000000161\ \%$ di vincere giocando una sestina. Se quindi il gioco fosse equo, la puntata su una giocata dovrebbe essere pagata 622614630volte la posta. Dato che la puntata su una sestina costa 800 L., mi aspetterei, in caso di successo, un premio di $800\cdot 622614630 =498091704000$L.

Un montepremi così alto non si è ancora visto!