teorema cinese dei resti

Teorema

Siano $m_{1}, \dots, m_{r} \in N$ a due a due coprimi. Siano inoltre $a_{1}, \dots, a_{r} \in Z$ . Allora il sistema di congruenze nell’incognita $x$ :

⎩ ⎨ ⎧ x \equiv a_{1} (mod m_{1}) x \equiv a_{2} (mod m_{2}) ⋮ x \equiv a_{r} (mod m_{r})

ammette una soluzione $y_{1}$ . Inoltre, se $y_{2}$ è un’altra soluzione si ha

y_{1} \equiv y_{2} (mod M) con M = m_{1} \cdot m_{2} \cdot \dots \cdot m_{r} .

Dimostrazione

Consideriamo dapprima il sistema:

⎩ ⎨ ⎧ x \equiv 1 (mod m_{1}) x \equiv 0 (mod m_{2}) ⋮ x \equiv 0 (mod m_{r})

Dalle ipotesi si ha che $m_{1}, m_{2}, \dots, m_{r}$ sono a due a due coprimi.

Per Bezout, $\exists α, β \in Z$ tali che

1 = g cd (m_{1}, m_{2} \dots m_{r}) = α m_{1} + β (m_{2} \dots m_{r}) .

$1 - α m_{1} = β (m_{2} \dots m_{r})$
$1 - α m_{1}$ mod $m_{1}$ vale $1$
$1 - α m_{1}$ mod $m_{2}$ vale $β (m_{2} \dots m_{r})$ mod $m_{2}$ che è $0$
$⋮$
$1 - α m_{r}$ mod $m_{r}$ vale $0$

Quindi il sistema ha soluzione $x_{1} = 1 - α m_{1}$ .

Analogamente si trovano soluzioni $x_{2}, \dots, x_{r}$ per i sistemi:

⎩ ⎨ ⎧ x \equiv 0 (mod m_{1}) x \equiv 1 (mod m_{2}) ⋮ x \equiv 0 (mod m_{r}) \dots ⎩ ⎨ ⎧ x \equiv 0 (mod m_{1}) x \equiv 0 (mod m_{2}) ⋮ x \equiv 1 (mod m_{r})

La soluzione del sistema generale è data da

x = a_{1} x_{1} + a_{2} x_{2} + \dots + a_{r} x_{r} .

poiché $a_{i} x_{i} \equiv a_{i} (mod m_{i})$ e $a_{i} x_{i} \equiv 0 (mod m_{j})$ per $j \neq = i$ .

Siano ora $x, y$ due soluzioni del sistema generale. Allora

x \equiv a_{i} (mod m_{i}) e y \equiv a_{i} (mod m_{i}) \forall i = 1, \dots, r .

Cioè $x - y \equiv a_{i} - a_{i} \equiv 0 (mod m_{i})$ per ogni $i$ , ovvero $x - y$ è multiplo di ciascun $m_{i}$ . Poiché i $m_{i}$ sono a due a due coprimi, $x - y$ è multiplo di $M = m_{1} m_{2} \dots m_{r}$ , ovvero

x \equiv y (mod M) .

Esempio

Risolviamo il sistema

⎩ ⎨ ⎧ x \equiv 3 (mod 5) x \equiv 1 (mod 2) x \equiv 2 (mod 3)

$x \equiv 1 (mod 2)$ significa che $x$ è dispari, quindi $x = 2 k + 1$ per qualche $k \in Z$ .

$x \equiv 2 (mod 3)$ implica che $x = 3 n + 2$ per qualche $n \in Z$ .

per avere entrambe le condizioni, poniamo $x = 3 (2 l + 1) + 2 = 6 l + 5$ per qualche $l \in Z$ .

Infine, imponiamo $x \equiv 3 (mod 5)$ , $x = 6 (5 m + 3) + 5 = 30 m + 23$ per qualche $m \in Z$ .

2brain

Esplora

teorema cinese dei resti

teorema cinese dei resti

Teorema

Dimostrazione

Esempio

Risorse

Vista grafico

Tabella dei contenuti

Link entranti