Uguaglianza tra numeri funzione eulero e classi invertibili
Volendo dimostrare che l'insieme $\varphi (m)$ dei naturali minori di $m$ e primi con $m$ è uguale all'insieme dei naturali tali che le rispettive classi di congruenza risultino invertibili nell'insieme quoziente $\mathbb{Z}_m$.
Se $a \in {a \in \mathbb{N} : a_m \in \mathbb{Z}_m \ "e" \ \ a_m \ "e' invertibile" }$ allora sicuramente $a \equiv r (mod m)$ ossia $a-r=mk \Rightarrow a=mk+r$ con $r
Se $a \in \varphi (m) = {a \in NN : a
Può scorrere come ragionamento ?
Se $a \in {a \in \mathbb{N} : a_m \in \mathbb{Z}_m \ "e" \ \ a_m \ "e' invertibile" }$ allora sicuramente $a \equiv r (mod m)$ ossia $a-r=mk \Rightarrow a=mk+r$ con $r
Se $a \in \varphi (m) = {a \in NN : a
Può scorrere come ragionamento ?
Risposte
E' sufficiente dimostrare che $a$ è coprimo con $m$ se e solo se è invertibile in $\mathbb Z_m$.
Se $\gcd(a,m)=1$ esistono $h,k$ tali che $ah+mk=1$, e riducendo entrambi i lati modulo $m$ si ha che $ah=1$, sicché $h=a^{-1}$ in $\mathbb Z_m$.
Se $a$ è invertibile modulo $m$ allora esiste $h$ tale che $ah=1$ modulo $m$, ovvero $ah-1=km$, e allora $\gcd(a,m)$ divide 1. Del resto ora può solo essere 1.
Se $\gcd(a,m)=1$ esistono $h,k$ tali che $ah+mk=1$, e riducendo entrambi i lati modulo $m$ si ha che $ah=1$, sicché $h=a^{-1}$ in $\mathbb Z_m$.
Se $a$ è invertibile modulo $m$ allora esiste $h$ tale che $ah=1$ modulo $m$, ovvero $ah-1=km$, e allora $\gcd(a,m)$ divide 1. Del resto ora può solo essere 1.
Si ma infatti sono io che mi devo complicare la vita 
Il punto è che leggendo una dispensa da qualche parte (non ritrovo nemmeno dove) ho trovato scritto che "si prova facilmente che per ogni naturale $m>1$, $\varphi (m)$ è il numero delle classi di congruenza modulo $m$ di interi primi con $m$ (suggerimento: per ogni intero $a$ se $r$ è il resto della divisione di $a$ per $m$ allora $M.C.D.(a,m)=1 \Leftrightarrow M.C.D.(r,m)=1$, in particolare $a$ è primo con $m$ se e solo se $r$ lo è)".
Se però volessi seguire il suggerimento dato, arrivo a questo:
Se $a$ è un generico elemento di $\varphi(m)$, dato $a=mq+r, r
E comunque, a prescindere da tutto, mi sa che inizio una campagna contro l'uso del "si prova facilmente" nei testi di matematica
Il punto è che leggendo una dispensa da qualche parte (non ritrovo nemmeno dove) ho trovato scritto che "si prova facilmente che per ogni naturale $m>1$, $\varphi (m)$ è il numero delle classi di congruenza modulo $m$ di interi primi con $m$ (suggerimento: per ogni intero $a$ se $r$ è il resto della divisione di $a$ per $m$ allora $M.C.D.(a,m)=1 \Leftrightarrow M.C.D.(r,m)=1$, in particolare $a$ è primo con $m$ se e solo se $r$ lo è)".
Se però volessi seguire il suggerimento dato, arrivo a questo:
Se $a$ è un generico elemento di $\varphi(m)$, dato $a=mq+r, r
E comunque, a prescindere da tutto, mi sa che inizio una campagna contro l'uso del "si prova facilmente" nei testi di matematica
Che poi, volendo, considero:
$A$ l'insieme $a$ dei naturali minori di $m$ e primi con $m$;
$B$ l'insieme $b$ delle classi di congruenza modulo $m$ di interi primi con $m$.
Stabilisco $f:A \rightarrow B$ con $f$ che associa ad ogni elemento di $a \in A$ una ed una sola classe di congruenza modulo $b_m \in B \subseteq ZZ_m$.
La funzione è iniettiva perchè
$\forall a,a' in A$ se $a \ne a' \Rightarrow b=mq+a \ne mq+a'=b' \ \forall q \in ZZ$ con
$b \equiv_m a$ e $b' \equiv_m a'$ e $b_m = a_$, $b'_m = a'_m$. Inoltre $b$ e $b'$ sono primi con $m$ e dunque appartengono a $B$
Ma $0 <=a'
A questo punto $|A|=|B|$
$A$ l'insieme $a$ dei naturali minori di $m$ e primi con $m$;
$B$ l'insieme $b$ delle classi di congruenza modulo $m$ di interi primi con $m$.
Stabilisco $f:A \rightarrow B$ con $f$ che associa ad ogni elemento di $a \in A$ una ed una sola classe di congruenza modulo $b_m \in B \subseteq ZZ_m$.
La funzione è iniettiva perchè
$\forall a,a' in A$ se $a \ne a' \Rightarrow b=mq+a \ne mq+a'=b' \ \forall q \in ZZ$ con
$b \equiv_m a$ e $b' \equiv_m a'$ e $b_m = a_$, $b'_m = a'_m$. Inoltre $b$ e $b'$ sono primi con $m$ e dunque appartengono a $B$
Ma $0 <=a'
"algibro":
Si prova facilmente che per ogni naturale $ m>1 $, $ \varphi (m) $ è il numero delle classi di congruenza modulo $ m $ di interi primi con $ m $
A questo punto $|A|=|B|$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo