Congruenze lineari e perplessità
Salve a tutti,
scusate se sono ancora qui a farvi domande, come ogni giorno, ma ho provato a cercare e non c'è nulla che risolve il mio dubbio sulle congruenze. Ovvero, ho capito come risolverle, ma non mi è chiaro "il risultato che otteniamo".
Ovvero prendiamo la congruenza lineare $36x -= 12 (mod 42)$
Sappiamo che è compatibile perchè $mcd(36,42)=6$ e $6|12$
A questo punto la trasformiamo in una equazione diofantea per trovare almeno una $x0$ che è soluzione della congruenza e quindi avremo:
$36x0+42y=12$
Per non starmi a calcolare l'identità di bezout divido tutto per d, ovvero per 6 ed ottengo:
$6x0+7y=2$
e qui trovo subito che ad esempio $x0=-2$ è una soluzione della nostra congruenza lineare
A questo punto possiamo correttamente affermare che la congruenza lineare ha infinite soluzioni che si trovano tramite questa formula:
$x=x0 + n/d * h$ che nel nostro caso è $-2 + 42/6 *h$ ? ovviamente con $h in ZZ$
A questo punto mi sfugge la parte della definizione di congruenza lineare in cui dice che "tra queste infinite soluzioni ci sono d soluzioni tra loro non congrue modulo 42"
So che per calcolarmi queste $d$ soluzioni, dove d sarà l'mcd calcolato prima, ovvero $6$, basta che faccio variare $h in ZZ$ da $0$ a $6-1$
ovvero in questo caso avrei:
con $h=0$ $x=-2$ ovvero $-2 -= -2 (mod 42)$
con $h=1$ $x=5$ ovvero $5 -= 5 (mod 42)$
...
fino ad arrivare ad con $h=5$ $x=33$ ovvero $33 -= 33 (mod 42)$
Ma cosa rappresenterebbero queste? e soprattuto potrei scriverle come $[-2]_42, [5]_42,.., [33]_42$ ? e perchè qualsiasi altra soluzione dovrebbe essere congrua ad una di queste classi?
Ovvero se prendo $h=6$ $x=40$ ovvero $40 -= 40 (mod 42)$ ovvero $[40]42$, a cosa dovrebbe essere equivalente questa classe?
Forse, anzi sicuramente, ho un pò di confusione in testa riguardo a questo pezzo "delle soluzioni al variare di h". Ma non riesco a trovare nulla di più chiaro in rete, quindi mi rimetto al vostro aiuto.
Vi ringrazio in anticipo,
Neptune.
scusate se sono ancora qui a farvi domande, come ogni giorno, ma ho provato a cercare e non c'è nulla che risolve il mio dubbio sulle congruenze. Ovvero, ho capito come risolverle, ma non mi è chiaro "il risultato che otteniamo".
Ovvero prendiamo la congruenza lineare $36x -= 12 (mod 42)$
Sappiamo che è compatibile perchè $mcd(36,42)=6$ e $6|12$
A questo punto la trasformiamo in una equazione diofantea per trovare almeno una $x0$ che è soluzione della congruenza e quindi avremo:
$36x0+42y=12$
Per non starmi a calcolare l'identità di bezout divido tutto per d, ovvero per 6 ed ottengo:
$6x0+7y=2$
e qui trovo subito che ad esempio $x0=-2$ è una soluzione della nostra congruenza lineare
A questo punto possiamo correttamente affermare che la congruenza lineare ha infinite soluzioni che si trovano tramite questa formula:
$x=x0 + n/d * h$ che nel nostro caso è $-2 + 42/6 *h$ ? ovviamente con $h in ZZ$
A questo punto mi sfugge la parte della definizione di congruenza lineare in cui dice che "tra queste infinite soluzioni ci sono d soluzioni tra loro non congrue modulo 42"
So che per calcolarmi queste $d$ soluzioni, dove d sarà l'mcd calcolato prima, ovvero $6$, basta che faccio variare $h in ZZ$ da $0$ a $6-1$
ovvero in questo caso avrei:
con $h=0$ $x=-2$ ovvero $-2 -= -2 (mod 42)$
con $h=1$ $x=5$ ovvero $5 -= 5 (mod 42)$
...
fino ad arrivare ad con $h=5$ $x=33$ ovvero $33 -= 33 (mod 42)$
Ma cosa rappresenterebbero queste? e soprattuto potrei scriverle come $[-2]_42, [5]_42,.., [33]_42$ ? e perchè qualsiasi altra soluzione dovrebbe essere congrua ad una di queste classi?
Ovvero se prendo $h=6$ $x=40$ ovvero $40 -= 40 (mod 42)$ ovvero $[40]42$, a cosa dovrebbe essere equivalente questa classe?
Forse, anzi sicuramente, ho un pò di confusione in testa riguardo a questo pezzo "delle soluzioni al variare di h". Ma non riesco a trovare nulla di più chiaro in rete, quindi mi rimetto al vostro aiuto.
Vi ringrazio in anticipo,
Neptune.
Risposte
$[40]_42=[-2]_42$
Effettivamente fai di nuovo 40 modulo 42 ed hai il resto 2 che è uguale a -2? (questa cosa del segno non mi ricordo come mai "si ignorava" nel resto?
Ovvero possiamo dire che: i valori di $x0$ che otteremo sono infiniti; Ma le classi di resto distinte di $x0$ sono in realta $d$ ?
Ma quindi nella nostra congruenza iniziale $36x -= 12 (mod 42)$ possiamo sostituire tutte le x0 che troviamo e devono darci resto 12? o cosa?
Ovvero possiamo dire che: i valori di $x0$ che otteremo sono infiniti; Ma le classi di resto distinte di $x0$ sono in realta $d$ ?
Ma quindi nella nostra congruenza iniziale $36x -= 12 (mod 42)$ possiamo sostituire tutte le x0 che troviamo e devono darci resto 12? o cosa?
Frena frena: facciamo così.
Diciamo che le classi di resto negative sono "scomode", e quindi non ci piacciono, non le vogliamo
.
Per togliercele dai piedi si può fare così: la classe $[-x]$ modulo $n$ corrisponde alla classe $[n-x]$, sempre modulo $n$. Questo è un trucchetto semplicissimo che dovrebbe aiutarti a capire se hai dei dubbi con i rappresentanti negativi.
E' più facile a farsi che a dirsi: prendi $ZZ_7$ (cioè lavoriamo modulo $7$). A che cosa corrisponde classe $[-5]$? Easy: prendi 7 e gli togli 5: $[7-5]=[2]$.
Quindi, modulo 42, $[-2]=[42-2]=[40]$. Tutto chiaro ora?
Diciamo che le classi di resto negative sono "scomode", e quindi non ci piacciono, non le vogliamo
. Per togliercele dai piedi si può fare così: la classe $[-x]$ modulo $n$ corrisponde alla classe $[n-x]$, sempre modulo $n$. Questo è un trucchetto semplicissimo che dovrebbe aiutarti a capire se hai dei dubbi con i rappresentanti negativi.
E' più facile a farsi che a dirsi: prendi $ZZ_7$ (cioè lavoriamo modulo $7$). A che cosa corrisponde classe $[-5]$? Easy: prendi 7 e gli togli 5: $[7-5]=[2]$.
Quindi, modulo 42, $[-2]=[42-2]=[40]$. Tutto chiaro ora?
Si perfetto riguardo i valori negativi, ma riguardo a quell'altra domanda che ti facevo sopra?
Ovvero, dopo esserci calcolati le infinite x, possiamo prenderle, sostituirle alla x della congruenza lineare e avere come resto $12$ o cosa?
Ovvero, dopo esserci calcolati le infinite x, possiamo prenderle, sostituirle alla x della congruenza lineare e avere come resto $12$ o cosa?
"Neptune":
Si perfetto riguardo i valori negativi, ma riguardo a quell'altra domanda che ti facevo sopra?
Ovvero, dopo esserci calcolati le infinite x, possiamo prenderle, sostituirle alla x della congruenza lineare e avere come resto $12$ o cosa?
Ah be', penso proprio di sì, almeno se abbiamo lavorato bene.
Alla fine i conti devono tornare, per cui se sostituisci una qualsiasi $x$ soluzione nell'equazione devi ottenere una uguaglianza. Ad esempio, verifichiamo che $40$ è soluzione:
$36*40=1440$. Se dividi per $42$ questo risultato, trovi come resto proprio....
Tra l'altro, considerando quello che mi hai detto, allora è sbagliato dire che $-2 -= -2 (mod 42)$ bensì dovrebbe essere $-2 -= 40 (mod42)$ o no?
Come $5 -= 5 (mod 42)$ dovrebbe essere sbagliato, ed invece sarebbe giusto dire $5 -= 37 (mod 42)$ se vogliamo che $a-n=b$. O no?
Come $5 -= 5 (mod 42)$ dovrebbe essere sbagliato, ed invece sarebbe giusto dire $5 -= 37 (mod 42)$ se vogliamo che $a-n=b$. O no?
Ma $1440$ diviso $42$ da resto $0$
"Neptune":
Ma $1440$ diviso $42$ da resto $0$
[tex]1440=34*42+\boxed{12}$[/tex]
P.S. La relazione di congruenza modulo $n$ è di equivalenza, per cui $a=a mod n$, ($n in NN^+$).
Giusto mi sono visto un attimo un prontuario delle formule e mi sono accorto che il resto posso calcolarlo banalmente facendo la divisione se $a>n$ altrimenti posso utilizzare la formula che dice che $n|a-b$ ovvero dico che $a-(b)=n*h$
Ad esempio $[5]_42$ me lo calcolo facendo $5-(-37) = 42$ ovviamente $42|42$ e quindi posso dire che $5 -= -37 (mod 42)$ . Giusto?
Ad esempio $[5]_42$ me lo calcolo facendo $5-(-37) = 42$ ovviamente $42|42$ e quindi posso dire che $5 -= -37 (mod 42)$ . Giusto?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo