Contare elementi di ordine due in Z/nZ
Ciao a tutti ragazzi!
mi sono imbattuto in un esercizio che non sono sicuro che ammetta soluzione, ma prima di darmi per vinto ho deciso di chiedere a voi!
Devo contare gli zeri del polinomio x^2-1 a coefficienti in Z/nZ, al variare di n nei naturali.
Tralasciando i casi in cui n è primo che sono banali, avete qualche idea?
Io sono solo riuscito a fare delle considerazioni: x^2-1 = 0 si scompone come (x-1)(x+1)=0, e quindi ho bisogno di contare tutti i divisori di zero "gemelli", cioè p = 2+q, ma a parte questa considerazione non so proprio come proseguire!
Grazie dell'aiuto!
mi sono imbattuto in un esercizio che non sono sicuro che ammetta soluzione, ma prima di darmi per vinto ho deciso di chiedere a voi!
Devo contare gli zeri del polinomio x^2-1 a coefficienti in Z/nZ, al variare di n nei naturali.
Tralasciando i casi in cui n è primo che sono banali, avete qualche idea?
Io sono solo riuscito a fare delle considerazioni: x^2-1 = 0 si scompone come (x-1)(x+1)=0, e quindi ho bisogno di contare tutti i divisori di zero "gemelli", cioè p = 2+q, ma a parte questa considerazione non so proprio come proseguire!
Grazie dell'aiuto!
Risposte
Scusa, sarò sciocco io ma non sono sempre due?
$ZZ/(nZZ) ~= ZZ_n$
Quindi le due soluzioni sono la classe dell'uno e del meno uno, no?!
$ZZ/(nZZ) ~= ZZ_n$
Quindi le due soluzioni sono la classe dell'uno e del meno uno, no?!
no, ad esempio in $ZZ_12$ risulta $5^2 = 1$
Ottimo! Sono sciocco, anche $7^2=1$ in $ZZ_12$
Questo però mi fa ragionare, mettiamoci in $ZZ_6$ questi valgono rispettivamente 1 e -1..
Trovato, per $ZZ_(4k)$ vanno bene anche $2k±1$, in $ZZ_(8k)$ vanno bene anche $4k±1, 2k±1$..
Però non funziona più con $ZZ_(16k)$, quindi ci limitiamo ai due casi di sopra; $4k±1, 2k±1$ salta col 32 e col 64, riprende col 128 e 256, non funziona col 512 e via cantando.. Credo non sia così facile trovare una regola generale..
Questo però mi fa ragionare, mettiamoci in $ZZ_6$ questi valgono rispettivamente 1 e -1..
Trovato, per $ZZ_(4k)$ vanno bene anche $2k±1$, in $ZZ_(8k)$ vanno bene anche $4k±1, 2k±1$..
Però non funziona più con $ZZ_(16k)$, quindi ci limitiamo ai due casi di sopra; $4k±1, 2k±1$ salta col 32 e col 64, riprende col 128 e 256, non funziona col 512 e via cantando.. Credo non sia così facile trovare una regola generale..
Andiamo per casi:
Caso 1 In $ZZ_p$ con $p$ primo ci sono esattamente due soluzioni
Caso 2 In $Z_{p^k}$ con $p>=3$ primo e $k>=2$ facciamo questo ragionamento: da $x^2 = 1$ (mod $p^k$) segue subito $x^2 = 1$ (mod $p$) e quindi $x = \pm 1$ (mod $p$) ovvero $x=mp \pm 1$ per qualche $m \in ZZ$. Allora
$(mp \pm 1)^2 = 1$ (mod $p^k$)
cioè
$m^2p^2 \pm 2mp + 1 = 1$ (mod $p^k$)
e quindi $m^2p^2 \pm 2mp = 0$ (mod $p^k$) da cui $p^k | mp(mp \pm 2)$ ovvero $p^{k-1}| m(mp \pm 2)$ ma siccome $p$ non divide $(mp \pm 2)$ allora $p^{k-1}| m$ cioè $m=sp^{k-1}$ per qualche $s \in ZZ$ e quindi $x=sp^k \pm 1$ cioè
$x= \pm 1$ (mod $p^k$)
Caso 3 In $ZZ_{2^k}$ distinguiamo 3 sottocasi. Se $k = 1$ c'è ovviamente l'unica soluzione $x=1$. Se $k= 2$ ci sono le soluzioni $x=1$ e $x=3$. Se $k >=3$ allora con un ragionamento del tutto analogo al caso 2 poniamo $x=2m \pm 1$ e senza ledere la generalità del discorso possiamo supporre $m$ pari, infatti se $m$ fosse dispari basterebbe notare che
$2m+1 = 2(m+1)-1$ ed $2m-1 = 2(m-1)+1$
Ora procedendo sempre come nel caso 2 arriviamo a dire che $2^{k-2} | m(m \pm 1)$ ma essendo $m$ pari e quindi $(m \pm 1)$ dispari concludiamo che $2^{k-2} | m$. Ricordando la posizione $x=2m \pm 1$ un rapido calcolo mostra che ci sono esattamente $4$ soluzioni $\pm 1$ ed $(2^{k-1} \pm 1)$
Caso generale Dato un intero $n$ sia $2^kp_1^{k_1}p_2^{k_2}...p_t^{k_t}$ la sua scomposizione in fattori primi. Sappiamo che $ZZ_n \cong ZZ_{2^k} xx ZZ_{p_1^{k_1}} xx ... xx ZZ_{p_t^{k_t}}$ In questo prodotto diretto un elemento $(x_0 , x_1,x_2,...,x_t)$ ha ordine moltiplicativo $2$ se e solo se ogni sua componente ha ordine due, quindi per quel che abbiamo detto nei casi 1-3 deduciamo che
se $k=0$ oppure $k=1$ allora ci sono $2^t$ soluzioni
se $k = 2$ ci sono $2^{t+1}$ soluzioni
se $k>=3$ ci sono $2^{t+2}$ soluzioni
Spero di non aver sbagliato niente.
Ciao ciao!
Caso 1 In $ZZ_p$ con $p$ primo ci sono esattamente due soluzioni
Caso 2 In $Z_{p^k}$ con $p>=3$ primo e $k>=2$ facciamo questo ragionamento: da $x^2 = 1$ (mod $p^k$) segue subito $x^2 = 1$ (mod $p$) e quindi $x = \pm 1$ (mod $p$) ovvero $x=mp \pm 1$ per qualche $m \in ZZ$. Allora
$(mp \pm 1)^2 = 1$ (mod $p^k$)
cioè
$m^2p^2 \pm 2mp + 1 = 1$ (mod $p^k$)
e quindi $m^2p^2 \pm 2mp = 0$ (mod $p^k$) da cui $p^k | mp(mp \pm 2)$ ovvero $p^{k-1}| m(mp \pm 2)$ ma siccome $p$ non divide $(mp \pm 2)$ allora $p^{k-1}| m$ cioè $m=sp^{k-1}$ per qualche $s \in ZZ$ e quindi $x=sp^k \pm 1$ cioè
$x= \pm 1$ (mod $p^k$)
Caso 3 In $ZZ_{2^k}$ distinguiamo 3 sottocasi. Se $k = 1$ c'è ovviamente l'unica soluzione $x=1$. Se $k= 2$ ci sono le soluzioni $x=1$ e $x=3$. Se $k >=3$ allora con un ragionamento del tutto analogo al caso 2 poniamo $x=2m \pm 1$ e senza ledere la generalità del discorso possiamo supporre $m$ pari, infatti se $m$ fosse dispari basterebbe notare che
$2m+1 = 2(m+1)-1$ ed $2m-1 = 2(m-1)+1$
Ora procedendo sempre come nel caso 2 arriviamo a dire che $2^{k-2} | m(m \pm 1)$ ma essendo $m$ pari e quindi $(m \pm 1)$ dispari concludiamo che $2^{k-2} | m$. Ricordando la posizione $x=2m \pm 1$ un rapido calcolo mostra che ci sono esattamente $4$ soluzioni $\pm 1$ ed $(2^{k-1} \pm 1)$
Caso generale Dato un intero $n$ sia $2^kp_1^{k_1}p_2^{k_2}...p_t^{k_t}$ la sua scomposizione in fattori primi. Sappiamo che $ZZ_n \cong ZZ_{2^k} xx ZZ_{p_1^{k_1}} xx ... xx ZZ_{p_t^{k_t}}$ In questo prodotto diretto un elemento $(x_0 , x_1,x_2,...,x_t)$ ha ordine moltiplicativo $2$ se e solo se ogni sua componente ha ordine due, quindi per quel che abbiamo detto nei casi 1-3 deduciamo che
se $k=0$ oppure $k=1$ allora ci sono $2^t$ soluzioni
se $k = 2$ ci sono $2^{t+1}$ soluzioni
se $k>=3$ ci sono $2^{t+2}$ soluzioni
Spero di non aver sbagliato niente.
Ciao ciao!
uhm, ci ragiono un po'!
Grazie comunque per le risposte ragazzi!
Grazie comunque per le risposte ragazzi!
Aspetta un attimo: 6=2*3, k=1 e t=2, e 21=3*7, k=0 e t=2, ma in Z/6Z ci sono 2 soluzioni e in Z/21Z ce ne sono 4!
Sbaglio?
Sbaglio?
$t$ è il numero di primi distinti diversi da $2$, infatti ho scitto $n= 2^kp_1^{k_1}p_2^{k_2}...p_t^{k_t}$ (guarda i pedici! 
) Faccio qualche esempio. quante sono le soluzioni in $Z_90$ ? Semplice $90 = 2 xx 3^2 xx 5$ quindi hai che l'esponente del 2 è $k = 1$ e ci sono due primi (3 e 5) diversi da 2, quindi in questo caso $t=2$ e ci sono $2^2 = 4$ soluzioni.
P.S. In $ZZ_6$ hai che $t=1$ perchè il $2$ non lo devi contare.
) Faccio qualche esempio. quante sono le soluzioni in $Z_90$ ? Semplice $90 = 2 xx 3^2 xx 5$ quindi hai che l'esponente del 2 è $k = 1$ e ci sono due primi (3 e 5) diversi da 2, quindi in questo caso $t=2$ e ci sono $2^2 = 4$ soluzioni. P.S. In $ZZ_6$ hai che $t=1$ perchè il $2$ non lo devi contare.
Hai ragione, ora mi torna! Grazie!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo