Teorema di aritmetica modulare sulla totiente di Eulero
Mi hanno detto che, se $MCD(a,n)=1$, allora $a^((\phi(n))/2)$ è congruo o a $1$ o a $-1$ modulo $n$
(dove $\phi(n)$ è ovviamente la funzione totiente di Eulero).
Si può dimostrare? Io ci sono riuscito solo nel caso abbastanza banale in cui $n$ è primo.
Conosco già il teorema di Eulero: $MCD(a,n)=1 \Rightarrow a^(\phi(n))\equiv1(mod n)$
perciò, se vi serve nella dimostrazione, potete usarlo senza dimostrarlo.
(dove $\phi(n)$ è ovviamente la funzione totiente di Eulero).
Si può dimostrare? Io ci sono riuscito solo nel caso abbastanza banale in cui $n$ è primo.
Conosco già il teorema di Eulero: $MCD(a,n)=1 \Rightarrow a^(\phi(n))\equiv1(mod n)$
perciò, se vi serve nella dimostrazione, potete usarlo senza dimostrarlo.
Risposte
Ricordo che nel corso di Crittografia si era dimostrato che $\phi(n)$ è dispari per ogni $n$, ma ora la dimostrazione non me la ricordo: dovrebbe venire direttamente dalla formula per calcolare la $\phi$, cioè
$\phi(ab)=\phi(a)\phi(b)$
per $(a,b)=1$... da applicare ai divisori di $n$.
Però a mio sostegno cito le parole di Ribenboim, the new book of Prime Number Records (pag. 37)
<1$, $m$ is odd, then $m$ is not a value of Euler's function.>>
Tradotto alla buona, "chiaramente $1= \phi(1)$ e se $m>1$ e $m$ è dispari, allora $m$ non è un valore della funzione di Eulero".
Da questo, segue che $\phi(n)$ è dunque pari. Chiamo $b= {\phi(n)}/2$ allora ho
$a^{2b} \equiv 1 (\text{mod} n)$
per il teorema di Eulero di cui parli nel tuo post ($2b=\phi(n)$ per costruzione) che equivale a $a^b \equiv \pm 1 ("mod" n)$.
Tuttavia manca da dimostrare che le due soluzioni sono uniche (avevo scritto una gran cavolata mi sa
).
Ora cerco in giro e vedo anche se il mio metodo è giusto, poi edito l'altro post.
Ok... sono stato un po' contorto, però alla fine sono pur sempre stato utile: ho uppato il tuo thread
$\phi(ab)=\phi(a)\phi(b)$
per $(a,b)=1$... da applicare ai divisori di $n$.
Però a mio sostegno cito le parole di Ribenboim, the new book of Prime Number Records (pag. 37)
<
Tradotto alla buona, "chiaramente $1= \phi(1)$ e se $m>1$ e $m$ è dispari, allora $m$ non è un valore della funzione di Eulero".
Da questo, segue che $\phi(n)$ è dunque pari. Chiamo $b= {\phi(n)}/2$ allora ho
$a^{2b} \equiv 1 (\text{mod} n)$
per il teorema di Eulero di cui parli nel tuo post ($2b=\phi(n)$ per costruzione) che equivale a $a^b \equiv \pm 1 ("mod" n)$.
Tuttavia manca da dimostrare che le due soluzioni sono uniche (avevo scritto una gran cavolata mi sa
).Ora cerco in giro e vedo anche se il mio metodo è giusto, poi edito l'altro post.
Ok... sono stato un po' contorto, però alla fine sono pur sempre stato utile: ho uppato il tuo thread
Grazie, Zero87.
Però c'è un passaggio che non mi torna:
Sono riuscito a dimostrare che questa affermazione è vera se $n$ è primo (cosa che mi ha permesso di completare la dimostrazione nel caso $n$ sia primo), ma non è vera in generale.
Esempio di controprova: $(7,12)=1$ e, benché $7$ non sia congruo a $\pm1(mod 12)$, $7^2=49\equiv1(mod 12)$.
Quindi le cose sono più complicate...
Però c'è un passaggio che non mi torna:
"Zero87":
ricordo che per $(a,n)=1$, $\pm 1$ erano le due uniche soluzioni (perché in altri casi $a^2 \equiv 1 (\text{mod} n)$ potrebbe avere più di due soluzioni se $(a,n) \ne 1$).
Sono riuscito a dimostrare che questa affermazione è vera se $n$ è primo (cosa che mi ha permesso di completare la dimostrazione nel caso $n$ sia primo), ma non è vera in generale.
Esempio di controprova: $(7,12)=1$ e, benché $7$ non sia congruo a $\pm1(mod 12)$, $7^2=49\equiv1(mod 12)$.
Quindi le cose sono più complicate...
"qasw":
Grazie, Zero87.
Però c'è un passaggio che non mi torna [...]
Lo so, me ne sono ricordato stamattina che non ha molto senso quello che avevo scritto (ora edito il messaggio sopra tra l'altro
).EDIT
Ho controllato una decina di libri differenti, ma tutti parlano di $n$ primo per quanto riguarda il teorema e l'unicità delle soluzioni, cioè che esistono solo $\pm 1$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo