Teorema cinese del resto

[giupar93]

Buona sera ragazzi, non riesco a capire il funzionamento del teorema cinese del resto, le mie dispense sono poco chiare.
Come risolvo questo sistema col teorema cinese del resto:

$ { ( x-=4(mod5) ),( x-=6(mod4) ),( x-=2(mod9) ):} $

???

Grazie mille anticipatamente

[vict85]

[xdom="vict85"]Il [regolamento]1_4[/regolamento] prevede un tentativo di risoluzione da parte tua.[/xdom]

Al di là del teorema del resto in sé, la seconda equazione può essere semplificata in qualche modo?

[giupar93]

vedendola meglio..ti direi che potrebbe essere scritta:
$x-=3(mod2)$ ?? .-.

[vict85]

Se \(\displaystyle x = 6 + 4k \) allora \(\displaystyle x \) è senz'altro pari, mentre \(\displaystyle 3 \), soluzione dell'equazione scritta da te, è dispari. Le due equazioni non sono certamente equivalenti. Semmai avrebbe senso scrivere \(\displaystyle x\equiv 2\!\!\!\!\pmod{4} \), non ti sembra?

Comunque \(\displaystyle 5 \), \(\displaystyle 4 \) e \(\displaystyle 9 \) sono coprimi a due a due quindi si può usare il teorema cinese del resto. Nota che tutte le soluzioni differiscono di un multiplo di \(\displaystyle n = 4\times 5\times 9 = 180 \).

Per risolverlo puoi usare varie strade. Un modo automatico è usare l'algoritmo esteso di Euclide, ma non è necessariamente il più rapido.

Nota che \(\displaystyle 5\times 9 = 45 = 44 + 1 = 11\times 4 + 1 \), pertanto risulta \(\displaystyle 1\times 45 - 11\times 4 = 1 \) anche senza usare l'algoritmo esteso di Euclide.

Similmente, \(\displaystyle 4\times 9 = 36 = 35 + 1 = 7\times 5 + 1 \). Non così fortunata è la coppia \(\displaystyle (9,20) \) che quindi richiede più calcolo. Con un minimo di ragionamento esce \(\displaystyle 100 - 99 = 1 \) ovvero \(\displaystyle 5\times 20 - 11\times 9 = 1 \).

Ora, vediamo se riesci a concludere.