Problema esercizio da libro, risultato totalmente differente
Questa domanda riguarda semplicemente un esercizio da un eserciziario di geometria e algebra sulle congruenze mod(M).
Il mio metodo risolutivo è abbastanza meccanico, ma trovo trovo spesso soluzioni molto differenti, mi chiedo se sbaglio qualcosa io o è il libro che è fatto all'acqua di rose (libro scritto dalla prof, ovviamente =\)
Vado al punto: Risolvere la seguente congruenza $15x-=10mod20$
$(15,20)=5$ (MCD)
ho 5 soluzioni non congrue tra loro quindi. Procedo con l'identità di Bezout e trovo $x_*=-2$
Le soluzioni sono del tipo: $-2+5k , k in ZZ$ tutte le altre (5) soluzioni le ottengo dando a k i valori da 0,1,..,4 quindi: $ -2 , 3 , 8 , 13, 8 $
Soluzione del libro:
La congruenza ammette 5 soluzioni distinte modulo 20 (per lo stesso motivo di sopra), il libro risolve la congruenza semplificata: $3x-=2mod4$ che ha soluzione: $x=2+4h , h in ZZ$ Per $h=0+5k , 1+5k , 2+5k , 3+5k , 4+5k$ , si ottengono poi le 5 soluzioni modulo 20, $ x_1=2+5k , x_2=6+5k , x_3=10+5k , x_4=14+5k , x_5=18+5k$.
Cosa cavolo non ho capito??
Cito la teoria, per completezza (da altro libro della prof -.-):
Data $ax-= b mod m$ Se $a,b,m in ZZ , m>=2$ la congruenza ammette soluzione se, e solo se, $b=(a,m)t , t in ZZ$ , inoltre se esiste una soluzione, ogni altra soluzione é $c' = c+(m/(a,m))z , z in ZZ$ ovvero risulta $c-=c' mod (m/(a,m))$
Grazie in anticipo a chi sarà cosi gentile da schiarirmi le idee
Il mio metodo risolutivo è abbastanza meccanico, ma trovo trovo spesso soluzioni molto differenti, mi chiedo se sbaglio qualcosa io o è il libro che è fatto all'acqua di rose (libro scritto dalla prof, ovviamente =\)
Vado al punto: Risolvere la seguente congruenza $15x-=10mod20$
$(15,20)=5$ (MCD)
ho 5 soluzioni non congrue tra loro quindi. Procedo con l'identità di Bezout e trovo $x_*=-2$
Le soluzioni sono del tipo: $-2+5k , k in ZZ$ tutte le altre (5) soluzioni le ottengo dando a k i valori da 0,1,..,4 quindi: $ -2 , 3 , 8 , 13, 8 $
Soluzione del libro:
La congruenza ammette 5 soluzioni distinte modulo 20 (per lo stesso motivo di sopra), il libro risolve la congruenza semplificata: $3x-=2mod4$ che ha soluzione: $x=2+4h , h in ZZ$ Per $h=0+5k , 1+5k , 2+5k , 3+5k , 4+5k$ , si ottengono poi le 5 soluzioni modulo 20, $ x_1=2+5k , x_2=6+5k , x_3=10+5k , x_4=14+5k , x_5=18+5k$.
Cosa cavolo non ho capito??
Cito la teoria, per completezza (da altro libro della prof -.-):
Data $ax-= b mod m$ Se $a,b,m in ZZ , m>=2$ la congruenza ammette soluzione se, e solo se, $b=(a,m)t , t in ZZ$ , inoltre se esiste una soluzione, ogni altra soluzione é $c' = c+(m/(a,m))z , z in ZZ$ ovvero risulta $c-=c' mod (m/(a,m))$
Grazie in anticipo a chi sarà cosi gentile da schiarirmi le idee
Risposte
In generale si ha che una congruenza algebrica [tex]ax \equiv b_{(mod n)}[/tex] ha soluzione in due casi:
1) [tex]ax \equiv b_{(mod n)} \Leftrightarrow d=1[/tex]
2) [tex]ax \equiv b_{(mod n)} \Leftrightarrow d|b[/tex]
dove [tex]d=MCD(a,n)[/tex]
Nella tua congruenza il caso 1) non è verificato, ma il caso 2) si, infatti hai che [tex]MCD(15,20)=5[/tex], e questo ti permette di semplificare la congruenza dividendo tutto per [tex]5[/tex]:
[tex]15x \equiv 10_{(mod 20)}[/tex] è equivalente a [tex]3x \equiv 2_{(mod 4)}[/tex]
che ora ricade nel caso 1).
A questo punto per risolvere l'equazione congruenziale devi trovare l'inverso moltiplicativo di [tex]3_{(mod 4)}[/tex] al fine di semplificarla, e questo lo fai sapendo che:
[tex]3x \equiv 1_{(mod 4)} \Rightarrow 4 | 3x - 1 \Rightarrow \exists y \in \mathbb{Z}[/tex] tale che [tex]3x - 1 = 4y[/tex] e [tex]3x - 4y = 1[/tex] che ha soluzione per [tex]x=3[/tex] e [tex]y=2[/tex]. A questo punto la tua equazione congruenziale può essere scritta come:
[tex]x \equiv 6 \equiv 2_{(mod 4)}[/tex] le cui soluzioni (ricavate come sopra) sono nella forma [tex]x=2+4k, k \in \mathbb{Z}[/tex].
1) [tex]ax \equiv b_{(mod n)} \Leftrightarrow d=1[/tex]
2) [tex]ax \equiv b_{(mod n)} \Leftrightarrow d|b[/tex]
dove [tex]d=MCD(a,n)[/tex]
Nella tua congruenza il caso 1) non è verificato, ma il caso 2) si, infatti hai che [tex]MCD(15,20)=5[/tex], e questo ti permette di semplificare la congruenza dividendo tutto per [tex]5[/tex]:
[tex]15x \equiv 10_{(mod 20)}[/tex] è equivalente a [tex]3x \equiv 2_{(mod 4)}[/tex]
che ora ricade nel caso 1).
A questo punto per risolvere l'equazione congruenziale devi trovare l'inverso moltiplicativo di [tex]3_{(mod 4)}[/tex] al fine di semplificarla, e questo lo fai sapendo che:
[tex]3x \equiv 1_{(mod 4)} \Rightarrow 4 | 3x - 1 \Rightarrow \exists y \in \mathbb{Z}[/tex] tale che [tex]3x - 1 = 4y[/tex] e [tex]3x - 4y = 1[/tex] che ha soluzione per [tex]x=3[/tex] e [tex]y=2[/tex]. A questo punto la tua equazione congruenziale può essere scritta come:
[tex]x \equiv 6 \equiv 2_{(mod 4)}[/tex] le cui soluzioni (ricavate come sopra) sono nella forma [tex]x=2+4k, k \in \mathbb{Z}[/tex].
"eisen":
$x_*=-2$
Le soluzioni sono del tipo: $-2+5k , k in ZZ$ tutte le altre (5) soluzioni le ottengo dando a k i valori da 0,1,..,4 quindi: $ -2 , 3 , 8 , 13, 8 $
Quindi io ho sbagliato? =\ eppure è esattamente l'applicazione della teoria! Quello che non avevo capito non è la semplificazione ma il modo in cui il libro espone i risultati:
"eisen":
$3x-=2mod4$ che ha soluzione: $x=2+4h , h in ZZ$ Per $h=0+5k , 1+5k , 2+5k , 3+5k , 4+5k$ , si ottengono poi le 5 soluzioni modulo 20, $ x_1=2+5k , x_2=6+5k , x_3=10+5k , x_4=14+5k , x_5=18+5k$.
Cosa intendi con:
"GundamRX91":
$4 | 3x - 1 $
"4 divide 3x-1"?
In effetti hai sbagliato. Guarda, tu hai trovato che l'equazione congruenziale [tex]15x \equiv 10_{(mod 20)}[/tex] ha soluzione per [tex]x=-2+5k, k \in \mathbb{Z}[/tex]. Intanto se scrivi una cosa del genere significa che ha soluzione per ogni numero intero di quella forma, e non per soli 5 valori. Poi per sincerarti della tua soluzione potevi fare delle prove: ad esempio se
[tex]15 \cdot -2 \equiv 10_{(mod 20)} \Rightarrow 20 | -30-10[/tex] è vero, non è vero che [tex]15 \cdot 3 \equiv 10_{(mod 20)} \Rightarrow 20 | 45 -10[/tex] ok?
Si, [tex]20|3x-1[/tex] significa proprio quello che hai scritto
[tex]15 \cdot -2 \equiv 10_{(mod 20)} \Rightarrow 20 | -30-10[/tex] è vero, non è vero che [tex]15 \cdot 3 \equiv 10_{(mod 20)} \Rightarrow 20 | 45 -10[/tex] ok?
Si, [tex]20|3x-1[/tex] significa proprio quello che hai scritto
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo