Equazione congruenziale
Salve,
qualcuno potrebbe spiegarmi come si risolve l'equazione con modulo
16a = -61 (mod 17)
Propongo il mio ragionamento finora:
Si tratta della forma ax=b (mod N) e so che ammette soluzione solo se MCD(a,n) è divisore di b. In questo caso MCD(16,17)=1 quindi ammette una soluzione. Devo trovare l'inverso moltiplicativo di 16 (mod 17) e con il teorema di euclide esteso trovo che 1 è esprimibile come combinazione lineare di 16 e 17 infatti: 1=16(-1)+17(1) quindi 16=1 mod 17
a = -61 mod 17 quindi a=-10
Grazie per l'aiuto.
qualcuno potrebbe spiegarmi come si risolve l'equazione con modulo
16a = -61 (mod 17)
Propongo il mio ragionamento finora:
Si tratta della forma ax=b (mod N) e so che ammette soluzione solo se MCD(a,n) è divisore di b. In questo caso MCD(16,17)=1 quindi ammette una soluzione. Devo trovare l'inverso moltiplicativo di 16 (mod 17) e con il teorema di euclide esteso trovo che 1 è esprimibile come combinazione lineare di 16 e 17 infatti: 1=16(-1)+17(1) quindi 16=1 mod 17
a = -61 mod 17 quindi a=-10
Grazie per l'aiuto.
Risposte
E' giusto, ma si risolve anche in modo immediato: poiche' modulo $17$ hai che $16 \equiv -1$, allora $16a \equiv -a$, e inoltre $-61 \equiv -10$.
Quindi l'equazione e' equivalente a $-a \equiv -10 \mod 17$, cambiando i segni $a \equiv 10 \mod 17$.
Quindi l'equazione e' equivalente a $-a \equiv -10 \mod 17$, cambiando i segni $a \equiv 10 \mod 17$.