Ordine moltiplicativo

[doiug.8]

E' noto che $x^y \mod m= (x \mod m)^{y \mod ord(m)} \mod m$, dove $ord(m)$ è il massimo ordine moltiplicativo modulo m.
Allora $2012^{2012} \mod 20=12^{2012 \mod 4} \mod 20= 12^0 \mod 20=1$.
Ma Wolfram mi dice che il risultato è $16$. Dov'è l'errore?

[ma_go]

quello che scrivi è vero (in generale) solo per $x$ coprimo con $m$.

comunque, il tuo post è davvero mal scritto. eviterei di cercare di compattare tutto in una "formula", se poi questa risulta (come in questo caso) incomprensibile.
per scrivere la stessa cosa, io avrei detto:

è noto che se $a\equiv b \pmod{{\rm ord}(m)}$, allora $x^a \equiv x^b \pmod m$.

qui dai implicitamente per scontato che l'elevamento a potenza (intera! vedi sotto) è un'operazione sulle le classi di resto (quindi non serve scrivere "$x\mod m$"), e scrivi a parte che stai prendendo due interi che sono congrui modulo l'ordine di $m$.
per inciso, la scrittura $x^{y\mod {\rm ord}(m)}$ non ha senso matematicamente, perché non sai cosa vuol dire elevare una classe di resto (un intero, un laterale di un ideale) ad una classe di resto, e non ci si può trovare un senso in generale.

[doiug.8]

quello che scrivi è vero (in generale) solo per $x$ coprimo con $m$.

comunque, il tuo post è davvero mal scritto. eviterei di cercare di compattare tutto in una "formula", se poi questa risulta (come in questo caso) incomprensibile.
per scrivere la stessa cosa, io avrei detto:

è noto che se $a\equiv b \pmod{{\rm ord}(m)}$, allora $x^a \equiv x^b \pmod m$.

qui dai implicitamente per scontato che l'elevamento a potenza (intera! vedi sotto) è un'operazione sulle le classi di resto (quindi non serve scrivere "$x\mod m$"), e scrivi a parte che stai prendendo due interi che sono congrui modulo l'ordine di $m$.
per inciso, la scrittura $x^{y\mod {\rm ord}(m)}$ non ha senso matematicamente, perché non sai cosa vuol dire elevare una classe di resto (un intero, un laterale di un ideale) ad una classe di resto, e non ci si può trovare un senso in generale.

Grazie per le correzioni ma_go. Comunque la notazione non è mia, l'ho presa pari pari dalla dispensa di matematica olimpionica (pag. 27 se vuoi dare un'occhiata).
Un'ultima domanda: in generale se $x$ e $m$ non sono coprimi come si procede?

[ma_go]

se $x$ e $m$ non sono coprimi, si procede via teorema cinese, che ti permette di ridurti al caso in cui $m$ è una potenza di un primo. ti rimpallo la domanda: che succede quando $m = p^\alpha$?

p.s. quel punto della dispensa è scritto altrettanto male comunque non voleva essere un'accusa personale, solo un incentivo a migliorare anche l'aspetto espositivo del problem-solving: tieni (tenete) presente che vuoi (volete) essere capiti, quando risolvete un problema. prova a rileggere il tuo post originale tra qualche mese, e dimmi quanto ci impieghi a capire le formule..

[doiug.8]

se $x$ e $m$ non sono coprimi, si procede via teorema cinese, che ti permette di ridurti al caso in cui $m$ è una potenza di un primo. ti rimpallo la domanda: che succede quando $m = p^\alpha$?

Se $(x, p)>1$, ovvero $x=kp^ \beta$, $x^n \equiv 0 \pmod {p^\alpha}$, per $n \ge {\alpha \over \beta}$.

[ma_go]

Se $(x, p)>1$, ovvero $x=kp^ \beta$, $x^n \equiv 0 \pmod {p^\alpha}$, per $n \ge {\alpha \over \beta}$.

vero, ma puoi anche dire cosa succede per $n<\alpha/\beta$ (anche se nel caso del problema numerico in questione, quello che hai scritto è più che sufficiente). non è altrettanto facile da scrivere, ma può essere utile pensarci: scrivi pure se hai dubbi (chiunque scriva se ha dubbi).

[doiug.8]

Se $(x, p)>1$, ovvero $x=kp^ \beta$, $x^n \equiv 0 \pmod {p^\alpha}$, per $n \ge {\alpha \over \beta}$.

vero, ma puoi anche dire cosa succede per $n<\alpha/\beta$ (anche se nel caso del problema numerico in questione, quello che hai scritto è più che sufficiente). non è altrettanto facile da scrivere, ma può essere utile pensarci: scrivi pure se hai dubbi (chiunque scriva se ha dubbi).

Se $\alpha<\beta$, $n=0$.
Se $\alpha>\beta$ e $n\ge1$, $x^n \equiv hp^{n\beta} \pmod {p^\alpha}$.

Ho detto cose abbastanza ovvie, quindi mi sorge il dubbio che possa esserci qualcos'altro da notare che al momento non vedo...

[ma_go]

beh, c'è qualcosa di ancora non determinato: cos'è $h$ nella seconda formula?

[Claudio.]

Testo nascosto:

Come si dimostra che se $(a,m)=1$ allora esiste $ord_a(m)$?

[doiug.8]

beh, c'è qualcosa di ancora non determinato: cos'è $h$ nella seconda formula?

$h\equiv k^n \pmod {p^{\alpha-n \beta}}$. Ma questa è un'altra cosa ovvia...

Come si dimostra che se $(a, m)=1$ allora esiste $ord_a(m)$?

Il tuo voleva essere un hint o cosa? Comunque perchè scrivi $ord_a(m)$ e non $ord_m(a)$?

[Claudio.]

No no, era proprio una domanda, siccome era a tema con il topic non ne ho aperto un altro, ho scoperto solo adesso gli ordini moltiplicativi, avevo pensato a come potevo dimostrarlo ma non mi erano venute idee, però poi ho risolto.
Domani provo $ord_m(a)\mid ord(m)$
Per il fatto che ho invertito la a e la m mi sembra che ci sia un errore nella dipensa a pag 26...

[ma_go]

$h\equiv k^n \pmod {p^{\alpha-n \beta}}$. Ma questa è un'altra cosa ovvia...

ovvia, ma non detta. e comunque, a suon di cose ovvie, mi pare che abbiamo risolto il problema, no?

Comunque perchè scrivi $ord_a(m)$ e non $ord_m(a)$?

nelle sue dispense, gobbino usa effettivamente questa notazione (che io trovo estremamente sconveniente).