OliForum Matematico

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!

Usa il teorema cinese del resto.

Si può risolvere senza congruenze?

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

Gauss91 ha scritto:Usa il teorema cinese del resto.

puoi farmi vedere i passaggi con TCR?

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

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.

Gauss91 ha scritto: $ x=1643 + 330k $,Ora si verificano $ 1643 $ e $ 330 $ con i divisori iniziali:

ma questo 1643 da dv viene?

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.

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.

Gauss91 ha scritto:$ x=(3\cdot5\cdot11)+(2\cdot2\cdot2\cdot5\cdot11)+(3\cdot2\cdot3\cdot11)+(4\cdot7\cdot2\cdot3\cdot5)=1643 $, soluzione unica a .

veramente io il teorema non l'ho capito..forse è questo il fatto.perchè moltiplici 2*2*2*5*11 e poi 3*2*3*11 e poi 4*7*2*3*5

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

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

ma quando fai $ a_2 $ e poi di devi calcolare l'inverso di $ b_2 $ come fai?

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 a modulo m si può solo se (a,m)=1 ed equivale a risolvere la diofantea
ax+my=1
che si risolve, ad esempio con l'algoritmo euclideo dell'MCD svolto a ritroso.