Esercizio congruenze

[kimy]

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

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

[math]2604 x \equiv 224 mod 455 [/math]

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


grazie

[ciampax]

Poiché hai

[math]MCD(2604,455)=7[/math]

e 7 divide 224, l'equazione ammette soluzioni che sono esattamente 7 non congruenti. Per determinarle tutte, basta usare la formula

[math]x_0+k\cdot\frac{455}{7},\qquad k=0,\ldots,6[/math]

dove

[math]x_0[/math]

è una soluzione possibile. Ora, per determinare questa

[math]x_0[/math]

fai così: poiché 455/7=65 e 65*6=390, dal momento che

[math]x_0+390\leq 455 \Longrightarrow x_0\leq 65[/math]

basta ricercare

[math]0\leq x_0\leq 65[/math]

intero. A questo punto... ti metti a provare tutti questi valori fino a che non ne trovi uno (e ne troverai solo uno, perché?) che va bene, e poi usando la formula di prima ottieni le altre sei soluzioni!

P.S.: giusto per la cronaca, la prima soluzione è 56.