Congruenza

[MissFoxy394]

Ciao!

Ho dei problemi a risolvere questa congruenza:

31 x = 56 (mod 70)

come posso fare?

[spugna2]

Che tipo di problemi hai? Hai fatto qualche tentativo? (da regolamento dovresti scriverne uno...)

Comunque

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.

[MissFoxy394]

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?

[spugna2]

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.

[MissFoxy394]

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!