Soluzioni
  • Ciao Giulialg88, ti rispondo subito!

    Risposta di Alpha
  • Cominciamo con la definizione.

    Si dicono equazioni congruenziali le equazioni lineari in una incognita in Zn.

    Queste equazioni, tipicamente, vengono scritte in due modi

    [a]_n[x]_n=[b]_n

    oppure

    ax=b\mbox{ mod}(n)

    Per risolvere questo tipo di equazioni è molto utile conoscere il seguente teorema:

    Teorema: Sia

    ax=b\mbox{ mod }n

    una congruenza lineare modulo n. Allora la congruenza ammette soluzione se e solo se MCD(a,n) divide b.

    In realtà il teorema è un po' più complesso, ma non voglio confonderti troppo.

     

    Esempio:

    Risolviamo la seguente equazione congruenziale:

    16x=6\mbox{ mod} 5

    MCD(16,5)=1, e 1 divide 6. Dunque l'equazione ammette soluzioni. Come trovarle? Dobbiamo cercare quel numero che sia l'inverso di 16 in Z5, in modo da poter moltiplicare a destra e a sinistra per quel numero e ottenere x=qualcosa mod n.

    L'esistenza di tale numero è garantita proprio dal fatto che MCD(16,5)=1 e per l'identità di Bezout, (te la racconto dopo), 1 è esprimibile come combinazione lineare di 16 e 5. Infatti possiamo scrivere

    16=1+3\cdot 5

    Cioè

    16-1=3\cdot 5

    che significa che

    16=1\mbox{ mod }5

    Quindi scrivere 16 è come scrivere 1, detta in modo rigoroso, abbiamo scoperto che in Z5, 16 è l'inverso di se stesso, dunque moltiplicano entrambi i membri dell'equazione per 16 otteniamo

    x=96\mbox{ mod }5

    96 è 1 mod 5, quindi

    x=1\mbox{ mod }5

    Cioè x appartiene alla classe [1]5 ovvero x={1,6,11,16,...}

    Come puoi vedere l'argomento non è semplicissimo, in realtà la questione è prendere cofidenza con queste operazioni sulle classi di resto per riuscire a  trovare l'inverso.

    Identità di Bézout: dati due numeri interi a e b, non entrambi nulli e tali che MCD(a,b)=d, allora esistono x e y tali che ax+by=d. Quindi nel nostro caso si ha

    1\cdot 16-5\cdot 3=1

    Spero di essere stato chiaro, se così non fosse chiedi pure!

    Risposta di Alpha
 
MEDIEGeometriaAlgebra e Aritmetica
SUPERIORIAlgebraGeometriaAnalisiAltro
UNIVERSITÀAnalisiAlgebra LineareAlgebraAltro
EXTRAPilloleWiki
 
Esercizi simili e domande correlate
Domande della categoria Università - Algebra