Congruenze lineari
Sapreste dirmi come si normalizza un sistema di congruenze lineari ...in modo tale che a sinistra ci siano solo le x?
Risposte
Ciao 
Un sistema di congruenze lineari si normalizza se sai come normalizzare una congruenza lineare.
Prendiamo una congruenza lineare del tipo $ax \equiv b \mod n$, supposto che $gcd(a, n) | b$(condizione necessaria e sufficiente affinché la congruenza abbia soluzione), si procede in tre passi:
1)si divide tutto per $gcd(a, n) = d$ quindi ottengo $a_1 = \frac{a}{d}$, $b_1 = \frac{b}{d}$ e $n_1 = \frac{n}{d}$ e la congruenza iniziale diventa: $ax \equiv b \mod n \iff a_1x \equiv b_1 \mod n_1$;
2)Nota che $gcd(a_1, n_1) = 1$ quindi $a_1$ ammette inverso modulo $n_1$: si cerca l'inverso applicando il lemma di bezout su $a_1$ e $n_1$;
3)Si moltiplicano ambo i membri della congruenza per l'inverso di $a_1$, quindi, identificando l'inverso con $a_1^{-1}$, ho che:
$a_1x \equiv b_1 \mod n_1 \iff a_1^{-1} \cdot a_1\cdot x \equiv a_1^{-1} \cdot b \mod n_1 \iff x \equiv a_1^{-1}b \mod n_1$
Ecco un esempio: prendiamo $12x \equiv 9 \mod 15$ e riduciamola.
1)$gcd(12, 15) = 3 | 9$ quindi la congruenza ha soluzione, divido tutto per $3$ e ho: $12x \equiv 9 \mod 15 \iff 4x \equiv 3 \mod 5$
2)$gcd(4, 5) = 1$ quindi $4$ ha inverso modulo $5$, applicando bezout si trova che l'inverso di $4$ è $4$(si nota anche ad occhio che $4^2 \equiv 1 \mod 5$).
3)Moltiplico ambo i membri per $4$:
$4x \equiv 3 \mod 5 \iff 16x \equiv 12 \mod 5 \iff x \equiv 12 \mod 5 \iff x \equiv 2 \mod 5$.
$12x \equiv 9 \mod 15 \iff x \equiv 2 \mod 5$
Finito.
Per normalizzare un sistema normalizzi tutte le sue equazioni.
Ciao
Edit: ho appena letto qualche tuo topic e deduco che questa sia la tua prima volta in un forum(o in un forum di questo genere), qualche consiglio: leggi il regolamento, poi questo topic e non rispondere mai male a nessuno. Benvenuto e buona permanenza!
Un sistema di congruenze lineari si normalizza se sai come normalizzare una congruenza lineare.
Prendiamo una congruenza lineare del tipo $ax \equiv b \mod n$, supposto che $gcd(a, n) | b$(condizione necessaria e sufficiente affinché la congruenza abbia soluzione), si procede in tre passi:
1)si divide tutto per $gcd(a, n) = d$ quindi ottengo $a_1 = \frac{a}{d}$, $b_1 = \frac{b}{d}$ e $n_1 = \frac{n}{d}$ e la congruenza iniziale diventa: $ax \equiv b \mod n \iff a_1x \equiv b_1 \mod n_1$;
2)Nota che $gcd(a_1, n_1) = 1$ quindi $a_1$ ammette inverso modulo $n_1$: si cerca l'inverso applicando il lemma di bezout su $a_1$ e $n_1$;
3)Si moltiplicano ambo i membri della congruenza per l'inverso di $a_1$, quindi, identificando l'inverso con $a_1^{-1}$, ho che:
$a_1x \equiv b_1 \mod n_1 \iff a_1^{-1} \cdot a_1\cdot x \equiv a_1^{-1} \cdot b \mod n_1 \iff x \equiv a_1^{-1}b \mod n_1$
Ecco un esempio: prendiamo $12x \equiv 9 \mod 15$ e riduciamola.
1)$gcd(12, 15) = 3 | 9$ quindi la congruenza ha soluzione, divido tutto per $3$ e ho: $12x \equiv 9 \mod 15 \iff 4x \equiv 3 \mod 5$
2)$gcd(4, 5) = 1$ quindi $4$ ha inverso modulo $5$, applicando bezout si trova che l'inverso di $4$ è $4$(si nota anche ad occhio che $4^2 \equiv 1 \mod 5$).
3)Moltiplico ambo i membri per $4$:
$4x \equiv 3 \mod 5 \iff 16x \equiv 12 \mod 5 \iff x \equiv 12 \mod 5 \iff x \equiv 2 \mod 5$.
$12x \equiv 9 \mod 15 \iff x \equiv 2 \mod 5$
Finito.
Per normalizzare un sistema normalizzi tutte le sue equazioni.
Ciao
Edit: ho appena letto qualche tuo topic e deduco che questa sia la tua prima volta in un forum(o in un forum di questo genere), qualche consiglio: leggi il regolamento, poi questo topic e non rispondere mai male a nessuno. Benvenuto e buona permanenza!
grazie mille comunque sapresti dirmi cosa sarebbe gcd??
sapresti normalizzarmi questo sistema di congruenze lineari
23x congruo 138 mod 115
15x congruo 37 mod 4
10x congruo 6 mod 7
E se sapessi pure risolverlo ti sarei veramente grato in modo tale da poter capire il meccanismo.
Comunque grazie per i tuoi consigli. Fra qualche giorno avro l' esame di matematica discreta e sono agitatissimo 
.
Quindi vorrei tenermi pronto ecco perche sono un po impulsivo
comunque sapresti dirmi cosa sarebbe gcd??sapresti normalizzarmi questo sistema di congruenze lineari
23x congruo 138 mod 115
15x congruo 37 mod 4
10x congruo 6 mod 7
E se sapessi pure risolverlo ti sarei veramente grato in modo tale da poter capire il meccanismo
.Comunque grazie per i tuoi consigli
. Fra qualche giorno avro l' esame di matematica discreta e sono agitatissimo .Quindi vorrei tenermi pronto
ecco perche sono un po impulsivo
"gcd" è l'abbreviazione inglese di "massimo comun divisore"(greatest common divisor).
Ti normalizzo due di quelle equazioni, l'altra la fai tu così vediamo se hai capito.
$23x \equiv 138 \mod 115$, nota che $138 = 115 + 23$(facendo la divisione euclidea) quindi $138 \equiv 23 \mod 15$ e $23x \equiv 138 \mod 115 \iff 23x \equiv 23 \mod 115$, applicando l'algoritmo di Euclide si ha che $gcd(23, 115) = 23$ quindi l'equazione ha soluzione. Dividendo tutto per il massimo comun divisore ottengo $x \equiv 1 \mod 5$
Passiamo alla seconda: $15x \equiv 37 mod 4$, nota che $37 = 4 \cdot 9 + 1$ quindi $37 \equiv 1 \mod 4$ e $15x \equiv 37 mod 4 \iff 15x \equiv 1 \mod 4$, il massimo comun divisore di $15$ e $4$ è $1$ che divide il membro destro dell'equazione e quindi la congruenza ha soluzione. Osserva che $15 \equiv -1 \mod 4$ e quindi la congruenza diventa $15x \equiv 1 \mod 4 \iff -x \equiv 1 \mod 4$, molitplicando per $-1$ ambo i membri ho: $x \equiv -1 \mod 4 \iff x \equiv 3 \mod 4$.
Prova a ridurre tu $10x \equiv 6 \mod 7$.
Dopo vediamo come si risolve il sistema.
Ps: leggi questo topic per capire come scrivere le formule sul forum.
Ciao
Ti normalizzo due di quelle equazioni, l'altra la fai tu così vediamo se hai capito.
$23x \equiv 138 \mod 115$, nota che $138 = 115 + 23$(facendo la divisione euclidea) quindi $138 \equiv 23 \mod 15$ e $23x \equiv 138 \mod 115 \iff 23x \equiv 23 \mod 115$, applicando l'algoritmo di Euclide si ha che $gcd(23, 115) = 23$ quindi l'equazione ha soluzione. Dividendo tutto per il massimo comun divisore ottengo $x \equiv 1 \mod 5$
Passiamo alla seconda: $15x \equiv 37 mod 4$, nota che $37 = 4 \cdot 9 + 1$ quindi $37 \equiv 1 \mod 4$ e $15x \equiv 37 mod 4 \iff 15x \equiv 1 \mod 4$, il massimo comun divisore di $15$ e $4$ è $1$ che divide il membro destro dell'equazione e quindi la congruenza ha soluzione. Osserva che $15 \equiv -1 \mod 4$ e quindi la congruenza diventa $15x \equiv 1 \mod 4 \iff -x \equiv 1 \mod 4$, molitplicando per $-1$ ambo i membri ho: $x \equiv -1 \mod 4 \iff x \equiv 3 \mod 4$.
Prova a ridurre tu $10x \equiv 6 \mod 7$.
Dopo vediamo come si risolve il sistema.
Ps: leggi questo topic per capire come scrivere le formule sul forum.
Ciao
non ho capito la seconda equazione i vari passaggi che hai svolto se potresti soffermarti di piu su ogni passaggio spiegando cosa hai fatto riuscirei a capirlo GRAZIE
se potresti soffermarti di piu su ogni passaggio spiegando cosa hai fatto riuscirei a capirlo GRAZIE
"thewinner69":
non ho capito la seconda equazione i vari passaggi che hai svolto
Ok, allora:
$15x \equiv 37 \mod 4$, nota che $37 \equiv 1 mod 4$ perché facendo la divisione euclidea tra 37 e 4 si ottiene $37 = 4*9 + 1$, leggendo l'uguaglianza modulo 4 ho $37 \equiv 4*9 + 1 \equiv 9*0 + 1 \equiv 1 \mod 4$ dove al secondo passaggio ho sostituito $4$ con $0$ perché, ovviamente, $4 \equiv 0 \mod 4$. Un altro modo di vederla è così: $37 = 4*9 + 1$ quindi $37-1 = 4*9$ e per definizione di congruenza ho che $37 \equiv 1 \mod 4$. Un altro ancora: 37 e 1 danno lo stesso resto divisi per 4, quindi $37 \equiv 1 \mod 4$.
Quindi l'equazione iniziale diventa $15x \equiv 1 \mod 4$. Ora nota che $15 = 16-1 = 4^2 - 1$ se passiamo al modulo 4 otteniamo $15 \equiv 4^2 - 1 \equiv -1 \mod 4$.
Quindi l'equazione diventa $-x \equiv 1 \mod 4$, moltiplicando per $-1$ si arriva a $x \equiv -1 \mod 4$ ma $-1 \equiv 3 \mod 4$ perché $3 = 4 -1$.
Spero di essermi spiegato.
Fammi sapere
ma non hai utilizzato l'inverso aritmetico?
"thewinner69":
ma non hai utilizzato l'inverso aritmetico?
Quelle osservazioni servivano per semplificare i calcoli, il procedimento è corretto ma evita di utilizzare bezout per trovare l'inverso numerico.
Comunque possiamo sempre ripartire da $15x \equiv 1 \mod 4$ e trovare l'inverso di $15$ modulo $4$: sappiamo che $gcd(15, 4) = 1$ per il lemma di bezout esistono $m, n \in \mathbb{Z}$ tali che $15m + 4n = 1$, come troviamo $m, n$?
Prima di tutto applichiamo l'algoritmo di euclide per trovare il massimo comun divisore di $4$ e $15$:
1)$15 = 4*3 + 3$
2)$4 = 3 + 1$
Adesso riscriviamo i resti:
1)$3 = 15 - 4*3$
2)$1 = 4 - 3$
e risaliamo dal basso verso l'alto: sappiamo che $1 = 4-3$ ma $3 = 15-4*3$, sostituendo ottengo: $1 = 4-3 = 4-(15-4*3) = 4*4 - 15$, quindi $15*(-1) + 4*(4) = 1$ $m,n$ sono $m = -1, n = 4$ passando al modulo otteniamo che $15*(-1) \equiv 1 \mod 4$, quindi l'inverso di $15$ è $-1$, quindi basta moltiplicare per $-1$ ambo i membri ed ottenere: $15x \equiv 1 \mod 4 \iff (-1)\cdot 15x \equiv -1 \cdot 1 \mod 4 \iff (-15) \cdot x \equiv -1 \mod 4 \iff x \equiv -1 \mod 4 \iff x \equiv 3 \mod 4$.
anche se non sto riuscendo a capire..... nonostante la tua spiegazione dettagliata ti ringrazio lo stesso
nonostante la tua spiegazione dettagliata ti ringrazio lo stesso
"thewinner69":
anche se non sto riuscendo a capire.....
Precisamente cosa non capisci?
Tu come calcoli l'inverso? Conosci tutte le definizioni e i teoremi che ho applicato?
Ciao
No i miei amici mi hanno detto ke per semplicita dovremmo trovare una x ke moltiplicata per a e successivamente sottraendo al prodotto la b si ottenga un divisore di n ad esempio.
15x≡37mod4 4|15x - 37 x = 3
15x≡37mod4 4|15x - 37 x = 3
"thewinner69":
No i miei amici mi hanno detto ke per semplicita dovremmo trovare una x ke moltiplicata per a e successivamente sottraendo al prodotto la b si ottenga un divisore di n ad esempio.
15x≡37mod4 4|15x - 37 x = 3
Beh questo equivale a risolvere la congruenza per tentativi
Non sempre si riesce a vedere la soluzione ad occhio.
Ciò che ho scritto nelle pagine precedenti è il metodo standard per risolvere le congruenze lineari senza andare per tentativi(ovvio che se la soluzione la vedi subito eviti di fare tutti i calcoli
).
grazie mille cmq davvero se tutte le persone fossero come te sarebbe un mondo migliore
Sapresti dirmi quando un grafo ammette una rappresentazione planare e come si fa a verificare la formula di Eulero.
Grazie
davvero se tutte le persone fossero come te sarebbe un mondo migliore Sapresti dirmi quando un grafo ammette una rappresentazione planare e come si fa a verificare la formula di Eulero.
Grazie
"thewinner69":
grazie mille cmq
Sapresti dirmi quando un grafo ammette una rappresentazione planare e come si fa a verificare la formula di Eulero.
Grazie
Purtroppo non conosco nulla di teoria di grafi, non posso aiutarti. :/
Ciao
su cosa potresti aiutarmi riguardo matematica discreta ..ho visto che sei molto bravo ...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo