Congruenza

Messaggioda MissFoxy » 21/07/2017, 23:02

Ciao! :D

Ho dei problemi a risolvere questa congruenza:

31 x = 56 (mod 70)

come posso fare?
MissFoxy
New Member
New Member
 
Messaggio: 1 di 84
Iscritto il: 21/07/2017, 22:54

Re: Congruenza

Messaggioda spugna » 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.
$2022=phi^15+phi^13+phi^10+phi^5+phi^2+phi^(-3)+phi^(-6)+phi^(-11)+phi^(-16)$
Avatar utente
spugna
Average Member
Average Member
 
Messaggio: 215 di 818
Iscritto il: 05/07/2016, 20:40

Re: Congruenza

Messaggioda MissFoxy » 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?
MissFoxy
New Member
New Member
 
Messaggio: 2 di 84
Iscritto il: 21/07/2017, 22:54

Re: Congruenza

Messaggioda spugna » 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.
$2022=phi^15+phi^13+phi^10+phi^5+phi^2+phi^(-3)+phi^(-6)+phi^(-11)+phi^(-16)$
Avatar utente
spugna
Average Member
Average Member
 
Messaggio: 216 di 818
Iscritto il: 05/07/2016, 20:40

Re: Congruenza

Messaggioda MissFoxy » 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! :D :D
MissFoxy
New Member
New Member
 
Messaggio: 3 di 84
Iscritto il: 21/07/2017, 22:54


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite