Salve e aiuto su Congruenze

[xlucyx]

Salve, sono una studentessa di informatica, e sto avendo problemi con le congruenze lineari....
ad esempio
se ho 3x = 4 mod 5

bisogna trovare le due soluzioni (xo,y0) della diofantea

3x+5y=4

quindi procedo con l'algoritmo di euclide a trovare l'MCD tra 3 e 5
che risulta 1 quindi ci saràuna soluzione incongrua modula 5.

adesso lavoro con i resti e trovo che x0=2 e y0=-1

Giusto?
e adesso?
non so come continuare

mi aiutate perfavore?

grazie

[fields1]

A dire il vero hai x0=3 e y0=-1. E dunque poni x=x0.

[xlucyx]

mmmm se ho sbagliato e anzike 2 è 3 allora la classe di congruenza sarebbe [3]5?

cmq ecco il risultato dei miei resti

5=1*3+2
3=1*2+1
2=1*2+0

MCD(3,5)=1

2=5-3*1
1=3-2*1=3-(5-3*1)*1=3-5+3*1=2*3-5

x0=2

ecco come ci sono arrivta...dove ho sbagliato?

[xlucyx]

nessuno?

[miuemia]

ciao scusa ma devi semplicemente risolvere la congruenza?

[neryo]

"xlucyx":
adesso lavoro con i resti e trovo che x0=2 e y0=-1
Giusto?

giusto!

d=a*x0+n*y0
1=3*2+5*(-1)=6-5=1

x0=2

[fields1]

Non è per niente giusto... Le soluzioni le ho scritte sopra, basta applicare l'algoritmo di euclide per ottenerle.

[neryo]

"fields":Non è per niente giusto... Le soluzioni le ho scritte sopra, basta applicare l'algoritmo di euclide per ottenerle.

boh anche a me viene come xlucyx... usando la tabellina..

-1 -1
1 0 1 -1
0 1 -1 2

[neryo]

si ha ragione fields x0 = 3

questo perche' quel 2 e' la x per 3x+5y=1
ma bisogna trovare quella per 3x+5y=4
quindi per trovare x0 devi moltiplicare la x trovata per k che e' b/MCD quindi k = 4

x0 = k*x = 4*2 = 8 congruo 3 mod 5

quindi x0 = 3

spiegato da schifo ma giusto fields?

[xlucyx]

grazie, quindi ho fatto bene l'algoritmo devo solo moltiblicare il mio x*k

quindi 8=3 mod 5

ma perche 3? se x0 è 8?scusate l'ignoranza ragazzi...

[fields1]

"neryo":spiegato da schifo ma giusto fields?

Yes.

"xlucyx":ma perche 3? se x0 è 8?scusate l'ignoranza ragazzi...

Perché lavori con le classi di congruenza e 3 è congruo a 8 modulo 5.