Alcuni esercizi di Aritmetica modulare

[Kashaman]

rivedendo un po gli argomenti di aritmetica modulare mi sono imbattuto nei seguenti quesiti, e confido in un vostro riscontro, per esser sicuro di aver ragionato come si deve . ringrazio anticipatamente coloro che mi risponderanno.
Quesito 1
Confutare o provare che :
Sia $x in ZZ$
$x$ invertibile in $ZZ_n <=>$ $x$ invertibile in $ZZ_(n^2)$
soluzione :

La condizione necessaria e sufficiente affinché $x$ sia invertibile in $ZZ_n$ è che $(x,n)=1$
Devo mostrare che $(x,n)=1<=>(x,n^2)=1$.
Mostro per via indiretta che $(x,n)!=1 <=> (x,n^2)!=1$
detto $n=p_1*p_2*.....*p_s$ ove $p_i$ son primi, equivale a dire che $x$ non ha fattori primi in comune con $n$.
Pertanto , considerato $n^2=(p_1*p_2*.....*p_s)^2=p_1^2*p_2^2*.....*p_s^2$segue che $n^2$ non ha fattori primi comuni con $x$, pertanto segue la tesi. Cioè se $x$ non è invertibile in $ZZ_n$ allora non lo è in $Z_(n^2)$ e viceversa.
Che ve ne pare?

Quesito 2
Trovare tutti gli $n in NN$
tali che $4*7-=_n2^4$
soluzione :

$4*7-=_n2^4 => 12-=_n0 => n in {2,3,4,6,12}$

Quesito 3 :
Al variare di $k in NN$ , determinare l'ultima cifra decimale del numero
$2^(2^k)+6$

Si ha dunque da trovare il resto della divisione euclidea di $2^(2^k)+6$
per $10$.
Cioè trovare $x in ZZ$ tale che $x-=2^(2^k)+6(mod10)$ o equivalentemente risolvere il sistema di congruenze dato da
$x-=0(mod2)
x-=2^(2^k)+1(mod5)$
Nel caso in cui $k=0,1$ la soluzione è immediata. si ha $x=8,0$ rispettivamente.
Consideriamo il termine $2^(2^k)(mod5)$
se $k=2q , q in ZZ$ è pari allora $2^(2^k)-=2^(4^q)-=1(mod5)$, visto che per il piccolo teorema di fermat $2^4-=1(mod5)$ e $4|4^q$.
Equivalentemente se $k=2q+1 => 2^(2^k)-= 2^ (2^(2q+1)) -=2^(4^q*2)-=1(mod5)$
da cui segue che $2^(2^k)-=1(mod5) AA k in NN \\ {0,1}$.
pertanto ho da considerare
$x-=0(mod2)
x-=2(mod5) $
da cui $x-=2(mod10)$
conclusione
per $k=0 => x=8 , k=1 => x=0 , AA k in NN\\{0,1} $ , come vi sembra?

Quesito 4

Sia $n$ un intero dispari.
Mostrare che $n^2-=1(mod8)$
soluzione

Sia $n=2k+1, k in ZZ$
$n^2-=4k^2+4k+1$.
Se $n^2-=1(mod8) => n^2-1-=4k^2+4k-=0(mod8)$ , verifico questo.
$4k^2+4k-=0(mod8) => 2k^2+2k-=0(mod4) => k^2+k-=0(mod2)$ pertanto, $4(k^2+k)-=n^2-1-=0(mod8)$, quindi
$n^2-=n^2-1+1-=1(mod8)$ la tesi.

Cordiali saluti.

[Kashaman]

up

[Leonardo891]

Correggo il 4.

Sia $n=2k+1, k in ZZ$. Allora $n^2-=4k^2+4k+1$. Si ha
$n^2-=1(mod8) \Leftrightarrow n^2-1-=0(mod8) \Leftrightarrow 4k^2+4k-=0(mod8) \Leftrightarrow 4k(k+1) -=0 (mod8)$.
Poiché \(\displaystyle k \in \mathbb{Z} \) allora o \(\displaystyle k \) o \(\displaystyle k + 1 \) è pari quindi \(\displaystyle k(k+1) \) è divisibile per \(\displaystyle 2 \) quindi \(\displaystyle 4k(k+1) \) è divisibile per \(\displaystyle 8 \) da cui la tesi.

Nella tua dimostrazione devi stare attento se le implicazioni sono unidirezionali o bidirezionali.
Mi spiego: se dimostri che la tesi è equivalente a qualcosa e dimostri quel qualcosa hai dimostrato la tesi ma se dimostri solamente che la tesi implica qualcosa e dimostri quel qualcosa non hai dimostrato la tesi.

Verso la fine la tua dimostrazione diventa molto confusionaria, inoltre: mi sembra di capire che tu sfrutti una conseguenza della tesi per dimostrare la tesi stessa!

Un'altra cosa a cui devi stare attento è la legge di cancellazione in aritmetica modulare. Te ne riporto la versione corretta.

Sia \(\displaystyle [c]_n [a]_n = [c]_n _n \) in \(\displaystyle \mathbb{Z}_n \). Se \(\displaystyle MCD(c, n)=1 \) allora si ha \(\displaystyle [a]_n = _n \).

Spero sia tutto a posto e di non aver sbagliato niente.

Edit: ho sostituito una congruenza con una uguaglianza.

[Kashaman]

grazie leonardo per la tua risposta, molto esauriente. Bastava alla fin fine dire questo
$n=2k+1$ è dispari.
consideriamo $n^2=4k^2+2k+1$. Allora
$n^2-=1(mod8)<=>n^2-1-=0(mod8)<=>4k^2+k-=0(mod8)<=>4k(k+1)-=0(mod8)$
A questo punto uno tra $k$ e $k+1$ è pari. (infatti se $k$ è pari $=>$ $k+1$ è dispari , se $k+1$ è pari allora $k=k+1-1$ è dispari , giusto?) pertanto uno tra $k$ e $k+1$ è divisibile per $2$ e dunque $4k(k+1)$ lo è per $8$

giusto o prendo cantonate?

[Leonardo891]

È giusto, hai sostanzialmente riscritto la mia dimostrazione.

Piuttosto, ho dato un'occhiata alla soluzione del numero 2.
Con quelle implicazioni tu hai dimostrato solamente che esistono al massimo \(\displaystyle 5 \) valori di \(\displaystyle n \) che verificano quella relazione: non hai dimostrato che quei \(\displaystyle 5 \) valori di \(\displaystyle n \) la verificano.
Questo perché tu hai scritto delle implicazioni unidirezionali e non delle implicazioni bidirezionali.
L'esercizio, quindi, è concettualmente sbagliato.
In realtà, quelle frecce sono tutte bidirezionali, cioè equivalenze, quindi la correzione è semplice.

Tutto ciò, forse, potrebbe sembrarti una mia sega mentale, soprattutto data la semplicità degli esercizi, ma ti garantisco che, concettualmente, l'errore è notevole: meglio estirparlo subito, prima che vada ad infestare esercizi più complicati.
L'importante è che tu capisca che dimostrare una conseguenza della tesi non vuol dire dimostrare la tesi.
Naturalmente se dimostri qualcosa di equivalente alla tesi allora hai dimostrato la tesi.

[Kashaman]

Hai ragione Leonardo. In sostanza ho sbagliato i connettivi logici e c'hai ragione.
Non penso siano seghe mentali le tue, anzi.
Correggo subito
$12-=_n0<=> n|12 <=> n in {2,3,4,6,12}$ ora credo vada bene . ( il motivo del mio errore è che prima dicevo semplicemente che se $12-=_n0 (1)=> n in {2,3,4,6,12}$ cioè posso trovare un possibile $n$ che soddisfa la (1) in quell'insieme. Ma non dico che ogni elemento di quell'insieme è soluzione giusto?. Quindi aggiungendo $<$$=$ confermo che ogni elemento di quell'insieme è soluzione della (1), esatto?)

[Leonardo891]

"Kashaman":cioè posso trovare un possibile $n$ che soddisfa la (1) in quell'insieme. Ma non dico che ogni elemento di quell'insieme è soluzione giusto?.

Ciò che tu dimostravi è che se esiste una soluzione, allora deve fare parte di quell'insieme, ma potrebbe anche darsi che nessun elemento di quell'insieme sia una soluzione.

"Kashaman":Quindi aggiungendo $<$$=$ confermo che ogni elemento di quell'insieme è soluzione della (1), esatto?)

Esatto ma devi accertarti che tu lo possa fare, cioè che la freccia sia realmente bidirezionale: in questo caso banalmente lo è ma in generale no.

Passiamo al quesito 1.

"Kashaman":La condizione necessaria e sufficiente affinché $x$ sia invertibile in $ZZ_n$ è che $(x,n)=1$
Devo mostrare che $(x,n)=1 \Leftrightarrow (x,n^2)=1$.
Mostro per via indiretta che $(x,n)!=1 <=> (x,n^2)!=1$

Va benissimo, anche se no so cosa intendi per "via indiretta". In realtà \(\displaystyle (x,n)=1 \Leftrightarrow (x,n^2)=1 \) è equivalente a \(\displaystyle (x,n) \neq 1 \Leftrightarrow (x,n^2) \neq 1 \) e dimostrare quest'ultima penso sia più semplice, prova a farlo.

"Kashaman":detto $n=p_1*p_2*.....*p_s$ ove $p_i$ son primi, equivale a dire che $x$ non ha fattori primi in comune con $n$.
Pertanto , considerato $n^2=(p_1*p_2*.....*p_s)^2=p_1^2*p_2^2*.....*p_s^2$segue che $n^2$ non ha fattori primi comuni con $x$, pertanto segue la tesi. Cioè se $x$ non è invertibile in $ZZ_n$ allora non lo è in $Z_(n^2)$ e viceversa.

Tutto questo non è molto chiaro, cerca di spiegarti meglio, anzi, cerca di dimostrare \(\displaystyle (x,n) \neq 1 \Leftrightarrow (x,n^2) \neq 1 \).

[Kashaman]

Ci provo . Speriamo di non dire cavolate.
Voglio mostrare che $(x,n)=d <=> (x,n^2)=d$. $d in ZZ$
Per definizione di massimo comune divisore $d|n $
quindi $d|n <=> n=dq , q in ZZ <=> n*(n)=ndq <=> n^2 = d(nq) $ Posto $k=nq in ZZ$
$n^2=dk <=> d|n^2$.
Ciò prova $<=>$. E dunque la tesi.

[Leonardo891]

"Kashaman":Voglio mostrare che $(x,n)=d <=> (x,n^2)=d$. $d in ZZ$

Non è vero. Prova con \(\displaystyle x=4 \) ed \(\displaystyle n=6 \). Non ti ho nemmeno chiesto di dimostrarlo.
Ciò che ti ho chiesto di dimostrare è che $(x,n) != 1 <=> (x,n^2) != 1$.

[Kashaman]

Tralasciando per un attimo l'esercizio, ho un forte dubbio sulle applicazioni ben definite che mi è sorto.
Consideriamo per esempio questa applicazione :
$f : ZZ_60 -> ZZ_12xZZ_20$ definita per ogni $x in ZZ$ , $f([x]_60)=([x]_12,[x]_20)$
se volessi verificare che si tratta di un'applicazione ben definita , dovrei verificare la seguente implicazione:
$[x]_60=[y]_60 => f([x]_60)=f([y]_60)$ e cioè che ad elementi congrui corrispondono immagini congrue, giusto?
Posso procedere al seguente modo ?
Siano $[x]_60 , [y]_60 in ZZ_60 | [x]_60=[y]_60 (1)$
dalla $(1)$ si evince che
$[x]_60=[y]_60 <=> 60|x-y <=> x-y=60k , k in ZZ$ (2)
Verifico ora che $f([x]_60)=f([y]_60)$
si ha che $f([x]_60)=f([y]_60) <=> ([x]_12,[x]_20)=([y]_12,[y]_20) <=> ... <=> 12| x-y = 60k ^^ 20| x-y=60k$ da cui la tesi?
Oppure posso fare in quest'altro modo :
Sia $[x] _60 in ZZ_60$ ogni altro rappresentante di $[x]_60$ è dato da $x+60k$
Pertanto se f è ben definita deve risultare che
$f([x]_60)=f(x+60k)$.
Cosa sbaglio? Grazie mille.

[Leonardo891]

"Kashaman":si ha che $f([x]_60)=f([y]_60) <=> ([x]_12,[x]_20)=([y]_12,[y]_20) <=> ... <=> 12| x-y = 60k ^^ 20| x-y=60k$ da cui la tesi?

Sì, perché sia \(\displaystyle 12 \) che \(\displaystyle 20 \) dividono \(\displaystyle 60 \).

"Kashaman":Pertanto se f è ben definita deve risultare che
$f([x]_60)=f(x+60k)$.
Cosa sbaglio? Grazie mille.

Cosa intendi con \(\displaystyle x +60k \)?

Supponiamo che tu intenda \(\displaystyle x +60k = x + 60 \mathbb{Z} \in \mathbb{Z}_{60} \) (notazione insolita).
Allora $[x]_60$ e $x+60k$ sono la stessa identica cosa, notazioni differenti per lo stesso elemento!
Scrivere $f([x]_60)=f(x+60k)$ è come scrivere $f([x]_60)=f([x]_60)$!

Supponiamo che tu intenda \(\displaystyle x +60k \in \mathbb{Z} \).
Allora $f(x+60k)$ non ha senso perché il dominio di \(\displaystyle f \) è \(\displaystyle \mathbb{Z}_{60} \) e non \(\displaystyle \mathbb{Z} \).

Edit: ho precisato alcune cose.

[Kashaman]

Come sempre, sai essere davvero esaustivo. Ti ringrazio. Mi hai colmato i miei dubbi.
Quindi succo del discorso, se ho un'applicazione del tipo
$f : ZZ_n -> ZZ_q XX ZZ_s$ definita $Aa x in ZZ : f([x]_n)=([x]_q,[x]_s)$ essa è ben definita se e solo se $q,s $ sono divisori di $n$ , giusto?
Quindi ad esempio se prendo
$f : ZZ_6 -> ZZ_12$ def $AA x in ZZ : f([x]_6)=[x]_12$ tale applicazione non è ben definita, infatti $12$ non divide $6$.
infatti essendo $[1]_6=[7]_6$
si nota subito che $f([1])=[1]_12!=[7]_12=f([7]_12)$
Però noterei una cosa , alla fin fine posso costruire un'applicazione che manda $ZZ_6 -> ZZ_12$
basta prendere una del tipo
$f([x]_6)=[ax]_12$
Quindi se $[x]=_6[y] => 6|x-y$
da cui $12|a(x-y)=a6k => a-=0(mod2)$ dunque se $2|a$ l'applicazione è ben definita o sbaglio?!
giusto?

[Leonardo891]

"Kashaman":Come sempre, sai essere davvero esaustivo. Ti ringrazio. Mi hai colmato i miei dubbi.
Quindi succo del discorso, se ho un'applicazione del tipo
$f : ZZ_n -> ZZ_q XX ZZ_s$ definita $Aa x in ZZ : f([x]_n)=([x]_q,[x]_s)$ essa è ben definita se e solo se $q,s $ sono divisori di $n$ , giusto?

Aspetta. Se \(\displaystyle q, s \) sono divisori di \(\displaystyle n \) l'applicazione \(\displaystyle f \) è ben definita, ok.
Chi ti dice che se l'applicazione \(\displaystyle f \) è ben definita allora \(\displaystyle q, s \) sono divisori di \(\displaystyle n \)? È vero, capiamoci, ma va dimostrato. Tu non l'hai fatto.

Dato che ci siamo \(\displaystyle \forall \) si scrive con \forall e \(\displaystyle \times \) con \times.

"Kashaman":Quindi ad esempio se prendo
$f : ZZ_6 -> ZZ_12$ def $AA x in ZZ : f([x]_6)=[x]_12$ tale applicazione non è ben definita, infatti $12$ non divide $6$.
infatti essendo $[1]_6=[7]_6$
si nota subito che $f([1])=[1]_12!=[7]_12=f([7]_12)$

Ok.

"Kashaman":Però noterei una cosa , alla fin fine posso costruire un'applicazione che manda $ZZ_6 -> ZZ_12$
basta prendere una del tipo
$f([x]_6)=[ax]_12$

Innanzitutto devi dimostrare che è ben definita poi, non capisco perché se anche fosse ben definita ciò sarebbe in contraddizione con la \(\displaystyle f \) dell'inizio del post. Sono due funzioni differenti anzi, la prima è un caso particolare della seconda con \(\displaystyle a=1 \).

"Kashaman":Quindi se $[x]=_6[y] => 6|x-y$
da cui $12|a(x-y)=a6k$

Perché \(\displaystyle 12 | a(x-y) \)?

"Kashaman":$=> a-=0(mod2)$

Perché \(\displaystyle 2 \) divide \(\displaystyle a \) e non \(\displaystyle k \)?

"Kashaman":dunque se $2|a$ l'applicazione è ben definita o sbaglio?!

Sì, è ben definita, ma dovresti dimostrarlo!
L'ultima parte che hai scritto non ha alcun senso! È un pasticcio!
Scrivi le ipotesi, parti da queste e cerca di arrivare alla tesi.

[Kashaman]

Ci riprovo.
Supponiamo di avere $f : ZZ_6-> ZZ_12$ , $ a in ZZ$ tale che $f(x)=[ax]_12$
Determinare per quali $a$ , $f$ risulta essere ben definita.
svolgimento.
Come sempre devo accertarmi che dati $x,y in ZZ$
se $[x]_6=[y]_6 => f([x]_6)=f([y]_6)$
Dunque, $[x]_6=[y]_6 <=> [x-y]_6=[0]_6<=>x-y-=0(mod6) <=>6|x-y<=>x-y=6k, k in ZZ$ (1)
verifico ora per quali $a$ $f$ è ben definita.
$f([x]_6)=f([y]_6) <=> [ax]_12=[ay]_12 <=> [ax-ay]_12=[0]_12 <=> [a(x-y)]_12=[0]_12 <=> 12|a(x-y)$ da cui per la (1)
$12|6ak <=> 6ak-=0(mod12) <=> ak-=0(mod2)<=>2|ak => 2|a vv 2|k$ (per la primalità di $2$)
da cui segue che $a-=0(mod2)$ pertanto , $f$ è ben definita se $a in {2,4,6,8,10,12,14,.....}$
Va meglio così , che ne dici? o pecco ancora in qualcosa?

[Leonardo891]

Se \(\displaystyle a \) è un multiplo di \(\displaystyle 2 \) allora \(\displaystyle f \) ben definita, ok.
Ma resta da far vedere che se \(\displaystyle f \) è ben definita allora \(\displaystyle a \) è un multiplo di \(\displaystyle 2 \).
Forse mi conviene scrivere tutto quanto per bene a questo punto.

Considero \(\displaystyle f \colon \mathbb{Z}_n \to \mathbb{Z}_s \) tale che \(\displaystyle f([x]_n)=[x]_s \) con \(\displaystyle s \) primo.
Voglio dimostare che \(\displaystyle f \) è ben definita se e solo se \(\displaystyle s \) divide \(\displaystyle an \).

Supponiamo che \(\displaystyle s \) divida \(\displaystyle a n \).
Sia \(\displaystyle [x_1]_n=[x_2]_n \). Allora esiste \(\displaystyle k \in \mathbb{Z} \) tale che \(\displaystyle x_1 -x_2 = nk \).
Devo dimostrare che \(\displaystyle [a x_1]_s=[a x_2]_s \) cioè che \(\displaystyle s | a(x_1 - x_2 ) \) ma ciò è vero perché \(\displaystyle a( x_1 -x_2 ) = ank \) ed \(\displaystyle s | an \) per ipotesi.

Supponiamo ora \(\displaystyle f \) ben definita.
Sia \(\displaystyle x_2 \in \mathbb{Z} \). Pongo \(\displaystyle x_1=x_2 + n(s+1) \). Allora \(\displaystyle [x_1]_n=[x_2]_n \).
Poiché \(\displaystyle f \) è ben definita si ha \(\displaystyle [a x_1]_s=[a x_2]_s \) quindi \(\displaystyle s | a(x_1 - x_2)=an(s+1) \).
Se \(\displaystyle s | (s+1) \) esiste \(\displaystyle l \in \mathbb{Z} \) tale che \(\displaystyle s+1=ls \) quindi \(\displaystyle s(l-1)=1 \) di conseguenza \(\displaystyle s= \pm 1 \) il che è assurdo per la primalità di \(\displaystyle s \).
Quindi \(\displaystyle s | an \).

Dovrebbe essere tutto corretto (spero ).

Edit: ho corretto un errore, \(\displaystyle s \) non può essere invertibile perché è primo.

[Kashaman]

Sarò un po tardo, ma onestamente non riesco a capire una cosa.
Praticamente quello che ho mostrato io è che $f$ è che se $2|a = >f$ è ben definita , giusto? Quindi in realtà dovevo mostrare anche che $f$ ben definita $=> 2|a$ o sbaglio?!
quindi devo mostrare una doppia equivalenza giusto?
L'esempio riportato sotto è il caso generale?

"Leonardo89":

Considero \(\displaystyle f \colon \mathbb{Z}_n \to \mathbb{Z}_s \) tale che \(\displaystyle f([x]_n)=[ax]_s \) con \(\displaystyle s \) primo.
Voglio dimostare che \(\displaystyle f \) è ben definita se e solo se \(\displaystyle s \) divide \(\displaystyle an \).

La prima, perché consideri $s$ primo? Per una questione di comodità?

"Leonardo89":

Supponiamo che \(\displaystyle s \) divida \(\displaystyle a n \).
Sia \(\displaystyle [x_1]_n=[x_2]_n \). Allora esiste \(\displaystyle k \in \mathbb{Z} \) tale che \(\displaystyle x_1 -x_2 = nk \).
Devo dimostrare che \(\displaystyle [a x_1]_s=[a x_2]_s \) cioè che \(\displaystyle s | a(x_1 - x_2 ) \) ma ciò è vero perché \(\displaystyle a( x_1 -x_2 ) = ank \) ed \(\displaystyle s | an \) per ipotesi.

Questo diciamo è quello che abbiamo fatto prima quando abbiamo verificato che la funzione era ben definita, giusto? O meglio , stai dimostrando che se $s$ è un divisore di $an$ allora $f$ è ben definita. Giusto?

"Leonardo89":
Supponiamo ora \(\displaystyle f \) ben definita.
Sia \(\displaystyle x_2 \in \mathbb{Z} \). Pongo \(\displaystyle x_1=x_2 + n(s+1) \). Allora \(\displaystyle [x_1]_n=[x_2]_n \).
Poiché \(\displaystyle f \) è ben definita si ha \(\displaystyle [a x_1]_s=[a x_2]_s \) quindi \(\displaystyle s | a(x_1 - x_2)=an(s+1) \).
Se \(\displaystyle s | (s+1) \) esiste \(\displaystyle l \in \mathbb{Z} \) tale che \(\displaystyle s+1=ls \) quindi \(\displaystyle s(l-1)=1 \) di conseguenza \(\displaystyle s= \pm 1 | an \).
Altrimenti \(\displaystyle s | an \) (\(\displaystyle s \) è primo per ipotesi).

Dovrebbe essere tutto corretto (spero ).

Qui invece ti sei accertato dell'unicità per i quali $f$ è ben definita, giusto? Cioè $f$ ben definita $=> s|an$ giusto?
Una cosa, Perché poni $x_1=x_2+n(s+1)$?
grazie mille

[Leonardo891]

"Kashaman":Praticamente quello che ho mostrato io è che $f$ è che se $2|a = >f$ è ben definita , giusto? Quindi in realtà dovevo mostrare anche che $f$ ben definita $=> 2|a$ o sbaglio?!
quindi devo mostrare una doppia equivalenza giusto?
L'esempio riportato sotto è il caso generale?

Tutto giusto.

"Kashaman":La prima, perché consideri $s$ primo? Per una questione di comodità?

Sì, perché mi faceva comodo nella seconda parte della dimostrazione: per pigrizia non mi andava di controllare se la seconda parte potesse fare a meno dell'ipotesi \(\displaystyle s \) primo.
Ho appena controllato che \(\displaystyle s \) può essere un numero intero qualsiasi: prova a modificare la mia dimostrazione per adattarla ad un \(\displaystyle s \) qualsiasi.

"Kashaman":
[quote="Leonardo89"]

Supponiamo che \(\displaystyle s \) divida \(\displaystyle a n \).
Sia \(\displaystyle [x_1]_n=[x_2]_n \). Allora esiste \(\displaystyle k \in \mathbb{Z} \) tale che \(\displaystyle x_1 -x_2 = nk \).
Devo dimostrare che \(\displaystyle [a x_1]_s=[a x_2]_s \) cioè che \(\displaystyle s | a(x_1 - x_2 ) \) ma ciò è vero perché \(\displaystyle a( x_1 -x_2 ) = ank \) ed \(\displaystyle s | an \) per ipotesi.

Questo diciamo è quello che abbiamo fatto prima quando abbiamo verificato che la funzione era ben definita, giusto? O meglio , stai dimostrando che se $s$ è un divisore di $an$ allora $f$ è ben definita. Giusto?[/quote]
Giusto e giusto.

"Kashaman":
[quote="Leonardo89"]
Supponiamo ora \(\displaystyle f \) ben definita.
Sia \(\displaystyle x_2 \in \mathbb{Z} \). Pongo \(\displaystyle x_1=x_2 + n(s+1) \). Allora \(\displaystyle [x_1]_n=[x_2]_n \).
Poiché \(\displaystyle f \) è ben definita si ha \(\displaystyle [a x_1]_s=[a x_2]_s \) quindi \(\displaystyle s | a(x_1 - x_2)=an(s+1) \).
Se \(\displaystyle s | (s+1) \) esiste \(\displaystyle l \in \mathbb{Z} \) tale che \(\displaystyle s+1=ls \) quindi \(\displaystyle s(l-1)=1 \) di conseguenza \(\displaystyle s= \pm 1 \) il che è assurdo per la primalità di \(\displaystyle s \).
Quindi \(\displaystyle s | an \).

Dovrebbe essere tutto corretto (spero ).

Qui invece ti sei accertato dell'unicità per i quali $f$ è ben definita, giusto? Cioè $f$ ben definita $=> s|an$ giusto?
Una cosa, Perché poni $x_1=x_2+n(s+1)$? [/quote]
Perché mi fa comodo per dimostrare la tesi, e funziona.

Edit: ho corretto un errore nel mio quote, \(\displaystyle s \) non può essere invertibile perché è primo.

[Kashaman]

Estenderò il caso per $n$ qualsiasi, quanto prima.
Quindi, ritornando al caso di prima, provo a rifarlo sulle righe di ciò che mi hai appena dimostrato, dimmi se il modo di svolgerlo è corretto.
Sia $f : ZZ_6 -> ZZ_12$ un'applicazione definita ponendo $f([x]_6)=[ax]_12$.
Determinare per quali $a$ f è ben definita.
svolgimento :
supponiamo che $[x]_6=[y]_6<=> 6|x-y <=> x-y=6k , k in ZZ$ (1)
determino per quali possibili $a$ f è ben definita.
se $f([x]_6)=f([y]_6) <=> [ax]_12=[ay]_12 <=> 12|a(x-y) <=>12|6ak<=> ak-=0(mod2)<=>2|ak => 2|a vv 2|k$
Pertanto se $a-=0(mod2) =>f$ è ben definita.
Ora dimostro che $f$ è ben definita $=>$ $2|a$
Sia $y in ZZ$
supponiamo che $y=x+13*6=> [y]_6=[x]_6$
Per ipotesi, $f$ è ben definita quindi
$[ax]_12=[ay]_12$ quindi $12|a(x-y) => 12|a(13*6)<=> 13*6a-=1*6a-=6a-=0(mod12) => a-=0(mod2)$
Ciò mostra che
$f$ è ben definita $<=> 2|a$ .
E' giusto?

[Leonardo891]

Attenzione, nel quote di Kashaman del mio post permane un mio errore che ho provveduto a correggere nei miei post.

"Kashaman":Estenderò il caso per $n$ qualsiasi, quanto prima.

Guarda che l'hai fatto esattamente qui sotto, senza rendertene nemmeno conto. La tua dimostrazione, inoltre, è più sintetica della mia che prevedeva la scomposizione di \(\displaystyle s \) in fattori primi.

"Kashaman":Quindi, ritornando al caso di prima, provo a rifarlo sulle righe di ciò che mi hai appena dimostrato, dimmi se il modo di svolgerlo è corretto.
Sia $f : ZZ_6 -> ZZ_12$ un'applicazione definita ponendo $f([x]_6)=[ax]_12$.
Determinare per quali $a$ f è ben definita.
svolgimento :
supponiamo che $[x]_6=[y]_6<=> 6|x-y <=> x-y=6k , k in ZZ$ (1)
determino per quali possibili $a$ f è ben definita.
se $f([x]_6)=f([y]_6) <=> [ax]_12=[ay]_12 <=> 12|a(x-y) <=>12|6ak<=> ak-=0(mod2)<=>2|ak => 2|a vv 2|k$
Pertanto se $a-=0(mod2) =>f$ è ben definita.
Ora dimostro che $f$ è ben definita $=>$ $2|a$
Sia $y in ZZ$
supponiamo che $y=x+13*6=> [y]_6=[x]_6$
Per ipotesi, $f$ è ben definita quindi
$[ax]_12=[ay]_12$ quindi $12|a(x-y) => 12|a(13*6)<=> 13*6a-=1*6a-=6a-=0(mod12) => a-=0(mod2)$
Ciò mostra che
$f$ è ben definita $<=> 2|a$ .
E' giusto?

Tutto giusto tranne questo passaggio:

"Kashaman":$12|a(x-y) => 12|a(13*6)<=> 13*6a-=1*6a-=6a-=0(mod12) => a-=0(mod2)$

La versione corretta è
$12|a(x-y) => 12|a(13*6)<=> 0 -=13*6a-=1*6a-=6a(mod12) => a-=0(mod2)$

[Kashaman]

Si , Leonardo, mi son reso conto che ho esteso la tua proposizione, ma non è il caso generale. Infatti ho applicato un po intuitivamente il tutto al caso particolare per $n=6$ , $s=12$ e $a in ZZ$.
Cerco di formalizzare il tutto ora.
Th
Siano $n,m$ interi positivi. E sia $a in ZZ$.
consideriamo l'applicazione , definita ponendo, $AA x in ZZ : f([x]_n)=[ax]_m$ .
Risulta che
$f$ è ben definita $<=> m|an$
dim $<$$=$
Supponiamo che $m|an$ e verifichiamo che $f$ è ben definita.
Sia $[x_1]_n=[x_2]_n$ allora $n|x_1-x_2 <=> EE k in ZZ : x_1-x_2=nk$.
Consideriamo ora $f([x_1])=f([x_2]$
allora $[ax_1]_m=[ax_2]_m <=> m|a(x_1-x_2)$ e cioè $m|ank$ ma ciò è vero perché per ipotesi $m|an$. Quindi $f$ è ben definita se $m|an$
$=>$
Verifichiamo ora che se $f$ ben definita allora $m|an$
Sia $x_2 in ZZ$
e sia $x_1= x_2+n(m+1) in ZZ$.
Allora
$[x_1]_n=[x_2]_n <=> x_1-x_2=n(m+1)$
Per ipotesi $f$ risulta essere ben definita pertanto
$[ax_1]_m=[ax_2]_m <=> m|a(x_1-x_2)<=> m|an(m+1) <=> (m+1)an-=0(modm) => an-=0(modm) =>m|an$ , perché $(m+1)-=1(modm)$
ciò mostra che se $f$ è ben definita $=>$ $m|n$
(effettivamente non c'era bisogno dell'ipotesi $m$ primo!!)
pertanto il teorema è dimostrato.

Spero di non aver fatto errori, che dici va bene?

[Leonardo891]

"Kashaman":Si , Leonardo, mi son reso conto che ho esteso la tua proposizione, ma non è il caso generale. Infatti ho applicato un po intuitivamente il tutto al caso particolare per $n=6$ , $s=12$ e $a in ZZ$.
Cerco di formalizzare il tutto ora.

Hai ragione, non era il caso generale, ma ci mancava veramente pochissimo!
La tua ultima dimostrazione va benissimo, correggo solo due sviste.

"Kashaman":Sia $x_2 in ZZ$
e sia $x_1= x_2+n(m+1) in ZZ$.
Allora
$[x_1]_n=[x_2]_n <=> x_1-x_2=n(m+1)$

Quest'ultima implicazione è solo da destra verso sinistra perché \(\displaystyle m+1 \) è fissato e non è un intero generico. Ciò, comunque, non è un problema perché noi abbiamo bisogno solo dell'implicazione da destra verso sinistra.

"Kashaman":ciò mostra che se $f$ è ben definita $=>$ $m|n$

Penso che intendevi \(\displaystyle m | an \).