Congruenze lineari ed equazioni diofantee

[Kvashir]

Ciao ragazzi, sto studiando l'argomento posto come titolo e non essendo per niente bravo non riesco a capire dove sbaglio...
vi posto il testo:

Decidere se la congruenza 12568x = 14356(mod 20) è compatibile, in tal caso determinare tutte le congruenze non congruenti tra loro modulo 20.

Dunque, intanto una delucidazione, cosa vuol dire "compatibile"?

ecco come ho provato a risolverla:

$12568x*20y-=14356$

ho ottenuto il MCD(12568,20) con le divisioni successive:

$12568 = 20*628+8$
$20 = 8*2+4$
$8 = 4*2+0$

quindi:

$MCD = 4$

A questo punto, ho diviso l'equazione per 4 (corretto?) ottenendo:
$3142x+5y=3589$

Ora come dovrei procedere? divisioni successive per calcolare i resti e poi identità di bezout? Potete gentilmente darmi delle dritte o aiutarmi nella risoluzione? più facilmente possibile magari, vi ringrazio! E scusatemi per il quesito molto poco complesso!

[Kashaman]

prima di tutto fai una cosa saggia.
tu hai $12568x-=14356(mod20)$
riduci innanzi tutto i coefficienti a modulo 20

(scrivi con le formule please)

[Kvashir]

"Kashaman":prima di tutto fai una cosa saggia.
tu hai $12568x-=14356(mod20)$
riduci innanzi tutto i coefficienti a modulo 20

(scrivi con le formule please)

$8x-=16(mod20)$
esatto?

[Kashaman]

esatto. Ora hai trovato un'equazione equivalente.
Ora chi è $d$? (il gcd di 8 e20)
è vero che $d|16$ e quindi la congruenza è compatibile?.
se si , allora possiamo ridurre tutto dividendo per $d$ ed otteniamo...

[Kvashir]

$2x-=4(mod5)$

da cui l'equazione diofantea:

$2x+5y=4$

[Kashaman]

bene,non ci resta che risolvere questa congruenza. (quante soluzioni modulo 20 avrà?)
E per farlo , bisogna calcolare un inverso aritmetico di due modulo 5.

[Kvashir]

Chiedo venia per l'ignoranza, ma come calcolo l'inverso aritmetico?

Forse sbaglio, ma riflettendoci potrebbe essere quel numero che moltiplicato con a nella congruenza $2x-=1(mod5)$ risulta congruo 1 modulo 5, quindi 3?

Magari sto dicendo una fesseria... Quindi mi scuso già ora!

[gundamrx91-votailprof]

Credo sia tutto giusto.

[Kashaman]

esattamente l'inverso di $2$ modulo cinque è $3$ .
ora non ti resta che moltiplicare ambo i membri per $3$ e ottieni...

[Kvashir]

$2*3+5*3=4$ ?

e quindi:

$6x+15y=4$

[Kashaman]

Aspetta, calmo. Lasciamo perdere per un attimo le equazioni diofantee.
Noi abbiamo che $2x-=4(mod5)$
possiamo vederla come $[2x]_5=[4]_5$
ora abbiamo notato che l'inverso di $2$ in $ZZ_5$ è tre, giusto?
perché $3*2-=1(mod5)$ ( o equivalentemente $[3*2]_5=[6]_5=[1]_5$)
dunque
$[3]_5[2x]_5=[3]_5[4]_5$ e cioè
$3*2x-=12(mod5) $ e quindi
$6x-=12(mod5) => x-=2(mod5)$
quindi le soluzioni della congruenza di partenza saranno date al variare di $k$ da
$x=2+5k$ (2)
ora , la congruenza di partenza ricercava le soluzioni modulo 20. Essendo $d=5$ a partire da ti ricavi tutte le soluzioni modulo 20