Teorema cinese del resto (senza dimostrazione)
Inviato: 15 mar 2005, 13:36
Questo stumento può risultare molto utile e non so se fa parte del bagaglio olimpionico degli studenti liceali...
Teorema Cinese del Resto
Siano $ a_1,\ldots,a_n\in\mathbb{N} $ coprimi. Siano $ b_1,\ldots,b_n\in\mathbb{N} $ tali che $ b_i<a_i $ per ogni $ i = 1,\ldots,n $. Allora esiste una soluzione al sistema di equazioni congruenziali
$ \left\{ \begin{array}{l} x \equiv_{a_1} b_1\\ x \equiv_{a_2} b_2\\ \vdots\\ x \equiv_{a_n} b_n\\ \end{array} \right. $
Inolte la soluzione è unica modulo $ a_1\cdot\ldots\cdot a_n $
Tralascio la dimostrazione perché ho un po' di cose da fare. Chi vuole può provare a farlo per esercizio.
Un simile teorema può essere utile per risolvere problemi come il seguente:
Abbiamo una collezione di biglie. Raccogliendole 3 a 3 ne rimangono 2, raccogliendole 5 a 5 ne rimangono 4, raccogliendole 14 a 14 ne rimangono 10. Quante palline ho? (sono meno di 210)
Il teorema non fornisce il numero di palline, dice solo che una tale situazione è possiblile. Tuttavia è facile trovare una soluzione a problemi semplici. Per cose più teoriche il teorema fornisce le condizioni per l'esistenza di una data soluzione.
Detto questo, tra qualche giorno proporrò un problema che richiederà l'uso di questo teorema.
Ps (per i gestori):
Un esercizio che richieda il teorema cinese del resto può essere messo sotto matematica elementare? Non si tratta di fare conti, ma di usare il teorema vero e proprio.
Teorema Cinese del Resto
Siano $ a_1,\ldots,a_n\in\mathbb{N} $ coprimi. Siano $ b_1,\ldots,b_n\in\mathbb{N} $ tali che $ b_i<a_i $ per ogni $ i = 1,\ldots,n $. Allora esiste una soluzione al sistema di equazioni congruenziali
$ \left\{ \begin{array}{l} x \equiv_{a_1} b_1\\ x \equiv_{a_2} b_2\\ \vdots\\ x \equiv_{a_n} b_n\\ \end{array} \right. $
Inolte la soluzione è unica modulo $ a_1\cdot\ldots\cdot a_n $
Tralascio la dimostrazione perché ho un po' di cose da fare. Chi vuole può provare a farlo per esercizio.
Un simile teorema può essere utile per risolvere problemi come il seguente:
Abbiamo una collezione di biglie. Raccogliendole 3 a 3 ne rimangono 2, raccogliendole 5 a 5 ne rimangono 4, raccogliendole 14 a 14 ne rimangono 10. Quante palline ho? (sono meno di 210)
Il teorema non fornisce il numero di palline, dice solo che una tale situazione è possiblile. Tuttavia è facile trovare una soluzione a problemi semplici. Per cose più teoriche il teorema fornisce le condizioni per l'esistenza di una data soluzione.
Detto questo, tra qualche giorno proporrò un problema che richiederà l'uso di questo teorema.
Ps (per i gestori):
Un esercizio che richieda il teorema cinese del resto può essere messo sotto matematica elementare? Non si tratta di fare conti, ma di usare il teorema vero e proprio.