Congruenze lineari, elementi invertibili e altre cose...
Buonasera a tutti.
L'ennesimo dubbio di Aritmetica modulare.
Scusate ma esiste un modo semplice e "rapido" per risolvere le congruenze lineari?
Sia data: $ax \equiv b mod n$ con $GCD(a,n)|b$. Come procedo? Ho trovato tante spiegazioni al riguardo, ma nessuna mi convince molto. Soprattutto una mi dice che da $ax \equiv b mod n$ (con la condizione scritta sopra) posso passare a $x \equiv b/a mod n$. Che cosa vuol dire $b/a mod n$? Come si effettua la divisione modulare? Se non sbaglio tale operazione non è ben definita (perchè dipende dalla classe scelta).
Non è che mi potete fare un esempio, per cortesia, visto che non ce n'è nessuno sulle mie dispense?
Personalmente poi penso che tale questione sia strettamente connessa con questa. Che cosa sono i cosiddetti elementi invertibili? Cito testualmente dalle mie dispense:
DEFINIZIONE. Un elemento $a in ZZ_(n)^(*)$ si dice invertibile se esiste un elemento $b in ZZ_(n)^(*)$ tale che $ab = 1$.
In questo caso $b$ si chiama inverso di $a$ e si denota con $a^(-1)$. L’insieme degli elementi invertibili di $ZZ_(n)^(*)$ si denota con $U(n)$.
Qualcuno mi può illuminare per favore?
Come sempre confido nella vostra gentilezza. Grazie mille in anticipo,
Paolo.
L'ennesimo dubbio di Aritmetica modulare.
Scusate ma esiste un modo semplice e "rapido" per risolvere le congruenze lineari?
Sia data: $ax \equiv b mod n$ con $GCD(a,n)|b$. Come procedo? Ho trovato tante spiegazioni al riguardo, ma nessuna mi convince molto. Soprattutto una mi dice che da $ax \equiv b mod n$ (con la condizione scritta sopra) posso passare a $x \equiv b/a mod n$. Che cosa vuol dire $b/a mod n$? Come si effettua la divisione modulare? Se non sbaglio tale operazione non è ben definita (perchè dipende dalla classe scelta).
Non è che mi potete fare un esempio, per cortesia, visto che non ce n'è nessuno sulle mie dispense?
Personalmente poi penso che tale questione sia strettamente connessa con questa. Che cosa sono i cosiddetti elementi invertibili? Cito testualmente dalle mie dispense:
DEFINIZIONE. Un elemento $a in ZZ_(n)^(*)$ si dice invertibile se esiste un elemento $b in ZZ_(n)^(*)$ tale che $ab = 1$.
In questo caso $b$ si chiama inverso di $a$ e si denota con $a^(-1)$. L’insieme degli elementi invertibili di $ZZ_(n)^(*)$ si denota con $U(n)$.
Qualcuno mi può illuminare per favore?
Come sempre confido nella vostra gentilezza. Grazie mille in anticipo,
Paolo.
Risposte
Con $b/a modn$ si intende $ba^(-1) modn$, dove $a^(-1)$ è quell'elemento tale che $a^(-1)a-=1 modn$.
Ad es.: $2^(-1) mod5 -=3$, infatti $2*3-=1mod5$.
Attenzione che non tutti gli elementi di una classe di resto ammettono l'elemento inverso, ad es. 2 non ha inverso in $ZZ_4$.
Ad es.: $2^(-1) mod5 -=3$, infatti $2*3-=1mod5$.
Attenzione che non tutti gli elementi di una classe di resto ammettono l'elemento inverso, ad es. 2 non ha inverso in $ZZ_4$.
"luca.barletta":
Attenzione che non tutti gli elementi di una classe di resto ammettono l'elemento inverso, ad es. 2 non ha inverso in $ZZ_4$.
Giusto, perchè se ho capito bene, $a$ ammette elemento inverso in $ZZ_n$ se e solo se $a$ è coprimo con $n$ ($(a,n)=1$). Dunque, esiste l'inverso di $3$ in $ZZ_5$, ma non in $ZZ_6$.
Adesso,
"luca.barletta":
Con $b/a modn$ si intende $ba^(-1) modn$, dove $a^(-1)$ è quell'elemento tale che $a^(-1)a-=1 modn$.
Ad es.: $2^(-1) mod5 -=3$, infatti $2*3-=1mod5$.
Scusa se abuso della tua pazienza ma esiste un modo per trovare questo inverso? Cioè, io devo trovare $2^(-1)mod5$. Quindi devo ceracre quel numero tale $b$ tale che $b[2]_5=[1]_5$ da cui $b=3$. E' corretto? E' questo il modo per ricavarsi l'inverso?
Grazie e scusa ancora il disturbo.
Paolo
Se i numeri sono pochi puoi andare a tentativi, oppure puoi usare l'algoritmo esteso di Euclide: trovare $b-=a^(-1)modn$ significa trovare $b$ e $t$ tale che $ba+tn=1$; con l'algoritmo di Euclide esteso trovi $b$ e $t$, e $b$ è l'inverso moltiplicativo di $a$ sse $gcd(a,n)=1$.
Ti ringrazio per le tue delucidazioni. Puoi ancora dirmi se il seguente svolgimento è corretto? Grazie.
$50x \equiv 12mod14$
E' $(50,14)=2$, dunque posso dividere e ottengo:
$25x \equiv 6mod7$
Ora, sarà $x \equiv 6*25^(-1)mod7$. Ciò significa che devo trovarmi l'inverso modulo $7$ di $25$ (e so che esiste, visto che sono coprimi).
Quindi, detto $b \equiv 25^(-1)mod7$ ho che
$25b+7t=1$ da cui $b=2$ e $t=-7$.
$b \equiv 2mod7$.
Poichè è $x \equiv 6*25^(-1)mod7$ allora
$x \equiv 6*2 mod7 \equiv 5mod7$.
Cosa dici?
Grazie in anticipo. Paolo
$50x \equiv 12mod14$
E' $(50,14)=2$, dunque posso dividere e ottengo:
$25x \equiv 6mod7$
Ora, sarà $x \equiv 6*25^(-1)mod7$. Ciò significa che devo trovarmi l'inverso modulo $7$ di $25$ (e so che esiste, visto che sono coprimi).
Quindi, detto $b \equiv 25^(-1)mod7$ ho che
$25b+7t=1$ da cui $b=2$ e $t=-7$.
$b \equiv 2mod7$.
Poichè è $x \equiv 6*25^(-1)mod7$ allora
$x \equiv 6*2 mod7 \equiv 5mod7$.
Cosa dici?
Grazie in anticipo. Paolo
Direi che va bene, anche perchè potevi procedere in quest'altro modo
$50x$ sarebbe, modulo $14$, $8x$
Perciò
$8x\equiv12 (mod14)$
$4x\equiv 6 (mod7)$
$2x\equiv 3\equiv10 (mod7)$
$x\equiv5(mod7)$
$50x$ sarebbe, modulo $14$, $8x$
Perciò
$8x\equiv12 (mod14)$
$4x\equiv 6 (mod7)$
$2x\equiv 3\equiv10 (mod7)$
$x\equiv5(mod7)$
ok, adesso dovresti trovare le soluzioni dell'equazione originale, cioè le soluzioni in $ZZ_(14)$. Le soluzioni totali sono $d=2$, perché abbiamo diviso per questo numero $d=gcd(a,n)$ all'inizio: una soluzione è quella già trovata, cioè $5$, l'altra si ottiene come $5+n/d=5+7=12$.
"luca.barletta":
ok, adesso dovresti trovare le soluzioni dell'equazione originale, cioè le soluzioni in $ZZ_(14)$. Le soluzioni totali sono $d=2$, perché abbiamo diviso per questo numero $d=gcd(a,n)$ all'inizio: una soluzione è quella già trovata, cioè $5$, l'altra si ottiene come $5+n/d=5+7=12$.
Già, è vero perchè le soluzioni incongrue modulo $n$ sono sempre in numero $d = (a,n)$. Più in generale, nell'equazione sopra, posso dire che le soluzioni sono $x=5+14h$ e $x=12+14h$, con $h,k in ZZ$.
Piuttosto, una domanda su un pezzo della risoluzione postata dal caro amico Steven: quando dici
$4x \equiv 6mod7 => 2x \equiv 3mod7=> 2x \equiv 10 mod7$ sfrutti il fatto che $3$ e $10$ sono nella stessa classe modulo $7$, vero?
Vi ringrazio per ora per i vostri chiarimenti... anche se ho la tentazione di chiedervi un'altra cosa: se avessi da risolvere una congruenza del tipo $f(x) \equiv a mod n$ con, ad esempio, $f(x)$ trinomio di secondo grado? Non so se la mia domanda è chiara... Grazie ancora per la disponibilità.
Paolo
"Paolo90":
Piuttosto, una domanda su un pezzo della risoluzione postata dal caro amico Steven: quando dici
$4x \equiv 6mod7 => 2x \equiv 3mod7=> 2x \equiv 10 mod7$ sfrutti il fatto che $3$ e $10$ sono nella stessa classe modulo $7$, vero?
Esattamente, stessa classe di resto.
Per l'altra domanda non so se esiste un modo più facile, ma forse potrebbe essere d'aiuto sapere che
$4a(ax^2+bx+c)=(2ax+b)^2+4ac-b^2$
(identità da cui deriva la nota formula per le equazioni di secondo grado).
Ciao
"Steven":
[quote="Paolo90"]
Piuttosto, una domanda su un pezzo della risoluzione postata dal caro amico Steven: quando dici
$4x \equiv 6mod7 => 2x \equiv 3mod7=> 2x \equiv 10 mod7$ sfrutti il fatto che $3$ e $10$ sono nella stessa classe modulo $7$, vero?
Esattamente, stessa classe di resto.
[/quote]
Grazie per il chiarimento.
"Steven":
Per l'altra domanda non so se esiste un modo più facile, ma forse potrebbe essere d'aiuto sapere che
$4a(ax^2+bx+c)=(2ax+b)^2+4ac-b^2$
(identità da cui deriva la nota formula per le equazioni di secondo grado).
Ciao
Sì, conosco quella formula perchè l'avevo studiata proprio con le equazioni di II grado. Vediamo un po' se riesco a fare qualche ragionamento.
Partiamo da
$ax^2+bx+c \equiv m mod n$ che posso riscrivere come
$4a(ax^2+bx+c) \equiv 4am mod n$
da cui, sfruttando la tua identità
$(2ax+b)^2+4ac-b^2 \equiv 4am mod n$
$(2ax+b)^2 \equiv (4am - 4ac + b^2) mod n$
cioè
$(2ax+b)^2 \equiv (4am + \Delta) mod n$
Ora però il problema è quello di estrarre radici quadrate modulari: come fare? Scusate il disturbo e abbiate pazienza se sono un po' duro a capire...
Grazie,
Paolo
"Paolo90":
Ora però il problema è quello di estrarre radici quadrate modulari: come fare? Scusate il disturbo e abbiate pazienza se sono un po' duro a capire...
Puoi consultare qui: http://www.matematicamente.it/forum/1-vt21458.html?&start=0
Ti ringrazio molto per il link... Gli ho dato uno sguardo e non ho capito molto perchè non so che cos'è il Criterio di Eulero... Adesso provo a cercare qualcosa su quello, poi ti faccio sapere.
Grazie ancora,
Paolo.
Grazie ancora,
Paolo.
"Paolo90":
Ti ringrazio molto per il link... Gli ho dato uno sguardo e non ho capito molto perchè non so che cos'è il Criterio di Eulero... Adesso provo a cercare qualcosa su quello, poi ti faccio sapere.
Grazie ancora,
Paolo.
Tranquillo, quello che mi ha spiegato Luca in quel topic non ha a che fare col Criterio di Eulero (che comunque è utile).
Dai un'occhiata semmai al simbolo di Legendre.
Ciao.
"Steven":
Tranquillo, quello che mi ha spiegato Luca in quel topic non ha a che fare col Criterio di Eulero (che comunque è utile).
Dai un'occhiata semmai al simbolo di Legendre.
Ciao.
Sì, hai ragione, leggendo un po' più con calma ho scoperto che non è così importante nella comprensione. Tuttavia, già che ci siamo vi dispiacerebbe rendermi dotto in materia? Scusate, se non avete voglia di spiegare queste cose ad un povero ignorante datemi anche solo qualche link utile, please... Grazie.
Per quanto riguarda il simbolo di Legendre, qualcosa dovrei ricordarmelo (ho rivisto la definizione e se non sbaglio è utilizzato nella cosiddetta legge di reciprocità dei residui quadratici di Gauss, legge però di cui ignoro il contenuto).
Infine, un'ultima delucidazione: che cosa è CRT? E' Chinese Remainder Theorem, vero? Cioè il Teorema Cinese del Resto?
Perchè anche qui c'è qualche dubbio nella mia mente. L'enunciato è
"Il sistema di congruenze lineari
${[x \equiv b_1modn_1],[x \equiv b_2modn_2],[\cdots],[x \equiv b_mmodn_m]:}$ in cui tutti gli $n_m$ sono primi tra loro ammette un'unica soluzione modulo $n_1n_2 \cdots n_m$"
Giusto (è possibile che la memoria mi inganni).
In ogni caso, come faccio però praticamente a risolvere il sistema?
Basterà un grazie per voi due? Be', al massimo mandatemi a casa la fattura a fine anno (o, ancora meglio, una volta ci troviamo e vi offro una pizza...
)GRAZIE,
Paolo.
Dunque, sono di nuovo qui per chiedervi di controllare i miei "progressi" nello studio.
Partiamo con una semplicissima equazione alle congruenze. Credo sia corretta, vorrei soltanto sapere il vostro parere sul procedimento.
$3x \equiv 6mod 12$
Ora un piccolo sistema.
${[x \equiv 3 mod 19],[x\equiv4mod7]:}$
Scusate il disturbo e grazie mille per il vostro aiuto.
A presto,
Paolo
Partiamo con una semplicissima equazione alle congruenze. Credo sia corretta, vorrei soltanto sapere il vostro parere sul procedimento.
$3x \equiv 6mod 12$
Ora un piccolo sistema.
${[x \equiv 3 mod 19],[x\equiv4mod7]:}$
Scusate il disturbo e grazie mille per il vostro aiuto.
A presto,
Paolo
Va bene.
"Paolo90":
Dunque, sono di nuovo qui per chiedervi di controllare i miei "progressi" nello studio.
Partiamo con una semplicissima equazione alle congruenze. Credo sia corretta, vorrei soltanto sapere il vostro parere sul procedimento.
$3x \equiv 6mod 12$
E' $(3,12)=3$ dunque si avranno tre soluzioni non congruenti modulo 12. Dividiamo per $3$ ottenendo $x \equiv 2mod4$. Dunque una prima soluzione è data da $x=2$. Le altre, procedendo come suggeriva Luca prima, si ottengono così: $x=2+12/3=6$ e $x=2+2*12/3=10$. La verifica conferma questi risultati. Dunque le soluzioni dell'equazione data sono $x=2+12k$,$6+12h$,$10+12q$ con $k,h,q in ZZ$. Che cosa ne dite?
In realtà qui è sufficiente da $x \equiv 2mod4$ ricavare i tre residui $mod12$ che ne derivano... 2, 6, 10 e quindi la soluzione cercata.
Grazie mille. Se ho ancora problemi vi scriverò.
Grazie ancora,
Paolo
Grazie ancora,
Paolo
Sì, hai ragione, leggendo un po' più con calma ho scoperto che non è così importante nella comprensione. Tuttavia, già che ci siamo vi dispiacerebbe rendermi dotto in materia? Scusate, se non avete voglia di spiegare queste cose ad un povero ignorante datemi anche solo qualche link utile, please... Grazie.
http://it.wikipedia.org/wiki/Criterio_di_Eulero
E' sintetica ed essenziale.
Infine, un'ultima delucidazione: che cosa è CRT? E' Chinese Remainder Theorem, vero? Cioè il Teorema Cinese del Resto?
Si.
In ogni caso, come faccio però praticamente a risolvere il sistema?
C'è la formula apposita, che trovi qua
http://it.wikipedia.org/wiki/Teorema_cinese_del_resto
Avevo chiesto chiarimenti, diverso tempo fa, sul perché di tale formula (non avevo compreso la dimostrazione).
Trovi qua
https://www.matematicamente.it/forum/chi ... 21048.html
Be', al massimo mandatemi a casa la fattura a fine anno (o, ancora meglio, una volta ci troviamo e vi offro una pizza...
Niente pizza, vada per il conto che ti sarà recapitato a casa
Sì, ho dato uno sguardo su wiki e ho trovato le informazioni di cui avevo bisogno (non crdere però di averla scampata: non ho ancora finito di torturarti.. ... Abbi pazienza, sto approfittando della tua bontà, anche per le correzioni dell'altro post... )
Grazie comunque anche per il link sul CRT qui su matematicamente...
Allora, dottore, ci mettiamo d'accordo via PM per la fattura?
A presto, Paolo
... Abbi pazienza, sto approfittando della tua bontà, anche per le correzioni dell'altro post... )Grazie comunque anche per il link sul CRT qui su matematicamente...
Allora, dottore, ci mettiamo d'accordo via PM per la fattura?
A presto, Paolo
"Paolo90":
Allora, dottore, ci mettiamo d'accordo via PM per la fattura?
Vabbe, vada per la pizza dai.
Non mi piacciono tutte 'ste complicazioni
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo