da Lord K » 04/02/2009, 09:20
Allora, cominciamo con il dire che la congruenza può essere scritta come:
$329x \equiv 224 (455)$
ed ammette soluzione se $gcd(329,455)|224$, calcoliamo quindi questo massimo comune divisore:
$455=329*1+126$
$329=126*2+77$
$126=77*1+49$
$77=49*1+28$
$49=28*1+21$
$28=21*1+7$
$21=7*3$
quindi: $gcd(329,455)=7$ ed anche $7*32 = 224$ allora la congruenza da risolvere è:
$329x \equiv 224 (455)$
che è equivalente a:
$47x \equiv 32 (65)$
da qui rifacciamo l'algoritmo di euclide per arrivare con quello esteso al valore dell'inverso di $47$:
$65=47*1+18$
$47=18*2+11$
$18=11*1+7$
$11=7*1+4$
$7=4*1+3$
$4=3*1+1$
$3=1*3$
Dalla penultima a salire:
$18*47 - 13*65 =1$
ed allora la soluzione è:
$47x \equiv 32 (65)$
$18*47x \equiv 18*32 (65)$
$x \equiv 576 (65)$
$x \equiv 56 (65)$
Tutto chiaro? ^_^
"La realtà è una invenzione di chi ha dimenticato come si sogna!" C.M.
"Le domande non sono mai stupide, esprimono dei nostri dubbi, solo le risposte possono esserlo!" Un saggio.