Risoluzione equazione congruenziale

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.

Risoluzione equazione congruenziale #72486

avt
Minimal19
Punto
Salve ragazzi, vorrei chiedervi aiuto per un'equazione congruenziale che ho provato a risolvere.

396x \equiv 144 \ (mod \ 156)


Dopo che mi sono calcolato il MCD=12 ho diviso a,b,n per codesto e ottengo:

33x\equiv12\ (mod\ 13)

tramite l'equazioni diofantee procedo e ottengo come soluzione -36.

33= 13\cdot 2+7\ \to\ 7= 33+13(-2)

13= 7\cdot 1+6\ \to\ 6= 13+7(-1)

7= 6\cdot 1+1\ \to\ 1= 7+6(-1)

6= 6\cdot 1+0

Successivamente partendo dall'equazione dell'1 e andando a sostituire ho:

1= 7+6(-1)=

= 33+13(-2) + (13+7(-1))(-1)=

= 33+13(-2) + 13(-1) + 7(1)=

= 33+ 13(-3) +7(1)=

Quindi ho che:

1= 13(-3) + 40(1)

Dato che il b è 12, vado a moltiplicare il 12 per la quantità nelle parentesi e pongo tutta l'equazione uguale a 12, ovvero;

12= 13(-3\cdot 12) + 40(1\cdot 12)=13(-36) + 40 (12)

Ed ho che -36 è una delle soluzioni. Per verificare le altre soluzioni avrò: -36 + 13\cdot h con h\in \mathbb{Z}

Sono corretti i miei passaggi?
 
 

Risoluzione equazione congruenziale #72516

avt
Galois
Amministratore
Ciao Minimal19 emt

Sarebbe più corretto dire che siamo di fronte ad una equazione congruenziale:

396x \equiv 144 \ (mod \ 156)

Ora, prima di procedere a trovare le soluzioni, sarebbe opportuno verificare se essa ammette o meno soluzioni.

Ricordando che, una equazione congruenziale

ax \equiv b \ (mod \ n)

ha soluzione se e solo se

mcd(a,n) \ | \ b

(ovvero se e solo se il massimo comun divisore tra a ed n divide b)

procediamo col trovare il massimo comun divisore tra a=396 ed n=156 e vediamo se è un sottomultiplo di b=144. Se lo è la nostra equazione ammette soluzione, altrimenti no.

Poiché

mcd(396, 156) = 12

che divide 144, la nostra equazione ha soluzione.

Osservando inoltre che a, b ed n sono tutti multipli di 12, possiamo dividere tutto per 12 in modo da ricondurci (come hai ben fatto) alla più semplice equazione congruenziale:

33x \equiv 12 \ (mod \ 13)

Ora, per risolvere tale equazione dobbiamo trovare l'inverso moltiplicativo di 33 modulo 13 in modo da poter poter moltiplicare a destra e a sinistra per quel numero ed ottenere

x\equiv \mbox{qualcosa} \ (mod \ 13)

che sarà la soluzione cercata.

Per trovare tale inverso moltiplicativo, ovvero quel numero (diciamolo c) tale che

33 c \equiv 1 \ (mod \ 13)

possiamo procedere in due modi:

- sfruttando l'identità di Bezout (come hai fatto tu)

- procedendo per tentativi.

Vediamoli entrambi. Procedere per tentativi vuol dire provare a moltiplicare il 33 per tutti i numeri naturali da 1 a 12 finché non si ottiene un numero che sia congruo ad 1 modulo 13. Poiché, subito:

33 \cdot 2 = 66 \equiv 1 \ (mod \ 13)

abbiamo che l'inverso moltiplicativo cercato è 2.

Moltiplicando ambo i membri dell'equazione congruenziale

33x \equiv 12 \ (mod \ 13)

per 2 si ha:

66x \equiv 24 \ (mod \ 13)

ovvero

x \equiv 11 \ (mod \ 13)

in quanto

66 \equiv 1 \ (mod \ 13) (l'abbiamo trovato di proposito)

e

24 \equiv 11 \ (mod 13)

Ragion per cui tutte e sole le soluzioni della nostra equazione saranno:

x=11+13k, \ k \in \mathbb{Z}

------------

Procediamo ora sfruttando l'identità di Bezout e vediamo dove sbagli.

Ripartiamo dall'equazione congruenziale

33x \equiv 12 \ (mod \ 13)

Essendo il massimo comun divisore tra 33 e 13 uguale ad 1, esistono x ed y interi tali che

(*) \ 33x+13y=1

da cui

13y = 1-33x

e quindi, per definizione di congruenza

33x \equiv 1 \ (mod \ 13)

L'inverso moltiplicativo di 33 modulo 13 sarà quindi l'x che troveremo da (*)

Ora, come hai ben fatto:

33= 13 \cdot 2 +7 \ \to \ 7 = 33-13 \cdot 2

13= 7 \cdot 1 + 6 \ \to \ 6 = 13-7 \cdot 1

7= 6 \cdot 1 + 1 \ \to \ 1 = 7-6 \cdot 1

6=6 \cdot 1  + 0

Però da questo punto in poi sbagli qualcosa. Noi infatti, sfruttando le relazioni appena scritte, dobbiamo scrivere l'1 come combinazione lineare tra 33 e 13 ed il numero che moltiplicherà il 33 sarà, per quanto prima detto, l'inverso che stiamo cercando.
Tu alla fine di tutto hai ottenuto

1=13 \cdot (-3) + 40

la quale, seppur essendo un'uguaglianza vera, non va bene in quanto il nostro scopo, ripeto, è quello di scrivere l'1 come combinazione lineare tra 13 e 33 e non tra 13 e 40.

Vediamo come fare.

Dall'ultima relazione abbiamo

1=7-6

dalla seconda, essendo 6 = 13-7 \cdot 1

andando a sostituire si ha

1=7-[13-7 \cdot 1] = 7-13+7 = 7 \cdot 2 - 13

Infine dalla prima abbiamo 7 = 33-13 \cdot 2 e sostituendo

1=7-[13-7 \cdot 1] = 7-13+7 = 7 \cdot 2 - 13 = [33-13 \cdot 2] \cdot 2 - 13=

=33 \cdot 2 -13 \cdot 4 - 13 = 33 \cdot 2 + 13 \cdot (-5)

Ovvero:

1=33 \cdot {\color{red}2}+13 \cdot (-5)

Come puoi vedere abbiamo riottenuto il 2 (come quando si è proceduto per tentativi).

A questo punto si procede allo stesso identico modo. Si moltiplicano cioè ambo i membri di

33x \equiv 12 \ (mod \ 13)

per 2

66x \equiv 24 \ (mod \ 13)

da cui

x \equiv 11 \ (mod \ 13)

emt
Ringraziano: Omega, Ifrit, CarFaby

Re: Risoluzione equazione congruenziale #72557

avt
Minimal19
Punto
Grazie per la risposta Galois ma non ho ancora capito un passaggio che effettui.
A parte l'errore che hai scritto:

1=13 \cdot 2 + 13(-5) (impossibile)

ma bensì, nella forma corretta si scrive:

1=33 \cdot 2 + 13(-5)

Sorvolando questo problema non ho capito come hai fatto a passare da:

66x \equiv\ 24(mod\ 13)

a

x \equiv\ 11(mod\ 13)

emt

Re: Risoluzione equazione congruenziale #72576

avt
Galois
Amministratore
Più di un errore direi che la prima è una svista, dato che ho semplicemente riportato quanto scritto nel rigo precedente. In ogni caso ora ho sistemato.

Se non hai capito come son passato da

66x \equiv 24 \ (mod \ 13)

a

x \equiv 11 \ (mod \ 13)

sarebbe il caso che tu ripeta la definizione di congruenza modulo n emt

Dovresti infatti sapere che, per definizione:

a \equiv b \ (mod \ n) \iff n|(a-b)

Poiché stiamo lavorando modulo 13, e poiché

66 \equiv 1 \ (mod \ 13)

[in quanto 13 divide (66-1 = 65)]

24 \equiv 11 \ (mod \ 13)

[in quanto 13 divide (24-11 = 13)]

possiamo (anzi dobbiamo) passare da

66x \equiv 24 \ (mod \ 13)

a

x \equiv 11 \ (mod \ 13)

che poi è la soluzione della nostra equazione.

------------

Per farla breve, pensa alle normali equazioni di primo grado.

Una volta arrivati ad una scrittura del tipo

ax=b, \ \mbox{con} \ a \neq 0

cosa si fai per trovare il valore dell'incognita x?

Si moltiplica a destra e sinistra per l'inverso moltiplicativo \frac{1}{a} \ \mbox{di} \ a.

Per le equazioni congruenziali il ragionamento è lo stesso. Solo che si ragiona modulo un intero.

Cioè una volta giunti a

33x \equiv 12 \ (mod \ 13)

si deve trovare l'inverso moltiplicativo modulo 13 di 33 (procedendo o per tentativi o sfruttando l'identità di Bezout come ti ho fatto vedere nella precedente risposta).

Una volta trovato (nel nostro caso era 2) si moltiplicano ambo i membri per 2:

66x \equiv 24 \ (mod \ 13)

E, il coefficiente del primo membro sarà necessariamente equivalente ad 1 (modulo 13) in quanto abbiamo moltiplicato il 33 per il suo inverso. Per quanto riguarda il secondo membro se, come in questo caso, si ottiene un numero maggiore del modulo n lo si riduce sfruttando la definizione di congruenza.

Tutto qui emt
Ringraziano: Omega, Ifrit, CarFaby
  • Pagina:
  • 1
Os