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]

Grazie mille per le correzioni Leonardo.
Vediamo ora se riesco ad applicare quanto appreso con altri due esercizi tratti da prove d'esame. Non so perché ma ho ancora un po di difficoltà-
Es 1Sia $\phi : ZZ_60 -> ZZ_12\timesZZ_20$. Definita $\forall x in ZZ : \phi([x]_60)=([x]_12,[x]_60)$
si verifichi che $\phi $ è ben definita.

Allora, devo diciamo sempre accertarmi che se $[x]_12 = [y]_12 => \phi([x]_12)=\phi([y]_12)$
Siano $x,y in ZZ$ tali che $[x]_60=[y]_60 <=> 60|x-y <=> x-y=60k , k in ZZ$(1)
Verifico la ben definizione di $\phi$
da $ \phi([x]_12)=\phi([y]_12)$ segue che $([x]_12,[x]_20)=([y]_12,[y]_20) <=> 12|x-y=60k ^^ 20|x-y=60k$
ma ciò è vero , perché sia $12,20$ sono divisori di $60$

Es 2 Siano $n.m >=2$ interi.
Per quante coppie $(n,m) in ZZ\timesZZ$ l'applicazione $f : ZZ_12 -> ZZ_m\timesZZ_n$ Definita $\forall x in ZZ : f([x]_12) = ([x]_m,[x]_n) $
risulta essere ben definita?

Prima di tutto,mi accerto per quali $n,m$ è ben definita.
Considero $x,y in ZZ$ tali che $x=y+12 <=> x-y=12 => [x]_12=[y]_12$
Supponiamo che $f$ sia ben definita , allora $f([x]_12)=f([y]_12) $ segue che $([x]_m,[x]_n)=([y]_m,[y]_n) <=> m|x-y ^^ n|x-y=12$
Pertanto $m,n in {2,4,6,12}$ . Ciò prova che se $f$ è ben definita allora $n,m$ sono divisori di $12$
D'altro canto supponiamo che $m|12^^n|12$
e verifichiamo che per si fatti valori $f$ è ben definita.
siano $[x]_12=[y]_12 <=> 12|x-y<=>x-y=12k$
ora $f([x]_12)=f([y]_12) <=> ([x]_m,[x]_n)=([y]_m,[y]_n) <=> m|x-y=12k ^^ n | x-y=12k$ ma ciò è vero per ipotesi.
Pertanto , conclusione, $f$ ben definita se e solo se $m|12^^n|12$
Pertanto considerando $(n,m) in ZZ\timesZZ$
posso scegliere $n$ in quattro modi distinti, lo stesso modo $m$, quindi ho in totale $2^4=16$ coppie del tipo $(n,m)$ per le quali $f$ è ben definita, giusto?

Spero di non aver scritto altre fesserie. Fatemi sapere, grazie mille.
EDIT perfezionato un po

[Kashaman]

uppino

[Leonardo891]

Scusa ma rivediti il tuo ultimo post a pagina 2 del topic: ti ho detto, all'inizio di questa stessa pagina, che quella dimostrazione era pressoché perfetta. Allora ora il problema qual è? Applica quel teorema!

Es1
\(\displaystyle \phi \) è ben definita perché sia \(\displaystyle 12 \) che \(\displaystyle 20 \) dividono \(\displaystyle 60 \).

Es2
I valori di \(\displaystyle n \) ed \(\displaystyle m \) che vanno bene sono tutti i divisori di \(\displaystyle 12 \) maggiori o uguali a \(\displaystyle 2 \) quindi \(\displaystyle 2, 3, 4, 6, 12 \). Quindi le coppie (ordinate) sono \(\displaystyle 5 \cdot 5= 25 \).

[Kashaman]

"Leonardo89":Scusa ma rivediti il tuo ultimo post a pagina 2 del topic: ti ho detto, all'inizio di questa stessa pagina, che quella dimostrazione era pressoché perfetta. Allora ora il problema qual è? Applica quel teorema!

Es1
\(\displaystyle \phi \) è ben definita perché sia \(\displaystyle 12 \) che \(\displaystyle 20 \) dividono \(\displaystyle 60 \).

Es2
I valori di \(\displaystyle n \) ed \(\displaystyle m \) che vanno bene sono tutti i divisori di \(\displaystyle 12 \) maggiori o uguali a \(\displaystyle 2 \) quindi \(\displaystyle 2, 3, 4, 6, 12 \). Quindi le coppie (ordinate) sono \(\displaystyle 5 \cdot 5= 25 \).

hai ragione, ma il problema è che se mi capita come tema d'esame, posso dire semplicemente $f$ è ben definita perché ....? (magari citando un piccolo lemmino dove trasporto quel teorema magari adattato per l'occasione)
Hai ragione , cosi facendo è come reinventassi la ruota ogni volta.

[Leonardo891]

Certo che puoi, naturalmente includendo la dimostrazione del lemma tanto, stringendo, sono poche righe.

[Kashaman]

"Leonardo89":Certo che puoi, naturalmente includendo la dimostrazione del lemma tanto, stringendo, sono poche righe.

Benissimo leonardo

[Kashaman]

Salve ragazzi, riesumo un'attimo questo topic. Ho un dubbio atroce.
Allora,
Sia $f_(a,b) ([x]_m,[y]_n) = [ax+by]_(mn)$ un'applicazione.
L'esercizio mi chiedeva di trovare per quali $(a,b)$ $f_(a,b)$ è ben definita e per quali $(a,b)$ $f_(a,b)$ è iniettiva.
Per il punto della ben definizione tutto ok,
ho trovato che $f$ ben definita se e solo se $n|a ^^ m|b$.
Ora il mio cruccio è sull'iniettività.
Ho considerato $([x_1]_m,[y_1]_n) , ([x_2]_m,[y_2]_n) in ZZ_m \times ZZ_n$
e voglio vedere per quali $a,b $
$f(([x_1]_m,[y_1]_n))=f( ([x_2]_m,[y_2]_n)) => ([x_1]_m,[y_1]_n) =([x_2]_m,[y_2]_n)$
Ma onestamente, mi sento un po bloccato.
infatti , facendo i conti e tenendo conto per quali $(a,b)$ f è ben definita ottengo che (tenendo conto $n|a => a=nk ^^ m|b=>mk'$)
$m*n| nk(x_2-x_1)+mk'(y_2-y_1)$
Ora , però osserverei che $k , k' $ sono arbitrari e quindi scelto $k'=0 ^^ k=1$ si ha che $m|x_2-x_1 $ e ragionando in maniera analoga $n|y_2-y_1$ , quindi mi verrebbe da dire che $f$ è iniettiva se $a=n ^^ b=m$ ? ma è giusto ciò che sto facendo?
grazie

[Kashaman]

up

[Kashaman]

ne posto un'altro , $AA n in Z $ sia $A(n)=n^9+2n^7+3n^3+4n$
a) determinare tutti $n$ per i quali $7|A(n)$
b) determinare tutti gli $n$ per i quali $30$ non divide $A(n)$

a)$7|A(n) <=> n^9+2n^7+3n^3+4+4n-=0(mod7)$ se $n=[0]_7$ allora $7|A(n)$
supponiamo che $n!=[0]_7$ per piccolo Th. di fermat
$n^9+2n^7+3n^3+4+4n-=n^3+2n+3n^3+4n-=n(4n^2+6)-=0(mod7)<=>$
$7|n(4n^2+6)=>${abbiamo supposto che $7$ non divide $n$)$7|4n^2+6 <=> 4n^2-=1(mod7) <=> n^2-=2(mod7) => n=[3]_7 vv n=[4]_7$
pertanto $7|A(n) <=> n=[0]_7 vv n=[3]_7 vv n = [4]_7$ che ne dite?
b) $30|A(n) <=> 2|A(n) ^^ 3|A(n) ^^ 5|A(n)$
osserviamo preliminarmente che se $30|n$ allora $30|A(n)$
supponiamo ora che $30$ non divide $n$
si ha da trovare $n in ZZ$ risolvente il sistema
$n^9+2n^7+3n^3+4+4n-=0(mod2)$
$n^9+2n^7+3n^3+4+4n-=0(mod5)$
$n^9+2n^7+3n^3+4+4n-=0(mod3)$

la prima vale per ogni $n$ così anche la seconda.
la terza se e solo se $n=[0]_3$
pertanto se $n=[0]_3$ $30|A(n)$
ne segue che $30$ non divide $A(n)$ se $n!=[0]_30 ^^ n!=[0]_3$

che ne dite? grazie