Elemento inverso

[lory1290]

Ciao a tutti,
Dunque io ho un problema su questo esercizio:

Si dica (motivando la risposta) se l'elemento b = 33
e un elemento invertibile o un divisore dello zero in Z875. Se l'elemento b e
invertibile, se ne determini l'inverso in Z875.

Per prima cosa procedo controllando che 33 e 875 siano coprimi. L'MCD mi risulta 1 quindi sono coprimi e posso dire che b non è un divisore dello zero ma è invertibile.
Passo quindi a cercare l'elemento inverso di b.

Pongo il problema come una congruenza lineare:
$33x -= 1 (mod 875)$

procedo impostando la seguente equazione in due incognite:
$ 33x + 875Y = 1$
$ MCD(33,875)=1$
quindi 1 divide 875 -> esiste una ed una sola soluzione

con l'algoritmo di euclide ricavo:
$875 = 26 * 33 +17$
$33 = 1 * 17 + 16$
$17 = 1 * 16 + 1$
$16 = 16 * 1 + 0$
Quindi:
$1=17 - 16=....=-53 * 33 + 2 * 875$

A questo punto mi blocco in quanto non riesco a capire quale è la soluzione. Spiego meglio: per quando mi ricordo, essendo in questo caso una soluzione unica, la sol dovrebbe essere -53 ma quando vado a provare:
$33 * -53 -= 874 (mod 875)$

Non so più cosa fare è una giornata che ci sto dietro e non arrivo ad una soluzione...
Aspetto vostre delucidazioni
grazie
lorenzo

[punx]

non ho controllato tutti i calcoli però se non sbaglio il tuo procedimento è giusto....come soluzione hai -53, ma stai ragionando modulo 875 devi trovare un altro rappresentate di -53 in Z875 che è 822(-53+875) se fai i calcoli vedi che è esattamente quello cercato...ti ripeto non ho controllato i passaggi...se sono giusti ecco il risultato

[lory1290]

Grazie per la tempestiva risposta...
dunque hai detto che devo trovare un rappresentate di -53 in Z875. C'è una formula generale per fare ciò? mi spiego meglio...Quando arrivo a trovare le soluzioni dell'equazione basta che faccia x + n ( dove x è la soluzione dell'equazione)?

[punx]

di niente...diciamo di si....praticamente le soluzioni di un'equazione congruenziale sono del tipo x(soluzione particolare)+n*k dove n è il modulo e k varia in Z. Quando ti ho detto di cercare un altro rappresentante volevo intendere quella x tale che 0

Cita

Segnala

[lory1290]

quindi in pratica essendoci sicuramente un solo inverso k darà sempre uno....quindi trovo la sol solo sommando la soluzione particolare al modulo...

[punx]

il problema è proprio questo l'inverso non è unico e ogni y tale che y=x(sempre soluzione particolare )+n*k. ovviamente se la x trovata è negativa, anche quella vale come inversa però devi modificare qualche calcolo...questo è vero poichè Zn è ciclico....

[lory1290]

ma quindi k come lo vario?

[punx]

se x>n allora puoi trovare quel k negativo tale che x+n*k=y ma questa y deve essere 0

Cita

Segnala