Congruenze lineari - id di bezout
Stavo risolvendo una congruenza lineare e mi è sorto un dubbio, come trovo l'inverso ad esempio della classe $ [2] $ in $ Z13 $?
Dovrei usare l'id di Bezout ma una volta che la risolvo trovando X' e Y' non so cosa ho ottenuto
Il ragionamento che faccio io è sempre lo stesso:
l'inverso di $ [2] $ in $ Z13 $ (in questo esempio sono in $ Z13 $ quindi $ n=13 $) è quella classe che moltiplicata a $ [2] $ è in congruenza con $ 1 mod 13 $, cioè:
se $ mcd(a,n)=1 $ so che la congruenza ammette soluzioni, quindi posso applicare il teorema e $ aX -= b mod n rArr X -=b*a^-1 mod n $. In questo caso l'inverso di $ [2] mod 13 $ è $ [7] $ perchè $ [2]*[7]=[14]-=[1] mod 13 $, giusto?
Dovrei usare l'id di Bezout ma una volta che la risolvo trovando X' e Y' non so cosa ho ottenuto
Il ragionamento che faccio io è sempre lo stesso:
l'inverso di $ [2] $ in $ Z13 $ (in questo esempio sono in $ Z13 $ quindi $ n=13 $) è quella classe che moltiplicata a $ [2] $ è in congruenza con $ 1 mod 13 $, cioè:
se $ mcd(a,n)=1 $ so che la congruenza ammette soluzioni, quindi posso applicare il teorema e $ aX -= b mod n rArr X -=b*a^-1 mod n $. In questo caso l'inverso di $ [2] mod 13 $ è $ [7] $ perchè $ [2]*[7]=[14]-=[1] mod 13 $, giusto?
Risposte
Il risultato è giusto... però non si capisce come tu lo abbia calcolato!
semplicemente sapendo che se voglio ottenere il risultato $ 1 mod 13 $ partendo da $ [2] $ io ad occhio so che $ [2][7]=[2*7]=[14]=[13+1] $ quindi $ 1mod13 $.. ora che mi confermate che è giusto qualcuno è in grado di spiegarmi come posso calcolarlo alla stessa maniera usando l'identità di Bezout?
Tu devi risolvere l'equazione congruenziale:
\[
2x\equiv1(mod13)
\]
ovvero determinare \(\displaystyle x,k\in\mathbb{Z}\) tali che:
\[
2x-1=13k\\
2x+13k=1
\]
e per il teorema di Bézout, tali interi esistono.
Poiché \(\displaystyle13\) è un numero primo allora hai che \(\displaystyle2x-1\) è divisibile per \(\displaystyle13\)[nota]A priori, può non essere divisibile per \(\displaystyle k\).[/nota] quindi la soluzione è da ricercare tra i multipli dispari di \(\displaystyle13\).
\[
2x\equiv1(mod13)
\]
ovvero determinare \(\displaystyle x,k\in\mathbb{Z}\) tali che:
\[
2x-1=13k\\
2x+13k=1
\]
e per il teorema di Bézout, tali interi esistono.
Poiché \(\displaystyle13\) è un numero primo allora hai che \(\displaystyle2x-1\) è divisibile per \(\displaystyle13\)[nota]A priori, può non essere divisibile per \(\displaystyle k\).[/nota] quindi la soluzione è da ricercare tra i multipli dispari di \(\displaystyle13\).
chiaro.. in altre situazioni bisogna prima semplificare l'equazione dividendo ogni elemento per l'mcd?
In generale bisogna applicare l'algoritmo di Euclide.
Prova a trovare l'inverso di 2317 modulo 4251.
Prova a trovare l'inverso di 2317 modulo 4251.
risolvendo $ X*2317 + Y*4251=1 $ ho trovato che $ 1=732*4251-1343*2317 $, quindi l'inverso è il valore di $ X $, cioè $ -1333+4251*k $.
Ho fatto la controprova usando $ 4251*1-1333 $ che fa $ 2908 $, poi ho moltiplicato questo numero per la classe $ [2317] $ trovando $ 6 737 836 $, e infatti $ 6737836=4251*1585+1 $.
tutto giusto spero...
Ho fatto la controprova usando $ 4251*1-1333 $ che fa $ 2908 $, poi ho moltiplicato questo numero per la classe $ [2317] $ trovando $ 6 737 836 $, e infatti $ 6737836=4251*1585+1 $.
tutto giusto spero...
Giusto. 
fantastico! grazie mille
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo