Aiuto Esercizi Congruenza
Salve sono nuovo in questo forum e volevo insieme a voi chiedervi se è corretto il mio ragionamento per trovare la congruenza.
Esercizi Congruenza :
1) $-4x \equiv 6 mod 10$
2) $ x \equiv 4^2546 mod 5$.
Svolgiamo la prima Congruenza :
$-4x \equiv 6 mod 10$
Per prima cosa posso dividere tutto per 2 e ottengo :
$-2x \equiv 3 mod 5$
Il mio obbiettivo è di trovare $-2x -6 = 5a$ , mi verrebbe da dire :
$ -2x = 6 + 5a $
$ -x = (6 + 5a)/2 $
$ x = ( -6 - 5a )/2 $
Se pongo $ a = 2 $ ottengo che la $ x = ( -6 - 5*2 )/2 = -16/2 = -4 $
Ottengo che $ x = -4 $
Scrivo le soluzioni $ x = -4 + k*n/d = -4 + k*5 $
Premetto che non sono sicuro perché le congruenze negative non l'ho mai svolte, suggerimenti e consigli sono bene accetti.
Per la seconda :
$ x \equiv 4^2546 mod 5$.
Non so dove cominciare consigli , suggerimenti ? Mi verrebbe da scomporre $4^2546$
Grazie anticipatamente. Nel frattempo provo a fare altri esercizi.
Esercizi Congruenza :
1) $-4x \equiv 6 mod 10$
2) $ x \equiv 4^2546 mod 5$.
Svolgiamo la prima Congruenza :
$-4x \equiv 6 mod 10$
Per prima cosa posso dividere tutto per 2 e ottengo :
$-2x \equiv 3 mod 5$
Il mio obbiettivo è di trovare $-2x -6 = 5a$ , mi verrebbe da dire :
$ -2x = 6 + 5a $
$ -x = (6 + 5a)/2 $
$ x = ( -6 - 5a )/2 $
Se pongo $ a = 2 $ ottengo che la $ x = ( -6 - 5*2 )/2 = -16/2 = -4 $
Ottengo che $ x = -4 $
Scrivo le soluzioni $ x = -4 + k*n/d = -4 + k*5 $
Premetto che non sono sicuro perché le congruenze negative non l'ho mai svolte, suggerimenti e consigli sono bene accetti.
Per la seconda :
$ x \equiv 4^2546 mod 5$.
Non so dove cominciare consigli , suggerimenti ? Mi verrebbe da scomporre $4^2546$
Grazie anticipatamente. Nel frattempo provo a fare altri esercizi.
Risposte
per la prima
più semplicemente hai che $-4x-=6(mod10)$
$-4=6(mod10) =>6x-=6(mod10)$
ora $(4,10)=2$ quindi $3x-=3(mod5) => x-=1(mod5)$ perché $3$ è invertibile e ha inverso $2$
quindi le due soluzioni modulo 10 sono $[1]_10$ e $[6]_10$
per il b) un piccolo hint,
qual'è il più piccolo $n>0$ tale che $4^n-=1(mod5)$?
più semplicemente hai che $-4x-=6(mod10)$
$-4=6(mod10) =>6x-=6(mod10)$
ora $(4,10)=2$ quindi $3x-=3(mod5) => x-=1(mod5)$ perché $3$ è invertibile e ha inverso $2$
quindi le due soluzioni modulo 10 sono $[1]_10$ e $[6]_10$
per il b) un piccolo hint,
qual'è il più piccolo $n>0$ tale che $4^n-=1(mod5)$?
Io avevo ragionato anche in questa maniera ora mi studio il tuo passaggio :
$−4x ≡ 6 mod 10$
$-4x -6 = 10a$
$-x = (a*10 +6) / 4$
$x = -4$ preso $a=1$
$x = -4 $
$x = -4 + k5 $=>
$k = 0$
$ x = -4$
( -4 non fà parte tra 0
$k = 1$
$x = 1$
( 1<10 si vero )
$ k = 2$
$ x = -4 + 5*(2)=6$
( 6<10 si vero )
$ k = 3$
$ x = -4 + 5*(3)=11$
( 11<10 falso )
Per la seconda mi viene da dire al tuo suggerimento $ 4^4 -= 1 mod 5 $Non sono sicuro.
P.s. Sai dove posso studiare bene le congruenze?! Grazie mille Kashaman.
$−4x ≡ 6 mod 10$
$-4x -6 = 10a$
$-x = (a*10 +6) / 4$
$x = -4$ preso $a=1$
$x = -4 $
$x = -4 + k5 $=>
$k = 0$
$ x = -4$
( -4 non fà parte tra 0
$k = 1$
$x = 1$
( 1<10 si vero )
$ k = 2$
$ x = -4 + 5*(2)=6$
( 6<10 si vero )
$ k = 3$
$ x = -4 + 5*(3)=11$
( 11<10 falso )
Per la seconda mi viene da dire al tuo suggerimento $ 4^4 -= 1 mod 5 $Non sono sicuro.
P.s. Sai dove posso studiare bene le congruenze?! Grazie mille Kashaman.
che libro stai usando?
comunque, per essere proprio proprio precisi.
Una congruenza del tipo $ax-=b(modn)$ o la risolvi pensandola in $ZZ_n$ (un poco come fatto io)
oppure
con bezout...
per l'altro punto è parzialmente vero.
sicuramente $4$ va bene , ma è il più piccolo?
sbircia alla fine
comunque, per essere proprio proprio precisi.
Una congruenza del tipo $ax-=b(modn)$ o la risolvi pensandola in $ZZ_n$ (un poco come fatto io)
oppure
con bezout...
per l'altro punto è parzialmente vero.
sicuramente $4$ va bene , ma è il più piccolo?
sbircia alla fine
Il libro che sto studiando è : " Elementi di Algebra e Matematica Discreta " Editore Accademica .
Grazie mille dell'aiuto che mi stai dando .
Giusto :
$ 4^2 = 16 $
$ 4^2 -= 1 mod 5 $
$ 16 - 1 = 15 $ che è un numero divisibile per $5$ perché $ 15/5 = 3 $
Grazie mille dell'aiuto che mi stai dando .
Giusto :
$ 4^2 = 16 $
$ 4^2 -= 1 mod 5 $
$ 16 - 1 = 15 $ che è un numero divisibile per $5$ perché $ 15/5 = 3 $
Per le congruenze cerca di vederti bene come è definita la relazione di congruenza e le relative implicazioni, poi i teoremi ad essa legati (quelli che ti aiutano a risolvere questi esercizi) ne sono una conseguenza logica.
In rete dovresti trovare gli appunti, liberamente scaricabili, del prof. Campanella (sono in formato pdf), che trovo siano veramente ben fatti.
In rete dovresti trovare gli appunti, liberamente scaricabili, del prof. Campanella (sono in formato pdf), che trovo siano veramente ben fatti.
no la cosa che mi riferivo è questa.
$x-=4^(2546)-=(4^2)^1723-=1^1723-=1(mod5)$
Conosci la nozione di
ordine di un elemento ?
Il th di eulero e quello di fermat?
$x-=4^(2546)-=(4^2)^1723-=1^1723-=1(mod5)$
Conosci la nozione di
ordine di un elemento ?
Il th di eulero e quello di fermat?
Penso che mi conviene rifare il ripasso o ristudio che c'è qualcosa che mi sfugge... Mi vado a ristudiare e poi torno..
Grazie Kashaman .
Grazie Kashaman .
Riepilogo della Teoria in mio Possesso
Identità di Bézout :
Il massimo comun divisore $d$ fra due interi non nulli $a$ e $b$ si può scrivere nella forma $d = a*h + b*k$ ,
$ h,k in ZZ$ tale identità prende il nome di Identità di Bézout.
I coefficienti $h$ e $k$ dell'identità di Bézout possono essere calcolati al modo seguente : si esprime $r_n$ in funzione di $r_(n-2) - r_(n-1)$ , si esprime poi $r_(n-1)$ in funzione di $r_(n-2) $ e $r_(n-3) $ e si sostituisce questa espressione nella precedente ottenendo $r_n$ in funzione di $r_(n-2) $ e $r_(n-3) $ . Procedendo si ottiene, alla fine , $r_n$ in funzione di $a$ e $b$
Esempio : Se $a=652$ e $b=38$ risulta:
$ 652 = 38*17+6 $
$ 38 = 6*6 + 2$
$ 6 = 2*3 $
e pertanto risulta $(652,38) = 2$, $d=2$ inoltre riscriviamo i $r_(1)$ e $r_(2)$
$2=38+6*(-6)$
$6=652 + 38*(-17)$
Segue che :
$ 2=38 + (-6)*[652 + 38*(-17) ] $
$ 2= 38*(1) + 652*(-6) + 38*(102) $
$ 2= 38*(1+102) + 653*(-6)$
$ 2= 38*(103) + 653*(-6) $
Quindi ora se riscriviamo l'Identità di Bézout $d=a*h + b*k$ sono, in questo caso $h=103$ e $k=-6$
Algoritmo euclideo delle divisioni successive :
Il massimo coum divisore fra due interi non nulli $a$ e $b$ è l'ultimo resto non nullo della seguente serie di divisioni successive :
$ a = b*q + r$
$ b = r*q_1 +r_1$
$ r = r_1*q_2 + r_2 $
$ ............... $
$ r_(n-2) = r_(n-1)*q_(n) + r_n $
$ r_(n-1) = r_(n)*q_(n+1) $
Ovvero $(a,b) = r_n$
Congruenze
Se $ a*c-= b*c mod m$ e $d= (c,m)$, $c= dc^{\prime}$, $m=dm^{\prime}$, $m^{\prime}=m/d$, allora $a-=b mod m^{\prime}$. In particolare, se $(c,m) = 1$, allora $a-=b mod m$.
Esempio :
$ 2*6 -= 7*6 mod 15 $
Non possiamo semplificare per $6$ perché $ 2 -= 7 mod 15 $ è sbagliata.
Applichiamo la definizione precedente, ed otteniamo $d=(6,15)= 3$ e pertanto otteniamo :
$ 2 -= 7 mod 5$ che è vera
Il piccolo Teorema di Fermat
Il piccolo teorema di Fermat dice che se $p$ è un numero primo, allora $AA a in ZZ$ :
$a^p -= a mod p$
Questo significa che se si prende un qualunque numero $a$ maggiore di 1, lo si moltiplica per se stesso $p$ volte e si sottrae $a$, il risultato è divisibile per $p$. È spesso espresso nella forma equivalente: se $p$ è primo e $a$ è un intero coprimo rispetto a $p$, allora:
$a^(p-1)-= 1 mod p$
Il Teorema di Eulero
Per ogni $a,n in ZZ$ tali che $(a,n)=1$ risulta :
$a^(\varphi(n)) -= 1 mod n$
Identità di Bézout :
Il massimo comun divisore $d$ fra due interi non nulli $a$ e $b$ si può scrivere nella forma $d = a*h + b*k$ ,
$ h,k in ZZ$ tale identità prende il nome di Identità di Bézout.
I coefficienti $h$ e $k$ dell'identità di Bézout possono essere calcolati al modo seguente : si esprime $r_n$ in funzione di $r_(n-2) - r_(n-1)$ , si esprime poi $r_(n-1)$ in funzione di $r_(n-2) $ e $r_(n-3) $ e si sostituisce questa espressione nella precedente ottenendo $r_n$ in funzione di $r_(n-2) $ e $r_(n-3) $ . Procedendo si ottiene, alla fine , $r_n$ in funzione di $a$ e $b$
Esempio : Se $a=652$ e $b=38$ risulta:
$ 652 = 38*17+6 $
$ 38 = 6*6 + 2$
$ 6 = 2*3 $
e pertanto risulta $(652,38) = 2$, $d=2$ inoltre riscriviamo i $r_(1)$ e $r_(2)$
$2=38+6*(-6)$
$6=652 + 38*(-17)$
Segue che :
$ 2=38 + (-6)*[652 + 38*(-17) ] $
$ 2= 38*(1) + 652*(-6) + 38*(102) $
$ 2= 38*(1+102) + 653*(-6)$
$ 2= 38*(103) + 653*(-6) $
Quindi ora se riscriviamo l'Identità di Bézout $d=a*h + b*k$ sono, in questo caso $h=103$ e $k=-6$
Algoritmo euclideo delle divisioni successive :
Il massimo coum divisore fra due interi non nulli $a$ e $b$ è l'ultimo resto non nullo della seguente serie di divisioni successive :
$ a = b*q + r$
$ b = r*q_1 +r_1$
$ r = r_1*q_2 + r_2 $
$ ............... $
$ r_(n-2) = r_(n-1)*q_(n) + r_n $
$ r_(n-1) = r_(n)*q_(n+1) $
Ovvero $(a,b) = r_n$
Congruenze
Se $ a*c-= b*c mod m$ e $d= (c,m)$, $c= dc^{\prime}$, $m=dm^{\prime}$, $m^{\prime}=m/d$, allora $a-=b mod m^{\prime}$. In particolare, se $(c,m) = 1$, allora $a-=b mod m$.
Esempio :
$ 2*6 -= 7*6 mod 15 $
Non possiamo semplificare per $6$ perché $ 2 -= 7 mod 15 $ è sbagliata.
Applichiamo la definizione precedente, ed otteniamo $d=(6,15)= 3$ e pertanto otteniamo :
$ 2 -= 7 mod 5$ che è vera
Il piccolo Teorema di Fermat
Il piccolo teorema di Fermat dice che se $p$ è un numero primo, allora $AA a in ZZ$ :
$a^p -= a mod p$
Questo significa che se si prende un qualunque numero $a$ maggiore di 1, lo si moltiplica per se stesso $p$ volte e si sottrae $a$, il risultato è divisibile per $p$. È spesso espresso nella forma equivalente: se $p$ è primo e $a$ è un intero coprimo rispetto a $p$, allora:
$a^(p-1)-= 1 mod p$
Il Teorema di Eulero
Per ogni $a,n in ZZ$ tali che $(a,n)=1$ risulta :
$a^(\varphi(n)) -= 1 mod n$
piccole note. Allora il Lemma di Bezout , ci dice che $d=(a,b)$ esiste e può essere espresso come combinazione lineare di $a,b$. Cioè ad esempio se $(4,3)=1$ posso scrivere
$4x+3y=1$ ponendo ad esempio $y=-1 ^^ x=1$ in genere $x,y$ non sono univocamente determinati.
In $ZZ_n$ la regola che
$ab-=ac(modn) => b-=c(modn)$ dice che se $(a,n)=1$ $a$ è cancellabile.
Ciò è vero perché in un anello commutativo unitario le nozioni di invertibilità e cancellabilità coincidono.
quindi si può fare quella cosa se e solo se $a$ è invertibile. (in particolare se $n$ è primo vale per ogni a con a diverso da zero, sai dire il perché?)
Passiamo agli altri due teoremi, importantissimi.
Il teorema di Eulero e quello di fermat. Dimmi, al corso, li avete dimostrati?
$4x+3y=1$ ponendo ad esempio $y=-1 ^^ x=1$ in genere $x,y$ non sono univocamente determinati.
In $ZZ_n$ la regola che
$ab-=ac(modn) => b-=c(modn)$ dice che se $(a,n)=1$ $a$ è cancellabile.
Ciò è vero perché in un anello commutativo unitario le nozioni di invertibilità e cancellabilità coincidono.
quindi si può fare quella cosa se e solo se $a$ è invertibile. (in particolare se $n$ è primo vale per ogni a con a diverso da zero, sai dire il perché?)
Passiamo agli altri due teoremi, importantissimi.
Il teorema di Eulero e quello di fermat. Dimmi, al corso, li avete dimostrati?
Ti spiego la mia situazione Universitaria: Sono uno studente lavoratore di Ingengeria Informatica a Roma Tre sono del vecchio ordinamento 509 , quindi non ho seguito il corso, mi devo preparare per l'esame di Combinatoria e Matematica Discreta mi sto preparando da solo studiando sui i libri e cercando di fare gli esercizi sul sito che sono veramente pochi esempio link esercizi : http://ricerca.mat.uniroma3.it/users/merola/madi/interi.pdf sito del corso http://www.dia.uniroma3.it/~dispense/merola/comb/ .
Ritornando alle domande penso che la dimostrazione l'abbia fatta.
P.S. Se ha un buon libro di esercizi e che spiega bene i passaggi me lo vado a comprare.
Adesso cerco di studiare e posto la dimostrazione .
Grazie ancora per tutto quello che fai.
Esercizio Semplice Congruenza :
Esercizio :
$7x-=3 (mod 10)$
$M.C.D.(7,10) = 1$
$10 = 7*1 + 3$
$7 = 3*2 + 1$
$3 = 1*3 + 0$
Possiamo riscrivere i resti :
$3 = 10 + 7(-1)$
$1 = 7 + 3(-2)$
$1 = 7 + (-2)*( 10 + 7(-1) ) =$
$1 = 7 + 10(-2) + 7(2) = $
$1 = 7(3) + 10(-2)$
Ottenuto $1$ possiamo ora sostituirlo nella forma $3 = 3*1$
$3 = 3*1 =$
$3 = 3*( 7(3) + 10(-2) ) =$
$3 = 7(9) + 10(-6) =$
Ora la metto nella forma $7x - 3 = 10y$
$7(9) - 3 = 10(6)$
Ottenendo che $x= 9$
Scriviamo tutte le possibili soluzioni $x = 9 + k*n/d$ => $9 + k*10/3 $=>
sapendo che la $x$ deve essere compresa tra $0
Questo esercizio come va come ragionamento?!
Ritornando alle domande penso che la dimostrazione l'abbia fatta.
P.S. Se ha un buon libro di esercizi e che spiega bene i passaggi me lo vado a comprare.
Adesso cerco di studiare e posto la dimostrazione .
Grazie ancora per tutto quello che fai.
Esercizio Semplice Congruenza :
Esercizio :
$7x-=3 (mod 10)$
$M.C.D.(7,10) = 1$
$10 = 7*1 + 3$
$7 = 3*2 + 1$
$3 = 1*3 + 0$
Possiamo riscrivere i resti :
$3 = 10 + 7(-1)$
$1 = 7 + 3(-2)$
$1 = 7 + (-2)*( 10 + 7(-1) ) =$
$1 = 7 + 10(-2) + 7(2) = $
$1 = 7(3) + 10(-2)$
Ottenuto $1$ possiamo ora sostituirlo nella forma $3 = 3*1$
$3 = 3*1 =$
$3 = 3*( 7(3) + 10(-2) ) =$
$3 = 7(9) + 10(-6) =$
Ora la metto nella forma $7x - 3 = 10y$
$7(9) - 3 = 10(6)$
Ottenendo che $x= 9$
Scriviamo tutte le possibili soluzioni $x = 9 + k*n/d$ => $9 + k*10/3 $=>
sapendo che la $x$ deve essere compresa tra $0
Questo esercizio come va come ragionamento?!
va bene, a me sembra corretto.
Comunque, come ti ho già detto si può fare tutto più velocemente senza passare per Bezout. E' rognosa come cosa!
puoi pensare le congruenze come semplici equazioni in $ZZ_n$
cioé se hai $ax-=b(modn)$ con $(a,n)=d|b$ che diventa supponiamo così
$a'x-=b'(modn')$ quest'ultima puoi pensarla come un'equazione in $ZZ_n$ del tipo $[a']_nx= [b']_n$ e comportarti più o meno come una equazione "normale.
Mi spiego,
Il tuo obbiettivo diventa di trovare un inverso di $[a']_n$. Tale inverso esiste se e solo se $(a',n)=1$ cioè se $a$ ed $n$ sono relativamente primi.
Denotiamo con $[a'^-1]_n$ tale inverso.
allora
moltiplicando a sinistra e a destra hai che $[x]_n=[a'^(-1)b']_n$ e che quindi $x_0= a'^(-1)b$ è la tua soluzione particolare... le altre sono della forma $x_1=x_0+n/d$ , $x_2=x_0+2n/d$ , ......,$x_k= x_0+(d-1)n/d$
Forse con un esempio ti aiuto a capire meglio.
consideriamo
$3x-=2(mod5)$
ho che $(3,5)=1$ quindi è compatibile.
è già ridotta e ora mi preoccupo ti trovare un inverso di $[3]_5$. come?
devo trovare un $n in ZZ$ tale che $[3n]_5=[1]_5$ e cioè $3n-=1(mod5) <=> 3n=1+5k$
scelto $k=1$ ho che $3n=6 => n=2$ quindi un inverso aritmetico di tre è due.
quindi
$2*3x-=2*2-=4(mod5) => 1*x=x-=4(mod5)$ ove $x=4$ è l'unica soluzione modulo cinque.
sono stato chiaro?
comunque,
http://www.dm.uniba.it/~barile/Rete4/al ... zione8.pdf <--guarda qui e [url http://www.dm.uniba.it/~barile/Rete4/al ... zione9.pdf <-anche qui
ci sta la teoria ed è fatta molto bene, cerca di comprendere teoremi e dimostrazioni.
leggendo il programma,
posso consigliarti un buon libro di algebra.
Ti consiglierei il "Piacentini - cattaneo - elementi di algebra un approccio algoritmico". A me piace, lo sto usando tutt'ora, molto intuitivo e lo considero abbastanza chiaro.
Ciao
comunque di niente , è un piacere
Comunque, come ti ho già detto si può fare tutto più velocemente senza passare per Bezout. E' rognosa come cosa!
puoi pensare le congruenze come semplici equazioni in $ZZ_n$
cioé se hai $ax-=b(modn)$ con $(a,n)=d|b$ che diventa supponiamo così
$a'x-=b'(modn')$ quest'ultima puoi pensarla come un'equazione in $ZZ_n$ del tipo $[a']_nx= [b']_n$ e comportarti più o meno come una equazione "normale.
Mi spiego,
Il tuo obbiettivo diventa di trovare un inverso di $[a']_n$. Tale inverso esiste se e solo se $(a',n)=1$ cioè se $a$ ed $n$ sono relativamente primi.
Denotiamo con $[a'^-1]_n$ tale inverso.
allora
moltiplicando a sinistra e a destra hai che $[x]_n=[a'^(-1)b']_n$ e che quindi $x_0= a'^(-1)b$ è la tua soluzione particolare... le altre sono della forma $x_1=x_0+n/d$ , $x_2=x_0+2n/d$ , ......,$x_k= x_0+(d-1)n/d$
Forse con un esempio ti aiuto a capire meglio.
consideriamo
$3x-=2(mod5)$
ho che $(3,5)=1$ quindi è compatibile.
è già ridotta e ora mi preoccupo ti trovare un inverso di $[3]_5$. come?
devo trovare un $n in ZZ$ tale che $[3n]_5=[1]_5$ e cioè $3n-=1(mod5) <=> 3n=1+5k$
scelto $k=1$ ho che $3n=6 => n=2$ quindi un inverso aritmetico di tre è due.
quindi
$2*3x-=2*2-=4(mod5) => 1*x=x-=4(mod5)$ ove $x=4$ è l'unica soluzione modulo cinque.
sono stato chiaro?
comunque,
http://www.dm.uniba.it/~barile/Rete4/al ... zione8.pdf <--guarda qui e [url http://www.dm.uniba.it/~barile/Rete4/al ... zione9.pdf <-anche qui
ci sta la teoria ed è fatta molto bene, cerca di comprendere teoremi e dimostrazioni.
leggendo il programma,
posso consigliarti un buon libro di algebra.
Ti consiglierei il "Piacentini - cattaneo - elementi di algebra un approccio algoritmico". A me piace, lo sto usando tutt'ora, molto intuitivo e lo considero abbastanza chiaro.
Ciao
comunque di niente , è un piacere
Grazie delle dispense sto notando che sono spiegate bene e sto riuscendo a capire molte cose.
Volevo chiederti mi potresti spiegare questo passaggio :
$rArr 1*x=x≡4(mod5)$
Sono riuscito a capire come trovarmi l'inverso $[a'^(-1)]_n$ e dopo che l'ho trovato lo devo moltiplicare sia a sinistra che a destra :
$3x-=2 (mod5)$ cosi ottenendo $2*3x-=2*2-=4(mod5)$
Ma non capisco questa cosa che segue $ rArr 1*x=x≡4(mod5)$ non ti potevi bloccare e dire subito che $x_(0)=a'^(-1)*b = 2*2=4$
Quello che ho capito per arrivare ad ottenere l'inverso : $[a'^(-1)]_n$
Prima cosa io la congruenza $3x-=2 (mod5)$ la vedo nella versione $ZZ_5 = [a']_5 x=[b']_5$
come dici il mio obbiettivo è di trovare $[a'^(-1)]_n$ alla condizione che esiste $(a',n)=1$
Prima cosa mi calcolo il $M.C.D.(3,5)=1$ rientro nella condizione.
Passo ora a trovare quella $n in ZZ$ tale che $[3*n]_5 = [1]_5$
(Se ho capito bene l'1 è dovuto dalla condizione che il $M.C.D.(3,5)=1$ )
Questo $[3*n]_5 = [1]_5$ lo possiamo vedere come $[a']_5n = [b']_5$ è uguale a dire $a'n-=b' (mod 5)=3n-=1 (mod 5)$
Risolvendo ottengo : $a'n = b' + 5k= 3n = 1 + 5k$ ora devo trovare il $k in ZZ$ opportuno per risolvere l'equazione .
Provo $k=0$ ottengo $3n = 1 $ falso non va bene.
Provo $k=1$ ottengo $3n = 1 + 5*1$ segue che $3n = 6 $ ora mi calcolo $n=6/3=2$ va bene e ottengo $n=2$
Ora posso concludere dicendo che $x_0 = a'^(-1)b = 2 * 2 = 4$
Ammette solo una soluzione perché essendo $d=1$ si ha solo la soluzione $x = x_0 + (d-1)n/d = 4 + (1-1)25/1 = 4$ .
Chiedo scusa se ti ho scritto tutti i passaggi ma è quello che ho capito io e ho cercato di spiegarti come l'ho capito io.
Se gentilmente mi mandi due esercizi dove ti posto i passaggi cosi per capire se ho capito bene.
Grazie Mille.
Volevo chiederti mi potresti spiegare questo passaggio :
$rArr 1*x=x≡4(mod5)$
Sono riuscito a capire come trovarmi l'inverso $[a'^(-1)]_n$ e dopo che l'ho trovato lo devo moltiplicare sia a sinistra che a destra :
$3x-=2 (mod5)$ cosi ottenendo $2*3x-=2*2-=4(mod5)$
Ma non capisco questa cosa che segue $ rArr 1*x=x≡4(mod5)$ non ti potevi bloccare e dire subito che $x_(0)=a'^(-1)*b = 2*2=4$
Quello che ho capito per arrivare ad ottenere l'inverso : $[a'^(-1)]_n$
Prima cosa io la congruenza $3x-=2 (mod5)$ la vedo nella versione $ZZ_5 = [a']_5 x=[b']_5$
come dici il mio obbiettivo è di trovare $[a'^(-1)]_n$ alla condizione che esiste $(a',n)=1$
Prima cosa mi calcolo il $M.C.D.(3,5)=1$ rientro nella condizione.
Passo ora a trovare quella $n in ZZ$ tale che $[3*n]_5 = [1]_5$
(Se ho capito bene l'1 è dovuto dalla condizione che il $M.C.D.(3,5)=1$ )
Questo $[3*n]_5 = [1]_5$ lo possiamo vedere come $[a']_5n = [b']_5$ è uguale a dire $a'n-=b' (mod 5)=3n-=1 (mod 5)$
Risolvendo ottengo : $a'n = b' + 5k= 3n = 1 + 5k$ ora devo trovare il $k in ZZ$ opportuno per risolvere l'equazione .
Provo $k=0$ ottengo $3n = 1 $ falso non va bene.
Provo $k=1$ ottengo $3n = 1 + 5*1$ segue che $3n = 6 $ ora mi calcolo $n=6/3=2$ va bene e ottengo $n=2$
Ora posso concludere dicendo che $x_0 = a'^(-1)b = 2 * 2 = 4$
Ammette solo una soluzione perché essendo $d=1$ si ha solo la soluzione $x = x_0 + (d-1)n/d = 4 + (1-1)25/1 = 4$ .
Chiedo scusa se ti ho scritto tutti i passaggi ma è quello che ho capito io e ho cercato di spiegarti come l'ho capito io.
Se gentilmente mi mandi due esercizi dove ti posto i passaggi cosi per capire se ho capito bene.
Grazie Mille.
"Davide1986":
$rArr 1*x=x≡4(mod5)$
Sono riuscito a capire come trovarmi l'inverso $[a'^(-1)]_n$ e dopo che l'ho trovato lo devo moltiplicare sia a sinistra che a destra :
$3x-=2 (mod5)$ cosi ottenendo $2*3x-=2*2-=4(mod5)$
Ma non capisco questa cosa che segue $ rArr 1*x=x≡4(mod5)$ non ti potevi bloccare e dire subito che $x_(0)=a'^(-1)*b = 2*2=4$
Allora, quello che ho fatto all'inizio è un po un'impostazione generale.
Lo schema per risolvere una congruenza è questo alla fine dei conti :
1) riduci i coefficienti a modulo $m$. esempio (se hai $a=405$ in $ZZ_2$ diventa $a=1$
2) poi dividi tutto per $(a,n)$ ( ovviamente, accertandoti se si può fare!)
2) ci si trova un inverso aritmetico di $a'$, e cioè un $m in ZZ$ tale che $a'm-=1(modn)$ (1)
(il perché c'è l'uno è semplice! non dipende strettamente da $(a',n)=1$ , o meglio, quella è condizione necessaria e sufficiente affinché a' sia invertibile.
$m$ è semplicemente un numero che moltiplicato per $a$ ti da $1$ in $ZZ_n$ (piccola nota, ne esistono infiniti!!)
e si trova risolvendo la $(1)$ oppure con Bezout. (la 1) l'ho sempre fatta un po a tentativi, quando era possibile , sostituendo un po di valori a $k$.
3) moltiplichiamo per $m$ ambo le parti e otteniamo il nostro insieme di soluzioni.
Prima cosa mi calcolo il $M.C.D.(3,5)=1$ rientro nella condizione.
Passo ora a trovare quella $n in ZZ$ tale che $[3*n]_5 = [1]_5$
(Se ho capito bene l'1 è dovuto dalla condizione che il $M.C.D.(3,5)=1$ )
Questo $[3*n]_5 = [1]_5$ lo possiamo vedere come $[a']_5n = [b']_5$ è uguale a dire $a'n-=b' (mod 5)=3n-=1 (mod 5)$
Risolvendo ottengo : $a'n = b' + 5k= 3n = 1 + 5k$ ora devo trovare il $k in ZZ$ opportuno per risolvere l'equazione .
Provo $k=0$ ottengo $3n = 1 $ falso non va bene.
Provo $k=1$ ottengo $3n = 1 + 5*1$ segue che $3n = 6 $ ora mi calcolo $n=6/3=2$ va bene e ottengo $n=2$
esatto.
Ora posso concludere dicendo che $x_0 = a'^(-1)b = 2 * 2 = 4$
Ammette solo una soluzione perché essendo $d=1$ si ha solo la soluzione $x = x_0 + (d-1)n/d = 4 + (1-1)25/1 = 4$ .
Imprecisa , ammette un'unica soluzione modulo 5. In $ZZ$ ne sono infinite.
Chiedo scusa se ti ho scritto tutti i passaggi ma è quello che ho capito io e ho cercato di spiegarti come l'ho capito io.
Se gentilmente mi mandi due esercizi dove ti posto i passaggi cosi per capire se ho capito bene.
tranquillo ci vuole tempo, anche io mesi fa ci ho messo un sacco a capirle!
Prova a risolvere queste
1) $2078539217x-=1(mod2)$
2) 7x-=2(mod14)
3) 5x-=25(mod60)
Per quanto riguarda l'elemento inverso, in generale in un anello [tex](A,+,*)[/tex] un elemento [tex]a \in A[/tex] si dice invertibile se esiste un [tex]x \in A[/tex] tale che [tex]a*x=x*a=1[/tex], dove [tex]x=a^{-1}[/tex].
"GundamRX91":
Per quanto riguarda l'elemento inverso, in generale in un anello [tex](A,+,*)[/tex] un elemento [tex]a \in A[/tex] si dice invertibile se esiste un [tex]x \in A[/tex] tale che [tex]a*x=x*a=1[/tex], dove [tex]x=a^{-1}[/tex].
Se proprio vogliamo essere formali
adattiamo a $ZZ_n$ questa definizione.
teorema
Sia $a in ZZ$ ,
Allora $[a]_n$ è invertibile in $ZZ_n$ se e solo se $(a,n)=1$
dim
$=>$ supponiamo che $[a]_n$ sia invertibile allora (per la definizione di Gundam) , esiste $[m]_n in ZZ_n$ tale che
$[am]_n=[1]_n$ e cioè un $m in ZZ$ verificante la congruenza lineare $am-=1(modn)$
sia ora $d=(a,n)$, poiché $d|1 => d=1$ . Ciò prova che $[a]_n $ invertibile $=> (a,n)=1$
$\leftarrow$
Per ipotesi $(a,n)=1$ quindi per il lemma di Bezout
$EE s, t in ZZ : as+nt=1 <=> as-1=n(-t) <=> n|as-1<=> as-=1(modn)$
ciò prova che se $a,n$ sono relativamente primi allora $[a]$ è invertibile.
Grazie degli esercizi e dell'aiuto grande che mi stai dando .
Prendiamo la prima :
$2078539217x-=1(mod2)$
Per prima cosa mi viene da calcolare il $d=MCD(2078539217,2)=1$ , si vede subito ad occhio, un numero dispari e un numero pari da come risultato $1$ .
Il numero $2078539217$ lo posso leggere come $2*10^8+7*10^7+8*10^6+5*10^5+3*10^4+9*10^3+2*10^2+1*10^1+7*10^0$ ma penso che questo strada non mi aiuta in e non mi porta da nessuna parte.
Riparto con il ragionamento , obbiettivo trovare l'inverso di $[2078539217]_2$ quindi devo procedere :
$[2078539217*n]_2 = [1]_2 $
Sapendo che $[a']_2 n = [b']_2$ che è uguale a dire $2078539217n -= 1 (mod 2)$
Si risolve e otteniamo che $2078539217n = 1 + 2k $ ora devo trova $k in ZZ$ .
$2078539217n = 1 + 1039269608*2$ se prendiamo come $k=1039269608$ cosi ottengo che $n=1$
Adesso so che l'inverso di $[2078539217*n]_2$ è $[1]_2$
Adesso mi calcolo $x_0 = a'^-1b= 1*1=1$
Posso concludere dicendo che la soluzione modulo $2$ è $x=x_0+(d-1)n/d = 1 + (1-1)2/1 = 1+0= 1$
In conclusione abbiamo che $x=x_0=1$ la soluzione in modulo $2$
Esercizio Secondo :
$7x-=2(mod14)$
Primo passaggio mi trovo il $M.C.D.(7,14)=7$
14 = 2*7
7 = 1*7
Ora verifico se $d$ è divisibile per $b$ in questo caso il $7$ non divide $2$ quindi non ammette soluzioni.
Esercizio Terzo:
$5x-=25(mod60)$
Già ad occhio si vede che si può dividere per $5$ e quindi semplificare ed ottenere :
$x -= 5 (mod 12)$
Ora mi calcolo il $M.C.D.(1,12)=1$ .
Ricordandomi che $ax-b = kn$ , $ x-5=12k $ , $ x = 12k + 5$ , adesso devo scegliere opportuno $k in ZZ$ .
Prendendo $k=1$ ed ottengo $x_1 = 5+12=17$
Prendiamo la prima :
$2078539217x-=1(mod2)$
Per prima cosa mi viene da calcolare il $d=MCD(2078539217,2)=1$ , si vede subito ad occhio, un numero dispari e un numero pari da come risultato $1$ .
Il numero $2078539217$ lo posso leggere come $2*10^8+7*10^7+8*10^6+5*10^5+3*10^4+9*10^3+2*10^2+1*10^1+7*10^0$ ma penso che questo strada non mi aiuta in e non mi porta da nessuna parte.
Riparto con il ragionamento , obbiettivo trovare l'inverso di $[2078539217]_2$ quindi devo procedere :
$[2078539217*n]_2 = [1]_2 $
Sapendo che $[a']_2 n = [b']_2$ che è uguale a dire $2078539217n -= 1 (mod 2)$
Si risolve e otteniamo che $2078539217n = 1 + 2k $ ora devo trova $k in ZZ$ .
$2078539217n = 1 + 1039269608*2$ se prendiamo come $k=1039269608$ cosi ottengo che $n=1$
Adesso so che l'inverso di $[2078539217*n]_2$ è $[1]_2$
Adesso mi calcolo $x_0 = a'^-1b= 1*1=1$
Posso concludere dicendo che la soluzione modulo $2$ è $x=x_0+(d-1)n/d = 1 + (1-1)2/1 = 1+0= 1$
In conclusione abbiamo che $x=x_0=1$ la soluzione in modulo $2$
Esercizio Secondo :
$7x-=2(mod14)$
Primo passaggio mi trovo il $M.C.D.(7,14)=7$
14 = 2*7
7 = 1*7
Ora verifico se $d$ è divisibile per $b$ in questo caso il $7$ non divide $2$ quindi non ammette soluzioni.
Esercizio Terzo:
$5x-=25(mod60)$
Già ad occhio si vede che si può dividere per $5$ e quindi semplificare ed ottenere :
$x -= 5 (mod 12)$
Ora mi calcolo il $M.C.D.(1,12)=1$ .
Ricordandomi che $ax-b = kn$ , $ x-5=12k $ , $ x = 12k + 5$ , adesso devo scegliere opportuno $k in ZZ$ .
Prendendo $k=1$ ed ottengo $x_1 = 5+12=17$
il primo è semplice. Basta sapere la definizione di classe di congruenza.
Tu sai che $ZZ_2={[0]_2,[1]_2}$
classe zero è l'insieme dei numeri pari, quella di classe 1 di quelli dispari . (i pari danno resto zero se divisi per 2, i dispari 1).
Quindi quel numero è dispari è quindi è congruo a uno modulo 2. pertanto quindi l'unica soluzione modulo 2. è proprio 1.
il due va bene. bravo.
il 3 è parzialmente corretto
$x-=5(mod12)$ è già ridotta e compatibile, puoi vederla come $x=5+12k$
una soluzione particolare è $x_0=5$ (unica modulo 5!!)
ma quella iniziale era modulo 60
quindi hai 5 soluzioni modulo 60
e sono....
Tu sai che $ZZ_2={[0]_2,[1]_2}$
classe zero è l'insieme dei numeri pari, quella di classe 1 di quelli dispari . (i pari danno resto zero se divisi per 2, i dispari 1).
Quindi quel numero è dispari è quindi è congruo a uno modulo 2. pertanto quindi l'unica soluzione modulo 2. è proprio 1.
il due va bene. bravo.
il 3 è parzialmente corretto
$x-=5(mod12)$ è già ridotta e compatibile, puoi vederla come $x=5+12k$
una soluzione particolare è $x_0=5$ (unica modulo 5!!)
ma quella iniziale era modulo 60
quindi hai 5 soluzioni modulo 60
e sono....
"Kashaman":
[quote="GundamRX91"]Per quanto riguarda l'elemento inverso, in generale in un anello [tex](A,+,*)[/tex] un elemento [tex]a \in A[/tex] si dice invertibile se esiste un [tex]x \in A[/tex] tale che [tex]a*x=x*a=1[/tex], dove [tex]x=a^{-1}[/tex].
Se proprio vogliamo essere formali
adattiamo a $ZZ_n$ questa definizione.
teorema
Sia $a in ZZ$ ,
Allora $[a]_n$ è invertibile in $ZZ_n$ se e solo se $(a,n)=1$
dim
$=>$ supponiamo che $[a]_n$ sia invertibile allora (per la definizione di Gundam) , esiste $[m]_n in ZZ_n$ tale che
$[am]_n=[1]_n$ e cioè un $m in ZZ$ verificante la congruenza lineare $am-=1(modn)$
sia ora $d=(a,n)$, poiché $d|1 => d=1$ . Ciò prova che $[a]_n $ invertibile $=> (a,n)=1$
$\leftarrow$
Per ipotesi $(a,n)=1$ quindi per il lemma di Bezout
$EE s, t in ZZ : as+nt=1 <=> as-1=n(-t) <=> n|as-1<=> as-=1(modn)$
ciò prova che se $a,n$ sono relativamente primi allora $[a]$ è invertibile.[/quote]
Quest'ultima parte della dimostrazione si può "vedere" usando le classi dei resti:
sempre da Bèzout [tex]as+nt=1[/tex] che convertite diventa [tex][a]
ma dato che [tex][n][t]=[0][/tex] allora [tex][a]
Hai ragione, che stupido che sono, mi sono proprio dimenticato che io devo sempre fare riferimento al modulo iniziale che era $60$ quindi ottengo che :
$x_0=5+12*0=5$
$x_1=5+12*1=17$
$x_2=5+12*2=29$
$x_3=5+12*3=41$
$x_4=5+12*4=53$
Ti posso chiedere sempre sulle congruenze ho un esercizio chiede http://ricerca.mat.uniroma3.it/users/merola/madi09/interi.pdf :
Senza eseguire le moltiplicazioni per esteso, mostrare che si ha
(a) $1234567 × 90123 -= 1( mod 10)$
(b) $2468 × 13579 -= −3 (mod 25)$
Prendiamo in esame (a) :
(a) $1234567 × 90123 -= 1( mod 10)$
Possiamo vede i numeri come :
$1234567 = 1*10^6 + 2*10^5+3*10^4+4*10^3+5*10^2+6*10^1+7*10^0$
$90123 = 9*10^4+1*10^2+2*10^1+3*10^0$
Mi scrivo le classi dei resti modulo 10 è $ZZ_10 = {[1]_10,[3]_10,[7]_10,[9]_10}$ .
A occhio posso dire che sono due numeri dispari che moltiplicati tra loro danno un numero dispari.
E ora che faccio?! Che domanda mi devo porre per impostare l'esercizio? Idee?!
Grazie ancora
$x_0=5+12*0=5$
$x_1=5+12*1=17$
$x_2=5+12*2=29$
$x_3=5+12*3=41$
$x_4=5+12*4=53$
Ti posso chiedere sempre sulle congruenze ho un esercizio chiede http://ricerca.mat.uniroma3.it/users/merola/madi09/interi.pdf :
Senza eseguire le moltiplicazioni per esteso, mostrare che si ha
(a) $1234567 × 90123 -= 1( mod 10)$
(b) $2468 × 13579 -= −3 (mod 25)$
Prendiamo in esame (a) :
(a) $1234567 × 90123 -= 1( mod 10)$
Possiamo vede i numeri come :
$1234567 = 1*10^6 + 2*10^5+3*10^4+4*10^3+5*10^2+6*10^1+7*10^0$
$90123 = 9*10^4+1*10^2+2*10^1+3*10^0$
Mi scrivo le classi dei resti modulo 10 è $ZZ_10 = {[1]_10,[3]_10,[7]_10,[9]_10}$ .
A occhio posso dire che sono due numeri dispari che moltiplicati tra loro danno un numero dispari.
E ora che faccio?! Che domanda mi devo porre per impostare l'esercizio? Idee?!
Grazie ancora
quanto vale $1234567$ e $90123$ modulo 10?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo