Lezione 2 (24 febbraio 1999 h. 9.30-10.30)

Divisione euclidea tra interi

Teorema 2.1 (divisione euclidea)   Siano $n,m\in\mathbb Z$ con $m\ne0$ allora esistono unici $q,r\in \mathbb Z$ tali che

$$n=mq+r\quad\hbox{\rm {con}}\quad 0\le r<\left\vert m\right\vert.$$

Dim.  Dimostriamo l'esistenza. Se $n\ge 0$ e m>0 la tesi segue dalla proposizione 1.4 e dall'osservazione che $\left\vert m\right\vert=m$.

Supponiamo ora n<0 e m>0. Allora -n>0 e quindi per il caso precedente si ha che esistono $q,r\in \mathbb Z$ tali che -n=mq+r e $0\le r<m=\left\vert m\right\vert$. E quindi n=m(-q)-r. Se r=0 abbiamo finito, se invece 0<r<m allora $0<m-r<m=\left\vert m\right\vert$ e n=m(-q)-r=m(-q)-m+m-r=m(-1-q)+(m-r).

Sia infine m<0 allora -m>0, quindi per i due casi precedenti esistono $q,r\in \mathbb Z$ tali che n=(-m)q+=m(-q)+r con $0\le r<-m=\left\vert m\right\vert$.

Dimostriamo ora l'unicità. Supponiamo che n=mq+r=mq'+r' con $0\le r,r'<\left\vert m\right\vert$. Supponiamo che $r'\ge r$, allora m(q-q')=r'-r e quindi passando ai moduli si ha $\left\vert m\right\vert\left\vert q-q'\right\vert=\left\vert r'-r\right\vert=r'-r<\left\vert m\right\vert$,da cui $0\le\left\vert q-q'\right\vert<1$ e quindi $\left\vert q-q'\right\vert=0$ ovvero q=q'. Ma allora da mq+r=mq'+r' segue che anche r=r'.     $\square$

Scrittura in base arbitraria degli interi

Teorema 2.2 (scrittura degli interi 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 e 3 allora $\varepsilon_i=\varepsilon'_i$ per ogni $i\in\mathbb N$.

Dim.  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$