Aiuto congruenza linerare

[BoG3]

Ciao a tutti, ho un problema con una congruenza lineare che non riesco a risolvere:

$31x-=15 (\text(mod) 81)$
Questo è quello che faccio io:
moltiplico entrambi i lati per $31^(-1)$
$31^(-1)31x-=31^(-1)15 (\text(mod) 81)$ per ottenere
$x-=31^(-1)15 (\text(mod) 81)$, ora devo trovare $31^(-1) \text(mod81)$.

Trovo l'$MCD(31, 81)$:
$81 = 31*2 +19$
$31 = 19*2 + 12$
$19 = 12*1 + 7$
$12 = 7*1 + 5$
$7 = 5*1 + 2$
$5 = 2*2 +1$

poi esplicito i resti:
$81 - 31*2 =19$
$31 - 19*2 =12$
$19 - 12*1 =7$
$12 - 7*1 =5$
$7 - 5*1 =2$
$5 - 2*2 =1$

Ora cerco di trovare il mio $1$ come combinazione lineare di $31$ e $81$:
$1 = 5-2*(2)=$
$ 5-2*(7- (5)*1) =$
$5-2*(7)+2*(5) =3*(5)-2*(7)=$
$3*(12-7*1)-2*7 = 3*(12) - 3*(7) -2*(7) = 3*(12) -5*(7)=$
$3*(12)-5*(19-(12)*1) = 3*(12)-5*(19)+5*(12) = 8*(12)-5*(19)=$
$8*(31-2*(19)) -5*(19)= 8*(31) -16*(19)-5*(19) =8*(31)-21*(19) =$
$8*(31) -21(81- 2*(31)) = 8*(31) - 21*(81)+42*(31) = 30*(31)+50*(81)$

Quindi il mio inverso di $31 \text(mod 81)$ è $30\text(mod81)$
quindi $x-=31^(-1)15 (\text(mod) 81)$ diventa
$x-=30*15 (\text(mod) 81)$
$x-=450(\text(mod) 81)$
quindi le mie soluzioni sono $[450]_(81) = [45]_(81)$

La soluzione proposta sulle slide è $[60]_(81)$.
Ho provato a rifare i calcoli 3 volte da zero ma ottengo sempre un risultato diverso.
Potete darmi una mano a trovare l'errore?
GRazie

[spugna2]

"BoG":
$31 = 19*2 + 12$

Immagino volessi scrivere $19*1$

Comunque se ti può interessare c'è un modo un po' più veloce per trovare l'inverso moltiplicativo:
per avere $ 31a-=1 (\text(mod) 81) $ è necessario che sia vero $\text(mod) 27$, quindi $ 4a-=1 (\text(mod) 27) \Rightarrow a-=7 (\text(mod) 27)$.

A questo punto puoi scrivere $a=27b+7$ e sostituire

$ 31(27b+7)-=1 (\text(mod) 81) \Rightarrow 108b+216-=0 (\text(mod) 81) \Rightarrow 4b+8-=0 (\text(mod) 3)$

dove nell'ultimo passaggio abbiamo diviso tutto per $27$: a questo punto

$b=3c+1 \Rightarrow a=27(3c+1)+7=81c+34 \Rightarrow a-=34 (\text(mod) 81)$

[BoG3]

Ciao, grazie della risposta.
Si, hai ragione, volevo scrivere $31 = 19*1+12$, ho controllato sul quaderno ed in effetti avevo scritto così. Purtroppo mi vengono comunque cose diverse ..a sto punto riprovro'.

Invece vorrei chiederti piu' informazioni sul procedimento che hai fatto dopo.
Ad esempio vorrei chiedere perchè $31a -= 1 \text(mod81)$ sia vera deve essere vera anche per $4a -=1\text(mod27)$ ?
In che modo hai semplificato? vedo che hai diviso $81$ per $3$ e al $31$ hai sottratto $27$ per avere un numero piu' gestibile, giusto?

Poi vedo che hai scritto $a = 27b+7$ per esprimere tutti i possibili inversi, no?
Quando poi hai inserito $a$ nella congruenza: $31(27b+7) -= 1\text(mod 81)$ avrei potuto porre $b=1$ (per trovare solo una soluzione?) e poi come hai fatto a far diventare $\text(1mod81)$ in $\text(0mod81)$ ?

A questo punto ti devi trovare l'inverso di $4$ invece di $31$ perchè hai semplificato(?), giusto?
Non credo di aver capito d dove viene fuori $b = 3c+1$.

Grazie

[spugna2]

"BoG":Ad esempio vorrei chiedere perchè $31a -= 1 \text(mod81)$ sia vera deve essere vera anche per $4a -=1\text(mod27)$ ?
In che modo hai semplificato? vedo che hai diviso $81$ per $3$ e al $31$ hai sottratto $27$ per avere un numero piu' gestibile, giusto?

In generale una condizione necessaria (ma non sufficiente) per avere $a-=b (\text(mod c))$ è $a-=b (\text(mod d))$, dove $d$ è un divisore di $c$. In questo caso, come forse avevi già capito, ho scelto $d=27$ per poter ridurre il $31$, cosa che si può fare perché in una congruenza modulo $n$ si possono aggiungere/sottrarre multipli di $n$, e quindi $31a$ può diventare $31a-27a=4a$

"BoG":Quando poi hai inserito $a$ nella congruenza: $31(27b+7) -= 1\text(mod 81)$ avrei potuto porre $b=1$ (per trovare solo una soluzione?) e poi come hai fatto a far diventare $\text(1mod81)$ in $\text(0mod81)$ ?

Se vedi a occhio che $b=1$ funziona sei a posto perché da qui troverai una soluzione per $a$, che sarà unica (come intero modulo $81$) perché è un inverso moltiplicativo. In ogni caso il passaggio è semplicemente $31(27b+7)=31*27b+217$. A questo punto basta sottrarre $1$ a entrambi i membri (per avere $0$ a destra), e ridurre $31*27$ modulo $81$

"BoG":Non credo di aver capito d dove viene fuori $b = 3c+1$.

Se ti è chiaro come si arriva a $4b+8-=0 (\text(mod 3))$ ti basta risolvere questa equazione, che ti dà $b-=1 (\text(mod 3))$, ma questo vuol dire proprio che $b-1$ è un multiplo di $3$, da cui $b=3c+1$

[BoG3]

"spugna":
$ 31(27b+7)-=1 (\text(mod) 81) \Rightarrow 108b+216-=0 (\text(mod) 81) \Rightarrow 4b+8-=0 (\text(mod) 3)$

Scusa ma se fai $ 31(27b+7) = 837b +217$ come fa a te a venire $108b$?

[spugna2]

Ricorda che hai a che fare con una congruenza modulo $81$, e quindi che puoi aggiungere multipli di $81$ a tuo piacimento. In particolare puoi sostituire $837$ con il suo resto nella divisione per $81$, cioè $27$. Io per evitare di calcolare $31*27$ avevo fatto così: $31*27b=(4+27)*27b=108b+729b$, ma dato che $729$ è multiplo di $81$ posso eliminare il secondo termine. Il punto è che tutti questi numeri ($27$, $108$, $837$ e molti altri) vanno bene, nel senso che se vai avanti trovi sempre lo stesso risultato, che è sempre quello giusto. Più precisamente, va bene qualunque numero che diviso per $81$ dia resto $27$.

[G.D.5]

Scusatemi ma, a parte l'inverso di \( 31 \bmod 81 \) che è \( 34 \) e non \( 30 \), come è stato fatto notare da spugna e come risulta anche a me usando l'identità di Bézout, \( 31 \cdot 60 \) non da mica resto \( 15 \) nella divisione per \( 81 \): il resto è \( 78 \). O no?

[BoG3]

Ciao, grazie della pazienza, spugna!
Allora, dato che anche a merifaccendo i calcoli da $34$ posso dire che: se l'inverso è $34$ e non $30$ (perchè ho sbagliato a fare i calcoli )
ricapitolando la parte finale dell'esercizio:
posso passare da $31x-}15 \text(mod 81)$ a $x -= 15*34\text(mod 81)$, no ?
Da cui poi la classe delle soluzioni è $[15*34]_(81)$ che poi al massimo va semplificato. Giusto?

[spugna2]

Giusto, ma come ha fatto notare G.D. viene $24$ e non $60$

[BoG3]

Boh, non so che dirvi... io mi sono fidato delle soluzioni e con il mio inverso non riuscivo a semplificare la classe a $[60]_(81)$. Al meno ora ho imparato qualcosa in piu' (spero )

Grazie mille