Ciao ragazzi spero di non avere sbagliato sezione. Qualcuno potrebbe spiegarmi questo problema :
Il sistema stellare di Alfa Centauri ha un numero impressionante di pianeti
che gli orbitano attorno. Alcuni esperti di numerologia hanno osservato che
tale numero e il piu piccolo intero positivo che: diviso per 8 dia resto 1, diviso
per 9 dia resto 2, diviso per 10 dia resto 3, diviso per 11 dia resto 4, diviso
per 12 dia resto 5.
Quanti sono i pianeti?
Grazie!
alfa centauri
Puoi provare a dare "condizioni successive": trovi con facili calcoli (o anche per verifica diretta) che il primo numero che diviso per 8 dà resto 1 e diviso per 9 dà resto 2 è il 65. Ovviamente tutti i numeri che soddisfano tale condizione saranno dati da questo sommandogli un multiplo del lcm di 8 e 9, cioè $ 65+72k $.
Deve dare poi resto 3 diviso per 10: 65 dà resto 5, 72 resto 2, quindi si vede facilmente che il più piccolo numero che soddisfa questo secondo passo è $ 65+4\cdot72 = 353 $. Tutti saranno dati da questo sommandogli un multiplo del lcm di 8, 9 e 10, cioè $ 353+360k $. E continui così fino a soddisfare tutte le condizioni.
E' lungo ma funziona.
Questo è il caso generale. Nel caso particolare in questione, puoi liquidare il problema istantaneamente osservando che in ogni condizione la differenza tra divisore e resto è 7: il numero cercato è $ lcm(8, 9, 10, 11, 12) - 7 $, ossia $ 3953 $.
Deve dare poi resto 3 diviso per 10: 65 dà resto 5, 72 resto 2, quindi si vede facilmente che il più piccolo numero che soddisfa questo secondo passo è $ 65+4\cdot72 = 353 $. Tutti saranno dati da questo sommandogli un multiplo del lcm di 8, 9 e 10, cioè $ 353+360k $. E continui così fino a soddisfare tutte le condizioni.
E' lungo ma funziona.
Questo è il caso generale. Nel caso particolare in questione, puoi liquidare il problema istantaneamente osservando che in ogni condizione la differenza tra divisore e resto è 7: il numero cercato è $ lcm(8, 9, 10, 11, 12) - 7 $, ossia $ 3953 $.
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"
Dunque, condizione necessaria (ma non sufficiente) affinché le condizioni siano rispettate, è che lo siano per i fattori primi dei divisori in questione. Quindi la condizione necessaria è espressa (è facile verificarlo) dal seguente sistema:
$ x\equiv 1 \pmod2 $
$ x\equiv 2 \pmod3 $
$ x\equiv 3 \pmod5 $
$ x\equiv 4 \pmod{11} $
Le condizioni del TCR sono così soddisfatte, e impostando una semplice sommatoria si ha $ x=1643 + 330k $, dato che $ 330=lcm(2,3,5,11) $.
Ora si verificano $ 1643 $ e $ 330 $ con i divisori iniziali:
$ 1643\equiv 3 \pmod8 $ e $ 330\equiv 2 \pmod8 $
$ 1643\equiv 5 \pmod9 $ e $ 330\equiv 6 \pmod9 $
$ 1643\equiv 3 \pmod{10} $ e $ 330\equiv 0 \pmod{10} $
$ 1643\equiv 4 \pmod{11} $ e $ 330\equiv 0 \pmod{11} $
$ 1643\equiv 11 \pmod{12} $ e $ 330\equiv 6 \pmod{12} $
Il problema è quindi ora trovare il più piccolo $ k $ tale che
$ 3+2k\equiv1 \pmod8 $
$ 5+6k\equiv2 \pmod9 $
$ 11+6k\equiv5 \pmod{12} $
Che dà $ k=7 $ da cui la soluzione finale $ x=1643+7\cdot330=3953 $.
$ x\equiv 1 \pmod2 $
$ x\equiv 2 \pmod3 $
$ x\equiv 3 \pmod5 $
$ x\equiv 4 \pmod{11} $
Le condizioni del TCR sono così soddisfatte, e impostando una semplice sommatoria si ha $ x=1643 + 330k $, dato che $ 330=lcm(2,3,5,11) $.
Ora si verificano $ 1643 $ e $ 330 $ con i divisori iniziali:
$ 1643\equiv 3 \pmod8 $ e $ 330\equiv 2 \pmod8 $
$ 1643\equiv 5 \pmod9 $ e $ 330\equiv 6 \pmod9 $
$ 1643\equiv 3 \pmod{10} $ e $ 330\equiv 0 \pmod{10} $
$ 1643\equiv 4 \pmod{11} $ e $ 330\equiv 0 \pmod{11} $
$ 1643\equiv 11 \pmod{12} $ e $ 330\equiv 6 \pmod{12} $
Il problema è quindi ora trovare il più piccolo $ k $ tale che
$ 3+2k\equiv1 \pmod8 $
$ 5+6k\equiv2 \pmod9 $
$ 11+6k\equiv5 \pmod{12} $
Che dà $ k=7 $ da cui la soluzione finale $ x=1643+7\cdot330=3953 $.
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"
Oppure a mano:
$ x=12k+5 $ quindi
$ x\equiv 4 \mod 11 $ diventa
$ k\equiv -1\mod 11 $ da cui $ k=11h-1 $ ovvero $ x=132h-7 $
dunque
$ 132h\equiv 0 \mod 10 $
da cui $ h\equiv 0\mod 5 $
e dunque $ x=60\cdot 11j-7 $ da cui
$ 60\cdot 11j \equiv 0\mod 9 $ e dunque $ j\equiv 0\mod 3 $
perciò $ x=180\cdot 11i-7 $ che porta a
$ 180\cdot 11 i\equiv0\mod 8 $ da cui $ i=2n $ e dunque
$ x=360\cdot 11n-7 $ che per n=1 da proprio il risultato detto.
$ x=12k+5 $ quindi
$ x\equiv 4 \mod 11 $ diventa
$ k\equiv -1\mod 11 $ da cui $ k=11h-1 $ ovvero $ x=132h-7 $
dunque
$ 132h\equiv 0 \mod 10 $
da cui $ h\equiv 0\mod 5 $
e dunque $ x=60\cdot 11j-7 $ da cui
$ 60\cdot 11j \equiv 0\mod 9 $ e dunque $ j\equiv 0\mod 3 $
perciò $ x=180\cdot 11i-7 $ che porta a
$ 180\cdot 11 i\equiv0\mod 8 $ da cui $ i=2n $ e dunque
$ x=360\cdot 11n-7 $ che per n=1 da proprio il risultato detto.
Semplicemente dall'impostazione del sistema che rientri nelle condizioni previste nel TCR, ossia che tutti i divisori siano primi fra loro:
$ x\equiv 1 \pmod2 $
$ x\equiv 2 \pmod3 $
$ x\equiv 3 \pmod5 $
$ x\equiv 4 \pmod{11} $
Da questo sistema si ottiene, per il TCR, $ x=(3\cdot5\cdot11)+(2\cdot2\cdot2\cdot5\cdot11)+(3\cdot2\cdot3\cdot11)+(4\cdot7\cdot2\cdot3\cdot5)=1643 $, soluzione unica a meno di multipli di $ lcm(2,3,5,11)=330 $.
Insomma ho solo applicato il cinesino.
$ x\equiv 1 \pmod2 $
$ x\equiv 2 \pmod3 $
$ x\equiv 3 \pmod5 $
$ x\equiv 4 \pmod{11} $
Da questo sistema si ottiene, per il TCR, $ x=(3\cdot5\cdot11)+(2\cdot2\cdot2\cdot5\cdot11)+(3\cdot2\cdot3\cdot11)+(4\cdot7\cdot2\cdot3\cdot5)=1643 $, soluzione unica a meno di multipli di $ lcm(2,3,5,11)=330 $.
Insomma ho solo applicato il cinesino.
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"
Metodo "furbo" che bypassa il TCR:
Sappiamo che il numero x che cerchiamo dà resto 1 mod 8, 2 mod 9, ..., 5 mod 12.
Ma allora y = x + 7 darà resto 8 mod 8, 9 mod 9, ..., 12 mod 12, cioè x+7 sarà un multiplo di 8, 9, 10, 11 e 12, e sarà al minimo il loro mcm, cioè 3960. Segue che x = y - 7 = 3953.
Sappiamo che il numero x che cerchiamo dà resto 1 mod 8, 2 mod 9, ..., 5 mod 12.
Ma allora y = x + 7 darà resto 8 mod 8, 9 mod 9, ..., 12 mod 12, cioè x+7 sarà un multiplo di 8, 9, 10, 11 e 12, e sarà al minimo il loro mcm, cioè 3960. Segue che x = y - 7 = 3953.
Membro dell'EATO.
Ci sono 10 tipi di persone: c'è chi sa leggere il codice binario e chi no.
I nemici dell'italiano sono miei nemici.
Ci sono 10 tipi di persone: c'è chi sa leggere il codice binario e chi no.
I nemici dell'italiano sono miei nemici.
Sia
$ x\equiv a_1 \pmod{d_1} $
$ x\equiv a_2 \pmod{d_2} $
$ \cdots $
$ x\equiv a_n \pmod{d_n} $
Con $ d_1, \cdots, d_n $ a due a due coprimi. Sia
$ b_i = \displaystyle\prod_{j \neq i}{d_i} $, e sia $ c_i $ l'inverso di $ b_i $ modulo $ d_i $ (cioè $ b_ic_i \equiv 1 \pmod{d_i} $).
Allora il TCR dice che la soluzione è
$ x=\displaystyle\sum_{i=1}^{n}{a_ib_ic_i} $
e che questa soluzione è unica a meno di multipli di $ lcm(d_1, ..., d_n) $.
Ho solo applicato il teorema
$ x\equiv a_1 \pmod{d_1} $
$ x\equiv a_2 \pmod{d_2} $
$ \cdots $
$ x\equiv a_n \pmod{d_n} $
Con $ d_1, \cdots, d_n $ a due a due coprimi. Sia
$ b_i = \displaystyle\prod_{j \neq i}{d_i} $, e sia $ c_i $ l'inverso di $ b_i $ modulo $ d_i $ (cioè $ b_ic_i \equiv 1 \pmod{d_i} $).
Allora il TCR dice che la soluzione è
$ x=\displaystyle\sum_{i=1}^{n}{a_ib_ic_i} $
e che questa soluzione è unica a meno di multipli di $ lcm(d_1, ..., d_n) $.
Ho solo applicato il teorema
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"
ma quando fai $ a_2 $ e poi di devi calcolare l'inverso di $ b_2 $ come fai?Gauss91 ha scritto:Sia
$ x\equiv a_1 \pmod{d_1} $
$ x\equiv a_2 \pmod{d_2} $
$ \cdots $
$ x\equiv a_n \pmod{d_n} $
Con $ d_1, \cdots, d_n $ a due a due coprimi. Sia
$ b_i = \displaystyle\prod_{j \neq i}{d_i} $, e sia $ c_i $ l'inverso di $ b_i $ modulo $ d_i $ (cioè $ b_ic_i \equiv 1 \pmod{d_i} $).
Allora il TCR dice che la soluzione è
$ x=\displaystyle\sum_{i=1}^{n}{a_ib_ic_i} $
e che questa soluzione è unica a meno di multipli di $ lcm(d_1, ..., d_n) $.
Ho solo applicato il teorema
In tal caso $ a_2 $ sarebbe 2, mentre $ b_2 $ è $ 110 ( \equiv 2 \pmod3 ) $. E l'inverso di 2 (mod 3) è 2, quindi $ c_2 = 2 $.
Calcolare l'inverso di un numero mod p (che esiste sempre) è facile per tentativi, dato che operi con numeri tendenzialmente piccoli in genere. Ma penso che ci siano altri metodi (che non conosco, è solo un'ipotesi) .
Calcolare l'inverso di un numero mod p (che esiste sempre) è facile per tentativi, dato che operi con numeri tendenzialmente piccoli in genere. Ma penso che ci siano altri metodi (che non conosco, è solo un'ipotesi)
."Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"