Soluzioni di un'equazione congruenziale

[knowitall]

Salve, ho un dubbio riguardo a questo esercizio.

Si determinino tutte le soluzioni positive dell'equazione congruenziale
$84x≡68 (mod 400)$

Ho calcolato il Massimo Comune Divisore tra 84 e 400 ed è 4. 68 è divisibile per 4 quindi l'equazione ammette soluzioni. Ora non so come calcolare le soluzioni, ho controllato su internet e dal libro ma non mi è chiaro il procedimento. Potete aiutarmi?

[mauri54]

Devi calcolare tutte le soluzioni della diofantea omogenea $ 84x+400y=68 $ , ossia:
$ 84x+400y=0\quad\rightarrow\quad21x+100y=0\quad\rightarrow\quad21x=-100y\quad\rightarrow\quadx=100h,\quad y=-21h\quad\text{con }h\in\mathbb{Z} $

Poi bisogna trovare una soluzione particolare. Un modo algoritmico è usare l'algoritmo euclideo e poi ricondursi all'identità di Bezout.
$ 400=4\cdot84+64 $
$ 84=1\cdot64+20 $
$ 64=3\cdot20+4 $

Tornando indietro hai $ 4=64-3\cdot20=64-3\cdot(84-64)=400-4\cdot84-3\cdot84+3(400-4\cdot84)=4\cdot400+(-19)84 $
Moltiplicando per 17 ottengo:
$ 68=68\cdot400+(-19\cdot17)84 $
ecco che una soluzione particolare è $ (-19\cdot 17, 68) $
Allora, sommando le soluzioni dell'omogenea con quella particolare, risulta che tutte le soluzioni della diofantea sono $ S=\{(100h-19\cdot 17,-21h+68):h\in\mathbb{Z}\} $
Le soluzione dell'equazione nelle classi ricavano sostituendo la soluzione generale della diofantea nella diofantea stessa e passando alle classi
$ \overline{84}\overline{x}+\overline{400}\overline{y}=\overline{68} $
$ \overline{84}\cdot\overline{(100h-19\cdot 17)}+\overline{400}\cdot\overline{(-21h+68)}=\overline{68} $
l'addendo con il 400 va a 0 perché sei modulo 400, quindi
$ \overline{84}\cdot\overline{(100h-19\cdot 17)}=\overline{68} $
Fai scorrere $h\in\mathbb{Z}$ finché le soluzioni $\overline{x}$ non ti tornano uguali. Quelle che hai trovato sono le soluzioni della tua equazioni