Discussioni su Algebra astratta, Logica Matematica, Teoria dei Numeri, Matematica Discreta, Teoria dei Codici, Algebra degli insiemi finiti, Crittografia.
21/07/2017, 23:02
Ciao!
Ho dei problemi a risolvere questa congruenza:
31 x = 56 (mod 70)
come posso fare?
21/07/2017, 23:44
Che tipo di problemi hai? Hai fatto qualche tentativo? (da regolamento dovresti scriverne uno...)
Comunque
Testo nascosto, fai click qui per vederlo
Uno dei procedimenti standard è spezzare $70$ in fattori coprimi e ricondursi a equazioni con numeri più bassi:
ad esempio da $70=7*10$ si ha:
- $31x -= 56$ $( mod 7) \Rightarrow 3x -= 0$ $(mod 7) \Rightarrow x=7y$;
- $31x -= 56$ $( mod 10) \Rightarrow x-=6$ $(mod 10) \Rightarrow 7y-=6$ $(mod 10) \Rightarrow y-=8$ $(mod 10)$, cioè $y=10z+8$.
A questo punto, $x=7y=7(10z+8)=70z+56-=56$ $(mod 70)$.
Altrimenti, se noti che $70$ e $56$ sono entrambi divisibili per $7$, chiaramente deve esserlo anche $31x$, quindi puoi porre $x=7y$ e dividere tutto per $7$: viene $31y-=8$ $(mod 10)$, e si conclude come prima.
22/07/2017, 00:04
Grazie per la risposta!
Sì, hai ragione scusa
Il prof l'ha scritta così: $ [x][31] = [56] mod70 $
ho provato a risolverla trovandomi l'MCD e trovando poi l'identità di Bézout che mi veniva
$ 1 = (4)*70 + (-9)*31 $
A quel punto mi sono bloccata.
Non ho mai visto il prof risolvere una congruenza in quel modo (dividendo 70 in 7 e 10).
Si può risolvere continuando il mio procedimento?
22/07/2017, 06:53
Se hai trovato i numeri che soddisfano l'identità di Bezout basta moltiplicare tutto per il secondo membro dell'equazione:
$4*70-9*31=1 \Rightarrow 56*4*70-56*9*31=56$
da cui la soluzione $x-= -56*9-=56$ $(mod 70) $.
Per completezza, nel caso non lo avessi mai visto, il procedimento che ho scritto prima usa il teorema cinese del resto: se hai un sistema di equazioni del tipo $x -= a_i $ $(mod b_i) $, dove i $b_i $ sono a due a due coprimi, detto $n $ il prodotto di questi ultimi esiste un unico $x in ZZ\text {/}n ZZ $ che le risolve tutte.
22/07/2017, 09:12
In mia difesa, il teorema cinese del resto non l'ha messo in programma e non l'ha fatto
Grazie mille per l'aiuto e per la velocità della risposta, ora ho capito!
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.