Dubbi con le classi di resto

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
wall98
Messaggi: 167
Iscritto il: 27 mar 2013, 11:23
Località: Roma

Dubbi con le classi di resto

Messaggio da wall98 »

Se io ho $ n \not \equiv 1,-1,0 \pmod{p} $ e lo elevo $ p-1 $ volte a potenza (cioè $ n^1,n^2,n^3... $) genero tutte le classi di resto modulo p eccetto la classe di 0?

Nel caso: se ho $ n=2 $ accade qualcosa di specifico rispetto a un generico $ n $?

Posso generalizzare questa cosa modulo $ m $ non primo?
Il problema non è il problema, il problema sei tu.
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Dubbi con le classi di resto

Messaggio da karlosson_sul_tetto »

Rispondo per farmi perdonare lo strafalcione di prima.
In genere le potenze di $n \mod{p}$ ciclano secondo l'ordine di $n$ modulo $p$: infatti, dato che $n^{ord_p(n)}\equiv 1 \pmod{p}$, $n^{ord_p(n)+1}\equiv n^{ord_p(n)}\cdot n \equiv n \pmod{p}$ e cosi via. Inoltre se $n^a\equiv n^b \pmod{p}$ con $a,b<ord_p(n)$, allora segue che $a=b$ (cosa abbastanza facile da dimostrare). Dunque se per un certo $n$ $ord_p(n)=p-1$, allora tale $n$ viene chiamato generatore o "elemento primitivo" se vuoi fare il figo. Esiste un generatore per qualsiasi p primo.

Modulo $m$ generico: noto che non potrò mai ottenere tutte le classi di resto modulo $m$ non primo; ho due casi:
1) $n$ non è coprimo con $m$.
2) $n$ è coprimo con $m$.
Nel primo caso sia $d$ tale che $n=d\cdot r,m=d\cdot s, d>1$ (può essere il MCD ma non per forza).
$n^a\equiv d^a\cdot r^a\equiv x \pmod{m}$. Noi vorremmo che $x$ possa assumere qualsiasi valore modulo $p$. Riscrivendo la congruenza come $d^a\cdot r^a=x+m\cdot k=x+d\cdot s\cdot k$, $d$ deve per forza dividere $x$ (siccome divide il membro di sinistra), dunque x non può assumere tutti i valori.
Il secondo è simmetrico: $n^a=x+m\cdot k$, dato che vorremo che $x$ assumesse tutti i valori, dovrebbe funzionare anche per $x$ non coprimo con $m$: prendo $x$ in modo che $\exists d$ tale che $x=d\cdot y$ e $m=d\cdot l$. Dunque
da $n^a=x+m\cdot k$ sostituendo: $n^a=d\cdot y+d\cdot l\cdot k$. Ma ciò è assurdo siccome abbiamo presupposto che $n$ è coprimo con $m$.

Dunque che si fa? Modulo $m$ generico un generatore si definisce tale se prende tutte le classi di resto coprime con $m$. Un generatore esiste sempre se $m\in {2,4,p^k, 2p^k}$ con $p$ primo dispari e $k$ intero positivo.
Queste cose sono spiegate brevemente sulle schede olimpiche e in parecchi video dei senior basic.

Riguardo al caso particolare $n=2$, non mi pare che ci sia qualcosa di particolarmente interessante.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Dubbi con le classi di resto

Messaggio da fph »

Avevo questo vago ricordo che 2 è un generatore modulo $5^k$ per ogni $k$; confermate?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: Dubbi con le classi di resto

Messaggio da <enigma> »

Sì, si fa facilmente per induzione. Anzi, volendo si può dimostrare un fatto ancora più simpatico: se un numero genera modulo $p$ e modulo $p^2$ allora genera modulo ogni potenza di $p$. Avvalendosi di questo, non è neanche difficile caratterizzare gli $n$ per cui esiste un generatore modulo $n$!
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Rispondi