esercizio congruenze

[billy80]

ciao a tutti qualcuno mi può spiegare come andrebbe risolto il seguente esercizio?

Determinare l’insieme di tutte le soluzioni intere dell’equazione:


2604 x = 224 mod 455



ho provato ma dopo il teorema di Euclide per trovare il MCD non riesco ad andare avanti


grazie

[Lord K]

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? ^_^

[billy80]

ciao Lord K, grz della disponibilità

avrei un dubbio, come hai trovato il 329 iniziale?
bisogna fare questa "riduzione" per forza?


grazie ancora

[Lord K]

E' il numero a cui è congruente $2604$ modulo $455$. La riduzione non è necessaria, ma rende i conti più semplici.

[billy80]

ok grazie mi è chiaro

un'ultima cosetta nn ho capito il passaggio da

$x \equiv 576 (65)$

a

$x \equiv 56 (65)$

[Lord K]

Sempre per congruenza, hai che:

$576= 8*65 + 56$

da cui la congruenza!

[billy80]

ok, grazie 1000

[billy80]

ok, grazie 1000