Congruenze
Intanto saluto calorosamente tutti (in quanto sono nuovo), e successivamente passo subito al punto senza tanti fronzoli. Mi trovo a dover dare matematica discreta (l'ho rimandata per un pò di tempo e ora mi trovo a dovermela dare per forza) e mi trovo di fronte ai sistemi di congruenze, che, credevo di saper risolvere, ma a quanto pare sono più ostici del previsto. Due cose in particolare non ho capito (da quel che ho visto nelle correzioni del compito d'esame):
1. Il professore ha "convertito" una congruenza in un modo che non capisco (ho visto che lo fate anche qui cercando per i topic), per fare un esempio:
$18x-=4(mod5)$ -- andrebbe trasformato --> $3x-=7(mod5)$
questo è il passaggio di cui non ho capito la logica ed ho visto che anche in altri topic vengono fatti passaggi simili (qui ad esempio luca.barletta trasforma $3x-=2(mod4)$ in $x-=2 (mod4)$).
E' molto probabile che sia una cosa banale e che io sia quindi un'ignorantone scandaloso, però non riesco proprio ad arrivarci.
Con questo è tutto, spero di essere riuscito a trasmettere il mio dubbio con chiarezza.
Grazie in anticipo!
Saluti (e buon natale!!!).
Giannix
N.B. io di solito risolvevo le congruenze singolarmente calcolando l'identità di bèzout di ognuna e ricavandone la soluzione da lì. Poi mettevo a sistema le soluzioni e trovavo quella "definitiva" (quella singola e l'insieme delle soluzioni generiche per intenderci). Però a quanto mi è stato fatto capire ho sbagliato in pieno...ma dove??
P.S. questo script per scrivere le formule matematiche è qualcosa di spettacolare, di solito io per riportare matematica su di una piattaforma web facevo uno screenshot a Derive e postavo l'immagine
, complimenti all'autore!
1. Il professore ha "convertito" una congruenza in un modo che non capisco (ho visto che lo fate anche qui cercando per i topic), per fare un esempio:
$18x-=4(mod5)$ -- andrebbe trasformato --> $3x-=7(mod5)$
questo è il passaggio di cui non ho capito la logica ed ho visto che anche in altri topic vengono fatti passaggi simili (qui ad esempio luca.barletta trasforma $3x-=2(mod4)$ in $x-=2 (mod4)$).
E' molto probabile che sia una cosa banale e che io sia quindi un'ignorantone scandaloso, però non riesco proprio ad arrivarci.
Con questo è tutto, spero di essere riuscito a trasmettere il mio dubbio con chiarezza.
Grazie in anticipo!
Saluti (e buon natale!!!).
Giannix
N.B. io di solito risolvevo le congruenze singolarmente calcolando l'identità di bèzout di ognuna e ricavandone la soluzione da lì. Poi mettevo a sistema le soluzioni e trovavo quella "definitiva" (quella singola e l'insieme delle soluzioni generiche per intenderci). Però a quanto mi è stato fatto capire ho sbagliato in pieno...ma dove??
P.S. questo script per scrivere le formule matematiche è qualcosa di spettacolare, di solito io per riportare matematica su di una piattaforma web facevo uno screenshot a Derive e postavo l'immagine

Risposte
riguardo il primo esempio: stai "guardando" i numeri modulo 5 quindi quello che conta è il resto della divisione intera per 5 nel caso di diciotto è 3. l'altra trasformazione è sbagliata il 4 può diventare un 7, per capire x=3 è soluzione della prima congruenza ma non della seconda, quindi non sono equivalenti e c'è un errore nella trasformazione. In genere comunque se consideri una congruenza modulo n si riducono solo gli interi più grandi di n per rendere più semplici i conti.
riguardo il secondo esempio: qui la trasformazione è di tipo diverso, i numeri sono già ridotti 3 e 2 sono più piccoli di 4, quello che si può fare è notare che $MCD(3,4)=1$ quindi (per l'identità di bezout) esistono a,b tali che $3a+4b=1$ che vista modulo 4 ti dice $3*a-=1(mod4)$ se trovi questo "a" puoi moltiplicare a destra e sinistra della congruenza ed ottenere un coefficiente 1 davanti alla x. Nel caso considerato a=3 quindi ottengo $9x-=6(mod4)$ ora riducendo (come nell'esempio precendente) ottieni $x-=2(mod4)$.
riguardo il secondo esempio: qui la trasformazione è di tipo diverso, i numeri sono già ridotti 3 e 2 sono più piccoli di 4, quello che si può fare è notare che $MCD(3,4)=1$ quindi (per l'identità di bezout) esistono a,b tali che $3a+4b=1$ che vista modulo 4 ti dice $3*a-=1(mod4)$ se trovi questo "a" puoi moltiplicare a destra e sinistra della congruenza ed ottenere un coefficiente 1 davanti alla x. Nel caso considerato a=3 quindi ottengo $9x-=6(mod4)$ ora riducendo (come nell'esempio precendente) ottieni $x-=2(mod4)$.
grazie per la risposta probabilmente ho ricopiato male dalla bella copia. Ma per il secondo esempio non ho capito una cosa: se consideriamo a=3 la congruenza dovrebbe venire $(3*3)x-=1*3(mod4)$ e cioè $9x-=3(mod4)$ quel 6 da dove l'hai preso?
"GianniX":
$3x-=2(mod4)$
moltiplico a destra e sinistra per tre ottengo $9x-=6$. La "a" è il numero per cui moltiplichiamo la congruenza iniziale, la congruenza $3a-=1(mod4)$ era per farti capire a che serve e come trovare "a"

quindi il numero 'a' è sempre il coefficente della x (in questo caso 3)?
altra domanda: quando riduco, in pratica, devo sostituire il numero al resto che ottengo dividendolo per il modulo? giusto per avere le idee chiare...
altra domanda: quando riduco, in pratica, devo sostituire il numero al resto che ottengo dividendolo per il modulo? giusto per avere le idee chiare...
a NON è il coefficiente della x in genere, casualmente in questo caso sono uguali, ti faccio un altro esempio per chiarire:
prima un osservazione se tu avessi un'equazione del tipo $k*x=m$ ($k!=0$) e volessi risolverla moltiplicheresti per $1/k$ a destra e sinistra ottenendo $x=m/k$, fai comparire un coefficiente 1 davanti alla x. L'idea è che vogliamo fare la stessa cosa "modulo n". Procediamo
:
$4x-=2(mod7)$ voglio un 1 davanti alla x, noto che come prima 5 e 7 sono coprimi quindi esistono a,b tali che $4a+7b-=1$ di nuovo visto modulo 7 ottieni $4a=1$ ("a" quindi è l'inverso di 4 modulo 7). In questo caso a=2 infatti $4*2-=8-=1(mod7)$ quindi la mia congruenza diventa $2*4x-=2*2(mod7)$ ovvero $x-=4(mod7)$
quando riduci sostituisci al numero il resto che ottieni dividendo per il modulo. se hai ancora qualche dubbio, non farti problemi
prima un osservazione se tu avessi un'equazione del tipo $k*x=m$ ($k!=0$) e volessi risolverla moltiplicheresti per $1/k$ a destra e sinistra ottenendo $x=m/k$, fai comparire un coefficiente 1 davanti alla x. L'idea è che vogliamo fare la stessa cosa "modulo n". Procediamo

$4x-=2(mod7)$ voglio un 1 davanti alla x, noto che come prima 5 e 7 sono coprimi quindi esistono a,b tali che $4a+7b-=1$ di nuovo visto modulo 7 ottieni $4a=1$ ("a" quindi è l'inverso di 4 modulo 7). In questo caso a=2 infatti $4*2-=8-=1(mod7)$ quindi la mia congruenza diventa $2*4x-=2*2(mod7)$ ovvero $x-=4(mod7)$
quando riduci sostituisci al numero il resto che ottieni dividendo per il modulo. se hai ancora qualche dubbio, non farti problemi

4 e 7 sono coprimi, quindi esistono a,b tali che $4a+7b-=1$. Visto modulo ottengo $4a-=1(mod7)$ e fin quì ci sono. Poi dici che 'a' è l'inverso di 4 modulo 7 e qui mi "freghi" perchè non capisco su che basi (io per inversi intendo elementi che moltiplicati tra di loro danno come risultato l'elemento neutro) oltre a non capire ancora (scusa ma sono di coccio
) da dove ottieni 2...anzi non del tutto capito, per cui ti pongo questa mia (spero) ultima domanda: il due lo ottieni tramite l'identità di bezout tra 4 e 7?
grazie ancora per la pazienza!
io l'identità (tanto per dirli tutti i procedimenti) la ricavo tramite divisioni successive (7:4 e 4:3 con 3 che è il resto di 7:4) ottenendo $1=4(2)+7(-1)$ dove, tenendo in considerazione la congruenza $4a+7b-=1$, considero il (2) come a ed il (-1) come b. Dimmi se sbaglio...

grazie ancora per la pazienza!
io l'identità (tanto per dirli tutti i procedimenti) la ricavo tramite divisioni successive (7:4 e 4:3 con 3 che è il resto di 7:4) ottenendo $1=4(2)+7(-1)$ dove, tenendo in considerazione la congruenza $4a+7b-=1$, considero il (2) come a ed il (-1) come b. Dimmi se sbaglio...
$2*4-=1(mod7)$ e 1 è elemento neutro moltiplicativo, comunque l'ho detto perché pensavo di chiarirti le idee non è indispensabile pensarlo così, basta capire che vuoi un 1 davanti alla x ed il modo per ottenerlo è moltiplicare per un opportuna costante (non è sempre possibile), la costante la ottieni come hai giustamente detto dall'identità di bezout, io le trovo ad occhio per questo non ho scritto esplicitamente l'identità (anche perché in effetti il b non serve). Spero sia tutto chiaro, altrimenti chiedi pure

ok quindi ricapitoliamo con l'esempio di prima per vedere se ho capito bene:
$18x-=4(mod5)$ abbiamo $MCD(18,5)=1$ per cui $18a+5b=1$, visto modulo viene $18a-=1(mod5)$ dove 'a' la ottengo tramite l'identità di bèzout tra 18 e 5 (cioè $1=18(2)+5(-7)$). In questo caso a=2, quindi $2*18x-=2*4(mod5)rarr36x-=8(mod5)rarr9x-=2(mod5)rarrx-=2(mod5)$
MODIFICATO!
$18x-=4(mod5)$ abbiamo $MCD(18,5)=1$ per cui $18a+5b=1$, visto modulo viene $18a-=1(mod5)$ dove 'a' la ottengo tramite l'identità di bèzout tra 18 e 5 (cioè $1=18(2)+5(-7)$). In questo caso a=2, quindi $2*18x-=2*4(mod5)rarr36x-=8(mod5)rarr9x-=2(mod5)rarrx-=2(mod5)$
MODIFICATO!
"GianniX":
ok quindi ricapitoliamo con l'esempio di prima per vedere se ho capito bene:
$18x-=4(mod5)$ abbiamo $MCD(18,5)=1$ per cui $18a+5b=1$, visto modulo viene $18-=1(mod5)$ dove 'a' la ottengo tramite l'identità di bèzout tra 18 e 5 (cioè $1=18(2)+5(-7)$). In questo caso a=2, quindi $2*18x-=2*4(mod7)rarr36x-=8(mod7)rarr9x-=2(mod7)rarr2x-=2(mod7)$
ed a questo punto però rimane 2x (a meno che non abbia sbagliato qualcosa) e dopo come proseguo? continuo a dividere per il modulo (7:2])? se continuo a dividere viene $x-=2(mod7)$ e verrebbe differente dal 3 ottenuto nei primi post...
Grazie ancora (sto abusando della tua pazienza)!!!
allora innanzitutto come ho detto da subito conviene ridurre per fare conti più semplici il 18 potevi metterlo subito 3 e risolvere l'identità. A parte questo hai cambiato il mod5 con un mod7 ad un certo punto quindi non ti tornano i conti. poi hai cercato un valore a tale che $18*a-=1(mod5)$ perché dividere per 4 poi? riguarda il tutto con calma e non cambiare i moduli strada facendo.
per il modulo si scusa è stato un'errore di distrazione. Mi interessava che il procedimento fosse giusto
. In questo modo se ho un sistema di congruenze me le "semplifico" in questo modo e poi posso risolvere "eguagliandole" facendo un procedimento di questo tipo:
${(x-=a+nk),(x-=b+nh):}rarra +nk=b+nh$ etc...

${(x-=a+nk),(x-=b+nh):}rarra +nk=b+nh$ etc...
se entrambe le congruenze sono modulo n la procedura dovrebbe essere quelle, se le congruenze hanno moduli diversi credo dovresti usare il teorema cinese del resto.
capito, grazie di tutto ora l'ultima domanda: ho provato a semplificare $9x-=6(mod12)$ (da questo post) con il metodo fatto finora, operando nel seguente modo:
1. dato che $MCD(9,12)=3 rarr 3x-=2(mod4);
2. ora il $MCD(3,4)=1$ per cui esistono $a,b$ tali che $3a+4b=1 rarr 3a-=1(mod4)$ dove, dato che $1=4(1)+3(-1) rarr a=-1 rarr -3x-=1(mod4) rarr x-=1(mod4)$
arrivato a questo punto però la soluzione del post è discordante dalla mia (in quanto lì risulta $x-=2(mod4)$), come mai? ho sbagliato io (se si dove)?
Grazie ancora in anticipo!!!
1. dato che $MCD(9,12)=3 rarr 3x-=2(mod4);
2. ora il $MCD(3,4)=1$ per cui esistono $a,b$ tali che $3a+4b=1 rarr 3a-=1(mod4)$ dove, dato che $1=4(1)+3(-1) rarr a=-1 rarr -3x-=1(mod4) rarr x-=1(mod4)$
arrivato a questo punto però la soluzione del post è discordante dalla mia (in quanto lì risulta $x-=2(mod4)$), come mai? ho sbagliato io (se si dove)?
Grazie ancora in anticipo!!!
"GianniX":
capito, grazie di tutto ora l'ultima domanda: ho provato a semplificare $9x-=6(mod12)$ (da questo post) con il metodo fatto finora, operando nel seguente modo:
1. dato che $MCD(9,12)=3 rarr 3x-=2(mod4);
2. ora il $MCD(3,4)=1$ per cui esistono $a,b$ tali che $3a+4b=1 rarr 3a-=1(mod4)$ dove, dato che $1=4(1)+3(-1) rarr a=-1 rarr -3x-=1(mod4) rarr x-=1(mod4)$
arrivato a questo punto però la soluzione del post è discordante dalla mia (in quanto lì risulta $x-=2(mod4)$), come mai? ho sbagliato io (se si dove)?
Grazie ancora in anticipo!!!
da $3x-=2(mod4)$ moltiplichi per -1 (che hai trovato con l'identità di bezout) ed ottieni $-3x-=-2(mod4)$ che equivale a $x-=2(mod4)$ hai sbagliato da qualche parte
quel $3x-=1(mod4)$ non si capisce bene dove l'hai tirato fuori e probabilmente l'errore è là
ah ho capito l'errore, ho considerato invece della congruenza normale, l'equazione in $a,b$ (cioè $3a+4b=1$). Sono un'idiota di dimensioni bibliche...
Grazie di tutto, sei stato gentilissimo, a buon rendere!!! ^^
Giannix.
Grazie di tutto, sei stato gentilissimo, a buon rendere!!! ^^
Giannix.
"GianniX":
ah ho capito l'errore, ho considerato invece della congruenza normale, l'equazione in $a,b$ (cioè $3a+4b=1$). Sono un'idiota di dimensioni bibliche...
Grazie di tutto, sei stato gentilissimo, a buon rendere!!! ^^
Giannix.
Ti toccherà offrirmi una birra

ciao