Sistema di congruenze

[Sk_Anonymous]

Ciao a tutti,
volevo chiedere a voi del forum se sono corretti i passaggi per trovare tutte le soluzioni del seguente sistema di congruenze:

$\{(x-=36(mod 99)),(x-=-36(mod 171)):}$


Infine, come posso trovare una soluzione che sia divisibile per $50$ ?

Grazie.
Giampaolo

1) Ho verificato con il Teorema Cinese del Resto che $-36 -36 = -72 $ sia divisibile per $gcd(99,171) = 9$

2) Mediante l'Algoritmo di Euclide, ho esplicitato $9$ come combinazione lineare di $99$ e $171$: $9=(7)99+(-4)171

3) Ho espresso $-72$ come combinazione lineare di $99$ e $171$: $-72=(-56)99+(32)171$

4) Ho combinato l'equazione $-36-36=(-56)99+(32)171$ ottenendo una soluzione particolare $x_0=-36-(-56)99=36+(32)171=5508$

5) Per trovare tutte le soluzioni ho considerato il minimo comune multiplo $[99,171]=(99*171)/gcd(99,171)=1881$

$Sol={5508+m1881 | m in Z} = [5508]1881 = [1746]1881 $

[Lord K]

Se osservi:

$1746=99*17+63$
$1746=171*10+36$

Mi sa che hai invertito alcune cosette nei conti. Riprova!

P.S. quando trovi la soluzione prova sempre come verifica a vedere che tutto combaci

[Sk_Anonymous]

Please help me!! Ho rifatto i conti ma ottengo sempre la stessa cosa.
Da cosa evinci che è sbagliato e in che passaggio ho sbagliato?

Grazie.

[misanino]

io credo che potresti sbagliare nel 3° punto, anche perchè usi -72 invece che 72 che è molto più facile.
In poche parole: devi trovare una soluzione particolare.
Quindi devi avere numeri h e k tale che
$36+k*99=-36+h*171$ cioè $72=h*171-k*99$.
Con l'algoritmo di Euclide trovi subito che k=h=1 e quindi $x_0=36+99=135$ e questa è la tua soluzione particolare.

[Neptune2]

Scusami ma stai utilizzando il teorema del resto o cosa? non dovresti ridurre quindi ognuna delle due congruenze a delle diofantee e trovarne la soluzione, poi mettere assieme le soluzioni trovate e crearne "una comune" ?

Ovvero da quel che so una soluzione $C$ di un sistema di congruenze compatibili con il teorema cinese del resto è pari alla sommatoria delle soluzioni delle singole congruenze per i resti per l'elemento $N_i$. Ove in questo caso $N_1=171$ ed $N_2 = 99$ ? (magari quest'ultima formula c'è qualcuno che te la sa spiegare meglio ).

Del resto, per far si che la soluzione sia anche divisibile per $50$ non ti basta aggiungere una terza congruenza a sistema dove dici che:

$x-=0(mod 50)$ ovvero che $x$ diviso per $50$ da resto $0$ ovvero proprio che $x$ è divisibile per $50$?

[misanino]

Il teorema cinese dei resti in realtà ti assicura solo che una soluzione esiste.
Poi in realtà, dato che una delle dimostrazioni del teorema cinese dei resti è costruttiva, ti fornisce anche un metodo per trovare una soluzione.
Nel tuo esercizio però tutto è molto più semplice e si risolve come ti ho fatto vedere io in un secondo