Lezione 7 (27 marzo 2000 h. 9-11)

Definizione di congruenza e prime proprietà

Definizione 7.1   Siano $a,b\in\mathbb Z$, si dice che a è congruo a b modulo n (in simboli $a\cong b \quad{\rm mod}\ n$) se $n\mathrel{\big\vert}a-b$.

Proposizione 7.2   Valgono le seguenti proprietà:

1.

(proprietà riflessiva)  $a\cong a \quad{\rm mod}\ n$ per ogni $a,n\in\mathbb Z$;

2.

(proprietà simmetrica)  $a\cong b\quad{\rm mod}\ n\Rightarrow b\cong a \quad{\rm mod}\ n$ per ogni $a,b,n\in\mathbb Z$;

3.

(proprietà transitiva)  $a\cong b \quad{\rm mod}\ n$ e $b\cong c\quad{\rm mod}\ n\Rightarrow a\cong c\quad{\rm mod}\ n$ per ogni $a,b,c,n\in\mathbb Z$.

Dimostrazione.  1. $n\mathrel{\big\vert}0=a-a$ per ogni $n\in\mathbb Z$.

2. Se $n\mathrel{\big\vert}a-b$ allora a-b=kn e quindi b-a=(-k)n e quindi $n\mathrel{\big\vert}b-a$ ossia $b\cong a \quad{\rm mod}\ n$.

3. Se $a\cong b \quad{\rm mod}\ n$ e $b\cong c \quad{\rm mod}\ n$ allora a-b=kn e b-c=hn e quindi a-c=a-b+b-c=kn+hn=(k+h)n e quindi $a\cong c\quad{\rm mod}\ n$.     $\square$

Ricordiamo la definizione di relazione d'equivalenza su un insieme.

Definizione 7.3   Una relazione $\cal R$ su X si dice d'equivalenza se

1.

è riflessiva, ossia $\forall x\in X$ $x\cal R x$;

2.

è simmetrica, ossia $\forall x,y\in X$ $x\cal R Y\Rightarrow y\cal R x$

3.

è transitiva, ossia $\forall x,y,z\in X$ $(x\cal R y \hbox{\rm { e }} y\cal R z)\Rightarrow x\cal R z$.

Osservazione 7.4   La proposizione precedente può essere allora rienunciato dicendo che la relazione di congruenza modulo n è una relazione d'equivalenza su $\mathbb Z$.

Classi di congruenza

Definizione 7.5   Siano $a,n\in\mathbb Z$, si chiama classe di congruenza di a modulo n l'insieme

$$\left[a\right]_n=\{x\in\mathbb Z\mid x\cong a\quad{\rm mod}\ n\}.$$

Indicheremo $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\textsty... ...scriptstyle {}n\mathbb Z}}=\big\{\left[a\right]_n\bigm\vert a\in\mathbb Z\big\}$

Osservazione 7.6   $x\cong a\quad{\rm mod}\ n$ se e solo se $n\mathrel{\big\vert}(x-a)$ se e solo se esiste $k\in\mathbb Z$ tale che x-a=kn se e solo se esiste $k\in\mathbb Z$ tale che x=a+kn e quindi

$$\left[a\right]_n=\{a+kn\mid k\in\mathbb Z\}.$$

Proposizione 7.7  

1.

 per ogni $a\in\mathbb Z$ $a\in\left[a\right]_n$

2.

 per ogni $a,b\in\mathbb Z$ $\left[a\right]_n=\left[b\right]_n$ se e solo se $a\cong b \quad{\rm mod}\ n$.

3.

 per ogni $a,b\in\mathbb Z$ $\left[a\right]_n\cap\left[b\right]_n\ne\varnothing\Rightarrow\left[a\right]_n=\left[b\right]_n$.

Dimostrazione.  1. Segue dalla proprietà riflessiva.

2. Se $\left[a\right]_n=\left[b\right]_n$ in particolare $b\in\left[b\right]_n=\left[a\right]_n$ e quindi $a\cong b \quad{\rm mod}\ n$. Viceversa sia $a\cong b \quad{\rm mod}\ n$. Se $x\in \left[a\right]_n$ allora $x\cong a\quad{\rm mod}\ n$; per la proprietà transitiva $x\cong b\quad{\rm mod}\ n$ ossia $x\in\left[b\right]_n$. Analogamente se $x\in\left[b\right]_n$ allora $x\in \left[a\right]_n$ e quindi le due classi coincidono.

3. Se $x\in\left[a\right]_n\cap\left[b\right]_n$ allora $x\cong a\quad{\rm mod}\ n$ e $x\cong b\quad{\rm mod}\ n$, usando le proprietà simmetrica e transitiva si ha allora che $a\cong b \quad{\rm mod}\ n$ e quindi, per la (2), appena dimostrata, $\left[a\right]_n=\left[b\right]_n$.     $\square$

In generale data una relazione d'equivalenza su un insieme

Le classi modulo n sono esattamente n

Proposizione 7.8   Se n>0 e r è il resto della divisione euclidea di a per n allora $a\cong r\quad{\rm mod}\ n$.

Dimostrazione.  a=nq+r quindi $n\mathrel{\big\vert}nq=a-r$.     $\square$

Corollario 7.9   Se n>0 allora $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}$ ha esattamente n elementi.

Dimostrazione.  Da 7.8 e dalla 2 di 7.7 segue immediatamente che l'insieme in questione ha al più n elementi e precisamente $\left[0\right]_n,\left[1\right]_n,\dots,\left[n-1\right]_n$. D'altra parte se $0\le h<k<n$ allora 0<k-h<n e quindi $n\not\mathrel{\big\vert}(k-h)$ e quindi (sempre per la 2 di 7.7) $\left[h\right]_n\ne\left[k\right]_m$.     $\square$

   
Successioni di tipo Fibonacci

La successione di Fibonacci è la successione $\{F_n\}$ così definita

$$\left\{ \begin{array}{rclcl} F_0 & = & 0 \\ F_1 & = & 1\\... ...= & F_{n+1}+F_n &&\hbox{\rm {se }} n\ge 0 \end{array} \right.$$

Esercizio 7.1    Si provi che (F_n+1,F_n)=1 per ogni $n\ge0$.
Soluzione

Esercizio 7.2    Si provi che

$$F_n=\frac{1}{\sqrt{5}}\Big(\frac{1+\sqrt{5}}{2}\Big)^n -\frac{1}{\sqrt{5}}\Big(\frac{1-\sqrt{5}}{2}\Big)^n$$

Soluzione

Esercizio 7.3    Si provi che dette $\alpha$ e $\beta$ le radici del polinomio x²-3x+2, allora le successioni $A\alpha^n+B\beta^n$ al variare di A e B sono tutte e sole le successioni tali che

x_n+2=3x_n+1-2

Soluzione

Esercizio 7.4    Si determini la successione tale che

$$\left\{ \begin{array}{rcl} x_{n+2} & = & 4x_{n+1}-3 \\ x_{0} & = & 0 \\ x_{1} & = & 1 \end{array} \right.$$

Soluzione

In effetti si può dimostrare il seguente

Teorema 7.10   Siano $a_0,\dots, a_{k-1}\in\mathbb R$ (o anche $\mathbb C$), tali che il polinomio $P(t)=t^k-\sum_{i=0}a_it^i$ ammette k radici distinte $\alpha_1,\dots,\alpha_k$, allora le successioni del tipo

$$x_n = A_1\alpha_1^n+\wedge_2\alpha_2^n+\dots+A_k\alpha_k^n\qquad A_i\in\mathbb R\ (\mathbb C)$$

sono tutte e sole le successioni tali che

$$x_{n+k} = \sum_{i=0}a_ix_{n+i} \qquad \forall \, n\in\mathbb N.$$

In più, dati numeri $b_0,\dots,b_{k-1}\in\mathbb R$ ($\mathbb C$) esiste un'unica di tali successioni tale che

$$x_0=b_0,\ x_1=b_1, \dots, x_{k-1}=b_{k-1}.$$