Sistema di congruenze

[giampfrank]

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

\( \displaystyle {\left\lbrace\matrix{{x}\equiv{36}{\left(\text{mod}{99}\right)}\\{x}\equiv-{36}{\left(\text{mod}{171}\right)}}\right.} \)


Infine, come posso trovare una soluzione che sia divisibile per \( \displaystyle {50} \) ?

Grazie.
Giampaolo

1) Ho verificato con il Teorema Cinese del Resto che \( \displaystyle -{36}-{36}=-{72} \) sia divisibile per \( \displaystyle {\gcd{{\left({99},{171}\right)}}}={9} \)

2) Mediante l'Algoritmo di Euclide, ho esplicitato \( \displaystyle {9} \) come combinazione lineare di \( \displaystyle {99} \) e \( \displaystyle {171} \): \( \displaystyle {9}={\left({7}\right)}{99}+{\left(-{4}\right)}{171}\lt{b}\frac{{r}}{\gt}\lt{b}\frac{{r}}{\gt}{3}\){H}{o}{e}{s}{p}{r}{e}{s}{s}{o} \)-72\( \displaystyle {c}{o}{m}{e}{c}{o}{m}{b}\in{a}{z}{i}{o}\ne{l}\in{e}{a}{r}{e}{d}{i} \)99\( \displaystyle {e} \)171\( \displaystyle : \)-72=(-56)99+(32)171\( \displaystyle \lt{b}\frac{{r}}{\gt}\lt{b}\frac{{r}}{\gt}{4}\){H}{o}{c}{o}{m}{b}\in{a}\to{l}'{e}{q}{u}{a}{z}{i}{o}\ne \)-36-36=(-56)99+(32)171\( \displaystyle {o}{\mathtt{{e}}}\ne{n}{d}{o}{u}{n}{a}{s}{o}{l}{u}{z}{i}{o}\ne{p}{a}{r}{t}{i}{c}{o}{l}{a}{r}{e} \)x_0=-36-(-56)99=36+(32)171=5508\( \displaystyle \lt{b}\frac{{r}}{\gt}\lt{b}\frac{{r}}{\gt}{5}\){P}{e}{r}{t}{r}{o}{v}{a}{r}{e}{t}{u}{\mathtt{{e}}}\le{s}{o}{l}{u}{z}{i}{o}{n}{i}{h}{o}{c}{o}{n}{s}{i}{d}{e}{r}{a}\to{i}{l}\min{i}{m}{o}{c}{o}\mu\ne\mu\lt{i}{p}{l}{o} \)[99,171]=(99*171)/gcd(99,171)=1881\( \displaystyle \lt{b}\frac{{r}}{\gt}\lt{b}\frac{{r}}{\gt} \)Sol={5508+m1881 | m in Z} = [5508]1881 = [1746]1881 $

[Lord K]

Se osservi:

\( \displaystyle {1746}={99}\cdot{17}+{63} \)
\( \displaystyle {1746}={171}\cdot{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

[giampfrank]

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
\( \displaystyle {36}+{k}\cdot{99}=-{36}+{h}\cdot{171} \) cioè \( \displaystyle {72}={h}\cdot{171}-{k}\cdot{99} \).
Con l'algoritmo di Euclide trovi subito che k=h=1 e quindi \( \displaystyle {x}_{{0}}={36}+{99}={135} \) e questa è la tua soluzione particolare.

[Neptune]

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 \( \displaystyle {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 \( \displaystyle {N}_{{i}} \). Ove in questo caso \( \displaystyle {N}_{{1}}={171} \) ed \( \displaystyle {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 \( \displaystyle {50} \) non ti basta aggiungere una terza congruenza a sistema dove dici che:

\( \displaystyle {x}\equiv{0}{\left(\text{mod}{50}\right)} \) ovvero che \( \displaystyle {x} \) diviso per \( \displaystyle {50} \) da resto \( \displaystyle {0} \) ovvero proprio che \( \displaystyle {x} \) è divisibile per \( \displaystyle {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