Risoluzione sistemi di congruenze per sostituzione

[Neptune2]

Mi ritrovo ad affrontare la risoluzione dei sistemi di congruenze lineari tramite il metodo della sostituzione, ed essendo che secondo i miei calcoli il sistema sembra incompatibile, e non riuscendo a dimostrare "che la mia soluzione sia realmente vera", ho pensato di riportarla qui sul forum per chiedere se a voi il procedimento sembra corretto.

$\{(x -= 2 (mod 3)),(x -= 1 (mod 4)),(x -= 1 (mod 5)):}$

Qui l'unica cosa che possiamo dire è che non essendo i moduli a due a due coprimi non possiamo usare il teorema del resto cinese.
Per la compatibilità di ogni singola congruenza, sono tutte compatibili perchè tutti i primi termini delle congruenze sono pari ad $1$ e l'mcd che otteniamo è sempre 1 che divide sia $2$ che $1$ ? oppure ho sbagliato il ragionamento?

Vediamo come risolvere il sistema iniziando da $x -= 2 (mod 3)$ dico che questa si può scrivere come:

$3|x-2$ ovvero $x-2 = 3*h$ con $h in ZZ$

Riscrivendola come congruenza abbiamo che:

$3*h -=2 (mod 3)$

Quindi $x = 3*h$ è la soluzione della prima congruenza del nostro sistema, sostituiamola nella seconda congruenza ed abbiamo:

$3*h -= 1 (mod 4)$

Qui diciamo subito che $mcd(3,4)=1|1$ ovvero la congruenza è compatibile ed ammette una ed una sola soluzione (dato che l'mcd è 1);

La sviluppiamo dicendo che quindi $4| 3*h -1$

Possiamo sostituire $3$ ad h ed abbiamo che $4|4$ ergo possiamo dire che $3*h-1 = 4*k$ con $k in ZZ$

Riscrivendocela sotto forma di congruenza otteniamo che $3*h -= 1 (mod 4)$ che è appunto la congruenza di prima.

Ovvero $x=3*h=4*k+1$ con $k in ZZ$ è soluzione sia del primo che del secondo elemento del sistema, andiamo a sostituire nella terza congruenza ed otteniamo che:

$4*k+1 -= 1 (mod 5)$ ma $5$ non divide $4k+1 -1$

In conclusione la terza congruenza rende il sistema incompatibile.
Ho fatto bene i calcoli?

[gladior-votailprof]

"Neptune":Direi di tagliare la testa al toro, non è che qualcuno mi saprebbe citare una guida che spiega come risolvere i sistemi di congruenze lineari tramite sostituzione?

Perchè un mio collega di università mi ha fatto vedere come sviluppare questa, provo a farne un'altra io e sempre non mi riesce (ovvero trovo una soluzione che è valida per 2 congruenze lineari su tre del sistema). Quindi forse è meglio che mi rileggo bene come si fa, invece di perdere tempo ad andare a tenativi.

http://www.dmi.unict.it/~gquattro/quattrocchigae/Didattica/formazione_discreta_2/teoriadeinumeri.pdf
Prova questa guida è molto completa.Spiega sia il teorema cinese del resto che la sostituzione.
Fammi sapere......................

[Neptune2]

"Gladior":[quote="Neptune"]Direi di tagliare la testa al toro, non è che qualcuno mi saprebbe citare una guida che spiega come risolvere i sistemi di congruenze lineari tramite sostituzione?

Perchè un mio collega di università mi ha fatto vedere come sviluppare questa, provo a farne un'altra io e sempre non mi riesce (ovvero trovo una soluzione che è valida per 2 congruenze lineari su tre del sistema). Quindi forse è meglio che mi rileggo bene come si fa, invece di perdere tempo ad andare a tenativi.

http://www.dmi.unict.it/~gquattro/quattrocchigae/Didattica/formazione_discreta_2/teoriadeinumeri.pdf
Prova questa guida è molto completa.Spiega sia il teorema cinese del resto che la sostituzione.
Fammi sapere......................[/quote]

Niente, non mi ci trovo, l'impostazione è totalmente diversa da quella detta a lezione.

Ho provato anche a fare questo esercizio, te lo riscrivo:

$\{(x -= 1(mod 3)),(x -= 2 (mod 4)),(x -= 4 (mod 5)):}$

Inizio a considerare la prima, ovvero $x -= (mod 3)$ e mi domando, in che forma devono essere scritte le mie $x$ per essere soluzione di questa prima congruenza? Rispondo a questa domanda così:

$3|x-1$

$x-1 = 3 * h $ $h in ZZ$

ovvero $x = 3*h +1$

Ad esempio con $h =1$ ottento $4 -= 1 (mod 3)$ quindi fin qui ci sono.

Adeso sostituisco quello che ho trovato per x nella seconda congruenza ed ho che:

$3*h +1 -= 2 (mod 4)$

$3h -= 1 (mod 4)$

..con un po di calcoli arrivo a dire che $h = 4k+3$ con $k in ZZ$

Difatti se metto $k = 1$ ottento $h=7$ e quindi $x = 22$

Ed infatti:
$22 -= 1 (mod 3)$
$22 -= 2( mod 4)$

Ora però mi perdo proprio nel terzo sistema, ovvero i calcoli che faccio "mi sembrano giusti" ma in realtà la $x$ che trovo soddisfa solo 2 congruenze su 3.

Sostituendo $x= 4k+3$ nell'ultima congruenza ottengo:

$4k+3 -= 4 (mod5)$

$4k -= 1 (mod 5)$

$5|4k-1$ $k = -1$

$k -= -1 (mod 5)$ ovvero $5|k-(-1)$ ovvero $k=4$

$k -= 4 (mod 5)$ $5|k-4$

$k = 5z+4$ $z in ZZ$

Ora però provando a sostituire a cascata a $z$ i valori $1,2$ comunque non mi riesce ovvero la $x= 3h +1$ con $h = 4k+3$ e con $k = 5z+4$ che trovo risulta soddisfare solo la prima e la seconda congruenza sostituento a $z$ appunto $1$, $2$.

Quindi, o devo sostituire a $z$ un'altro valore, ma a questo punto non è molto immediata la cosa, come faccio a trovarla senza andare troppo a tentativi? oppure ho sbaglio proprio quest'ultimo calcolo perchè per i primi due sistemi la soluzione che avevo trovato era abbastanza immediata.