In tutte o quasi le lezioni/dispense si definisce la congruenza come $ a\equiv b \pmod{n} \iff a-b=kn $ con $k\in \mathbb{Z}$.
Ora, $ a\equiv b \pmod{n} \iff a\equiv b \pmod{-n} $ siccome al posto di $k$ posso mettere $-k$. La domanda:
entriamo nello specifico dei $n$ primi (non è strettamente necessario ma vabbé). Sia $n=7$ che è $\equiv 3 \pmod{4}$. $-n=-7\equiv 1 \pmod{4}$ (ho preso $n$ piccolo, ma volendo se ne può scegliere uno grande). Da un lato le proprietà modulo $n$ dovrebbero essere le stesse di $-n$, mentre dall'altro ci sono cose che cambiano. Esempio: $-1$ è residuo quadratico modulo $p$ se e solo se $p\equiv 1 \pmod{4}$. Dunque modulo $7$, $-1$ non è un residuo quadratico, mentre modulo $-7$ si.
Modulo -p
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
Modulo -p
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
---
"Chissa se la fanno anche da asporto"
Re: Modulo -p
In realtà anche modulo $-7$ non è residuo quadratico...
Infatti hai che $\left(\dfrac{-1}p\right)=1\iff |p|\equiv1\pmod4$
Perché? Basta ripensare alla dimostrazione... allora prendiamo un primo $p>0$; abbiamo $a^2\equiv-1\pmod p\iff ord_p(a)=4$; ma l'ordine moltiplicativo divide la phi, quindi dobbiamo avere $4\mid p-1$.
Ora, il passaggio cruciale è quella divisibilità... si dimostra dicendo che $a^{p-1}\equiv1\pmod p$ (con $a\not\equiv0$), e questo si fa per esempio prendendo i due insiemi $A=\{1,2,\dots,p-1\}$ e $aA=\{a,2a,\dots,(p-1)a\}$, dicendo che sono uguali modulo $p$ e uguagliando il prodotto; la divisibilità segue dalla minimalità dell'ordine moltiplicativo.
Dunque, vediamo ora cosa succede con $-p$: la cosa fondamentale è che anche qua $a^{p-1}\equiv1\pmod{-p}$, e all'esponente non c'è $p+1$ o altro, ma proprio $p-1=|-p|-1$, e questo si fa nello stesso identico modo, infatti $-p$ è primo e ha gli stessi residui di $p$. Quello che vorresti affermare è equivalente al dire appunto che $a^{p+1}\equiv1$. La cosa importante è QUANTE sono le classi di congruenza, e poco importa se sono modulo un primo positivo o negativo.
Detto in altre parole, l'ordine del gruppo $\mathbb Z/(-p)\mathbb Z^\ast$ è $p-1$, esattamente quanto quello di $\mathbb Z/p\mathbb Z^\ast$; anzi in realtà i due gruppi sono la stessa cosa!
Spero di essermi fatto capire
Infatti hai che $\left(\dfrac{-1}p\right)=1\iff |p|\equiv1\pmod4$
Perché? Basta ripensare alla dimostrazione... allora prendiamo un primo $p>0$; abbiamo $a^2\equiv-1\pmod p\iff ord_p(a)=4$; ma l'ordine moltiplicativo divide la phi, quindi dobbiamo avere $4\mid p-1$.
Ora, il passaggio cruciale è quella divisibilità... si dimostra dicendo che $a^{p-1}\equiv1\pmod p$ (con $a\not\equiv0$), e questo si fa per esempio prendendo i due insiemi $A=\{1,2,\dots,p-1\}$ e $aA=\{a,2a,\dots,(p-1)a\}$, dicendo che sono uguali modulo $p$ e uguagliando il prodotto; la divisibilità segue dalla minimalità dell'ordine moltiplicativo.
Dunque, vediamo ora cosa succede con $-p$: la cosa fondamentale è che anche qua $a^{p-1}\equiv1\pmod{-p}$, e all'esponente non c'è $p+1$ o altro, ma proprio $p-1=|-p|-1$, e questo si fa nello stesso identico modo, infatti $-p$ è primo e ha gli stessi residui di $p$. Quello che vorresti affermare è equivalente al dire appunto che $a^{p+1}\equiv1$. La cosa importante è QUANTE sono le classi di congruenza, e poco importa se sono modulo un primo positivo o negativo.
Detto in altre parole, l'ordine del gruppo $\mathbb Z/(-p)\mathbb Z^\ast$ è $p-1$, esattamente quanto quello di $\mathbb Z/p\mathbb Z^\ast$; anzi in realtà i due gruppi sono la stessa cosa!
Spero di essermi fatto capire
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)