[Esercizio] funzioni iniettive
Sia $f : ZZ_n -> ZZ_n$, con $[x]_n |-> [6x+7]_n$. Dire per quali $n in NN$ $f$ è iniettiva.
Per $ZZ_3$, $f$ non è iniettiva, infatti [tex]f([0]_3)=[1]_3[/tex] e [tex]f([1]_3)=[1]_3[/tex],
mentre per $ZZ_4$ e $ZZ_5$ la funzione è iniettiva.
All'inizio pensavo che la non iniettività dipendesse dai campi $ZZ_n$ con $n$ numero primo,
ma $ZZ_5$ è un campo eppure $f$ è iniettiva.... Cosa mi potete suggerire in proposito?
Grazie.
Per $ZZ_3$, $f$ non è iniettiva, infatti [tex]f([0]_3)=[1]_3[/tex] e [tex]f([1]_3)=[1]_3[/tex],
mentre per $ZZ_4$ e $ZZ_5$ la funzione è iniettiva.
All'inizio pensavo che la non iniettività dipendesse dai campi $ZZ_n$ con $n$ numero primo,
ma $ZZ_5$ è un campo eppure $f$ è iniettiva.... Cosa mi potete suggerire in proposito?
Grazie.
Risposte
Guarda, non so se il mio ragionamento è corretto, ma io avrei ragionato cosi, qualcuno mi corregga.
Allora ho che $f : Z_n -> Z_n$ definita ponendo
$f([x]_n] = [6x+7]_n$
Prima di tutto mi accerto se l'applicazione è ben definita per ogni $ n in NN$.
Siano $ [x]_n , [y]_n in Z_n$
Verifico che $ [x]_n=[y]_n => f([x]_n)=f([y]_n) , AA n$
Se $ [x]_n=[y]_n => n| x-y => x-y=kn , k in ZZ$
Ora se $f([x]_n)=f([y]_n) => ............ => n|6(x-y) =6(kn)=n(6k)$ ok.
Ora vedo per quali n $f$ risulta essere ingettiva.
Ora se $f([x]_n)=f([y]_n) => ...... => n|6(x-y)=2*3*(x-y)$
Ora se $n=2 => $ n non divide $x-y$ $=> $ f non ingettiva. Stessa cosa per $n=3$.
Ora supposta n diversa da due e tre si ha che :
n non divide ne due ne tre e di conseguenza, poiché divide il prodotto, $n|x-Y$. Dunque per n diversi da due e tre , f risulta essere ingettiva.
Allora ho che $f : Z_n -> Z_n$ definita ponendo
$f([x]_n] = [6x+7]_n$
Prima di tutto mi accerto se l'applicazione è ben definita per ogni $ n in NN$.
Siano $ [x]_n , [y]_n in Z_n$
Verifico che $ [x]_n=[y]_n => f([x]_n)=f([y]_n) , AA n$
Se $ [x]_n=[y]_n => n| x-y => x-y=kn , k in ZZ$
Ora se $f([x]_n)=f([y]_n) => ............ => n|6(x-y) =6(kn)=n(6k)$ ok.
Ora vedo per quali n $f$ risulta essere ingettiva.
Ora se $f([x]_n)=f([y]_n) => ...... => n|6(x-y)=2*3*(x-y)$
Ora se $n=2 => $ n non divide $x-y$ $=> $ f non ingettiva. Stessa cosa per $n=3$.
Ora supposta n diversa da due e tre si ha che :
n non divide ne due ne tre e di conseguenza, poiché divide il prodotto, $n|x-Y$. Dunque per n diversi da due e tre , f risulta essere ingettiva.
Ancora non sono riuscito a trovare una dimostrazione, comunque $f$ non è iniettiva per $n=2,n=3,n=6k$ per $k in ZZ$.
Non è difficile, basta applicare la definizione. Supponiamo innanzi tutto che [tex]\text{gcd}(6,n) = 1[/tex]. Allora [tex]6[/tex] è invertibile modulo [tex]n[/tex], ossia esiste [tex]a[/tex] tale che [tex][a 6]_n = [1]_n[/tex]. Allora se [tex][6x + 7]_n = [6y+7]_n[/tex] segue [tex][6x]_n = [6y]_n[/tex] e moltiplicando per [tex][a]_n[/tex], ricaviamo [tex][x]_n = [y]_n[/tex], quindi la funzione è iniettiva.
Viceversa, supponiamo che [tex]\text{gcd}(6,n) = d > 1[/tex]. Allora sia [tex]m = \frac{n}{d}[/tex]; abbiamo [tex][6m]_n = 0[/tex] e quindi [tex][6 \cdot 0 + 7]_n = [7] = [6 \cdot m + 7]_n[/tex], sicché la funzione non è iniettiva.
[OT] Sto ridendo da solo perché l'esercizio è obiettivamente facile, ma ci si potrebbe parlare sopra abbastanza a lungo, da punti di vista più avanzati (decomposizione primaria di moduli ecc.). [/OT]
Lodevole, ma inutile. E' composizione di funzioni ben definite!
Viceversa, supponiamo che [tex]\text{gcd}(6,n) = d > 1[/tex]. Allora sia [tex]m = \frac{n}{d}[/tex]; abbiamo [tex][6m]_n = 0[/tex] e quindi [tex][6 \cdot 0 + 7]_n = [7] = [6 \cdot m + 7]_n[/tex], sicché la funzione non è iniettiva.
[OT] Sto ridendo da solo perché l'esercizio è obiettivamente facile, ma ci si potrebbe parlare sopra abbastanza a lungo, da punti di vista più avanzati (decomposizione primaria di moduli ecc.). [/OT]
"Kashaman":
Prima di tutto mi accerto se l'applicazione è ben definita per ogni $ n in NN$.
Lodevole, ma inutile. E' composizione di funzioni ben definite!
Giocando con i numero ho commesso un errore di calcolo: in [tex]\mathbb{Z}_4[/tex], $f$ non è iniettiva!!!!!
E, ovviamente, Maurer aveva ragione in quanto la soluzione è semplice e dipende dalla definizione di congruenza algebrica e dal fatto che [tex]ax \equiv b_(mod n) \Leftrightarrow (a,n)=1[/tex], infatti in caso contrario possiamo avere due casi:
se [tex]a \not\mid n[/tex] allora [tex]ax \equiv 0_(mod n)[/tex], mentre se [tex]a | n[/tex] allora le classi dei resti "ciclano" (cioè assumono lo stesso valore) ogni [tex]n/d[/tex] volte (dove [tex]d=MCD(a,n)[/tex]).
Quindi [tex][x] \mapsto [6x+7]_n[/tex] è iniettiva quando [tex]MCD(6,n)=1[/tex] perchè negli altri casi possiamo avere "ripetizione" di classi dei resti, oppure zero, e quindi non può essere iniettiva.
E, ovviamente, Maurer aveva ragione in quanto la soluzione è semplice e dipende dalla definizione di congruenza algebrica e dal fatto che [tex]ax \equiv b_(mod n) \Leftrightarrow (a,n)=1[/tex], infatti in caso contrario possiamo avere due casi:
se [tex]a \not\mid n[/tex] allora [tex]ax \equiv 0_(mod n)[/tex], mentre se [tex]a | n[/tex] allora le classi dei resti "ciclano" (cioè assumono lo stesso valore) ogni [tex]n/d[/tex] volte (dove [tex]d=MCD(a,n)[/tex]).
Quindi [tex][x] \mapsto [6x+7]_n[/tex] è iniettiva quando [tex]MCD(6,n)=1[/tex] perchè negli altri casi possiamo avere "ripetizione" di classi dei resti, oppure zero, e quindi non può essere iniettiva.
Vedo che usi i tag del tex: due consigli. Il simbolo di non divisibilità ha codice \nmid. La congruenza modulo n si denota \pmod{n} (include già le parentesi e i dovuti spazi). 
L'affermazione non è del tutto corretta. Quell'equazione ha soluzione se e solo se [tex](a,n) \mid b[/tex] (quindi ha soluzione per ogni [tex]b[/tex] sse [tex](a,n) = 1[/tex]).
"GundamRX91":
la soluzione è semplice e dipende [...] dal fatto che [tex]ax \equiv b_(mod n) \Leftrightarrow (a,n)=1[/tex]
L'affermazione non è del tutto corretta. Quell'equazione ha soluzione se e solo se [tex](a,n) \mid b[/tex] (quindi ha soluzione per ogni [tex]b[/tex] sse [tex](a,n) = 1[/tex]).
Grazie!!!!! Lo stavo cercando ma non riuscivo a trovarlo, idem per la notazione di modulo
Si, vero, me ne dimentico sempre di specificarlo....
Grazie ancora
Si, vero, me ne dimentico sempre di specificarlo....
Grazie ancora
Giusto. Non c'avevo pensato. Devo ancora ben familiarizzare con la ben definizione di un f a quanto pare XD
Sarà pure obbiettivamente semplice maurer... ma per i new bie dell'algebra, come me , può essere un bel muretto da superare.
Sarà pure obbiettivamente semplice maurer... ma per i new bie dell'algebra, come me , può essere un bel muretto da superare.
Sono gli scogli naturali attraverso cui siamo passati tutti quanti! 
Non arrenderti e vedrai che presto ti sembrerà facilissimo (ho una teoria al riguardo, che il livello di difficoltà soggettivo - i.e. percepito dall'individuo - di un qualsiasi argomento tenda a zero quando il tempo passato a lavorare in quel settore tenda all'infinito
).P.S. Si dice newbie, senza spazio!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo