residui quadratici modulo 2^n

[piever]

Un simpatico problemino:

Sia $ a\equiv 1 \pmod 8 $ un intero e $ n $ un intero positivo

Si dimostri che $ a $ è un residuo quadratico modulo $ 2^n $

Buona fortuna e buona Epifania!

[Thebear]

ok, scusa l'ignoranza (mi sto accostando da poco a TDN). ma cosa intendi per "residuo quadratico modulo 2^n"?
già che ci sono chiedo se qualcuno ha del materiale su cui lavorare per TDN, partendo dalle più semplici basi!
grazie

[SkZ]

http://it.wikipedia.org/wiki/Residuo_quadratico

[darkcrystal]

Sfatiamo questa strana leggenda per la quale i matematici, di notte, dormirebbero.

Consideriamo la funzione f: elevare al quadrato modulo $ 2^n $. Sia A il sottoinsieme di $ Z_{p^2} $ delle classi di resto dispari, e sia $ B=f(A) $

Sia infine C l'insieme delle classi mod $ 2^n $ di interi congrui ad 1 mod 8.

Se $ n \leq 2 $ si fa a mano, quindi suppongo $ n \geq 3 $.

Domanda: quand'è che capita che $ a^2=b^2 \pmod{2^n} $ per $ a, b \in A $? Se e solo se $ 2^n | (a-b)(a+b) $. Escludendo il caso idiota $ a=b $, si ha o che $ a=-b $, oppure, considerando come possono distribuirsi i fattori due, uno tra $ a+b $ e $ a-b $ è divisibile per $ 2^{n-1} $. Nel complesso, fissato $ a $, hanno la sua stessa immagine esattamente altri tre elementi: -a, $ 2^{n-1}+a $ e $ 2^{n-1}-a $.
Ora notiamo che $ a^2 \equiv 1 \pmod 8 \forall a \in A $, dunque B è un sottoinsieme di C; d'altra parte, $ |B|=2^{n-1}/4=2^{n-3} $, e |C| (i casi della vita!) è $ 2^{n-3} $. Perciò l'inclusione non è stretta, e B=C, cioè la tesi.

Buonanotte a tutti coloro che, inspiegabilmente, vanno a letto!

[piever]

Sia A il sottoinsieme di $ Z_{p^2} $ delle classi di resto dispari

Ora, i casi sono 2: o io ho completamente frainteso la tua soluzione, oppure sarebbe il caso di chiederti secondo quale notazione perversa $ Z_{p^2} $ sono le classi di resto modulo $ 2^n $? (Devo procurarmi a tutti i costi la mitica maglietta di Sam con la scritta "Your notation sucks")

La seconda cosa che viene da chiederti è: come mai il buffo ominide che ha fatto il miglior punteggio d'ammissione in normale tra i matematici, alle 2 di notte non trova di meglio da fare che risolvere (elegantemente, perché si tratta di un ominide di classe) problemi olimpici sull'oliforum???

Se proprio non hai sonno, cmq, Denis mi aveva spiegato cosa si può fare a Pisa a ogni ora della notte (anche se detto così suona ambiguo): mi sembra di ricordare che alle due il buon Denis suggeriva di prendersi un maritozzo alla crema al "Dolce Notte"..

Ciau, e fatti sentire!

[darkcrystal]

Innanzitutto lol; in secondo luogo, per sfortunate coincidenze burocratiche (chiamate Leggi dello Stato), pare che la Dolce Notte non possa più rimanere aperta fino a quell'ora, purtroppo; infine, yes, my notation sucks, ma *quella* notation è un'errore di battitura dovuto all'ora tarda e soprattutto al fatto che abbiamo, tra meno di una settimana, un'esame di aritmetica in cui gli $ Z_{p^2} $ si sprecano: accetta le mie più umili scuse e prendilo per uno $ Z_{2^n} $

Ciau

p.s. Mi scuso per il mezzo OT, ma ci sono stato trascinato... per non sprecare totalmente il messaggio, faccio presente che esiste anche una dimostrazione per induzione di questo fatto: chi si diverte a trovarla?

[FrancescoVeneziano]

Senza nulla togliere alla dimostrazione già postata, approfitto di questo problema per ricordare un po' di fatti utili sui generatori.
Sia p è un primo dispari e sia g un generatore modulo p, allora g o g+p è un generatore modulo $ p^2 $.
Sia p è un primo dispari e sia g un generatore modulo $ p^2 $, allora g è un generatore modulo $ p^n $ per ogni n.
Cosa succede quando al posto di un primo dispari prendiamo il 2? Non è più vero che $ \mathbb{Z}/2^n\mathbb{Z}^* $ è un gruppo ciclico, ma lo è quasi;i è isomorfo a $ \mathbb{Z}/2\mathbb{Z}\times\mathbb{Z}/2^{n-2}\mathbb{Z} $ e si possono individuare i generatori delle due componenti, infatti:
Dati n>2 e a dispari possiamo sempre scrivere $ a\equiv \pm 5^b \pmod {2^n} $ dove il segno è individuato in modo unico e b a meno di multipli di $ 2^{n-2} $.
A voi dimostrare questi fatti ed applicarli al problema iniziale.
(può essere utile anche questo lemma)

[g(n)]

La mia soluzione è molto simile a quella di darkcrystal, ma leggermente diversa, quindi la posto (anche perchè mi ha bruciato sul tempo, l'avevo risolto ma per mancanza di tempo non l'ho postato )

Voglio dimostrare che gli insiemi
$ \{1^2,3^2,...,(2^{n-2}-1)^2\} $ e $ \{1,9,...,2^{n}-7\} $
coincidono modulo $ 2^n $.

Come già detto $ (2k+1)^2\equiv 1\pmod 8 \forall k $.

Adesso supponiamo che 2 dispari diversi, entrambi compresi tra $ 1 $ e $ 2^{n-2}-1 $, abbiano lo stesso residuo quadratico, cioè che
$ (2k+1)^2\equiv (2j+1)^2 \pmod {2^n} $
per qualche k,j. Sviluppando si ottiene
$ 4k^2+4k\equiv 4j^2+4j \pmod {2^n} \Leftrightarrow k^2+k\equiv j^2+j \pmod{2^{n-2}} $
Questo è equivalente a
$ k^2+k-j^2-j\equiv 0\pmod{2^{n-2}}\Leftrightarrow (k-j)(k+j+1)\equiv 0 \pmod{2^{n-2}} $

A questo punto, $ k-j $ e $ k+j+1 $ hanno diversa parità, per cui si deve avere $ k-j\equiv 0 \pmod{2^{n-2}} $ oppure $ k+j+1\equiv 0 \pmod{2^{n-2}} $
Il primo caso implica $ k\equiv j \pmod{2^{n-2}} $.

Secondo caso: $ k+j+1\equiv 0 \pmod{2^{n-2}} $

Però si ha che $ 1\leq 2k+1,2j+1\leq 2^{n-2}-1 $ e quindi $ 0\leq k,j \leq 2^{n-3}-1 $, che implica $ 0\leq k+j+1\leq 2^{n-2}-1 $, ma quindi è impossibile soddisfare la congruenza.

A questo punto si conclude notando che i due insiemi hanno la stessa cardinalità e che la funzione è iniettiva, e dunque biiettiva.

[leonim]

Sia p è un primo dispari e sia g un generatore modulo p, allora g o g+p è un generatore modulo .
Sia p è un primo dispari e sia g un generatore modulo , allora g è un generatore modulo per ogni n

(1) Se $ g $ è un generatore mod p anche $ g+p $ è un generatore mod p. Si ha: $ ord_{p^2}(g)| \phi{(p^2)}=p(p-1) $. Quindi $ ord_{p^2}(g)=1,p-1,p,p(p-1) $. Se $ ord_{p^2}(g)=1 $ allora $ g\equiv1 $ (mod $ p^2) \Rightarrow g\equiv1 $ (mod $ p $). Assurdo. Se $ ord_{p^2}(g)=p $ allora $ g^p\equiv1 $ (mod $ p^2) \Rightarrow g^p\equiv g\equiv1 $ (mod $ p $). Assurdo. Quindi l'ordine è uguale a $ p-1 $ o $ p(p-1) $. Facendo lo stesso ragionamento con g+p concludiamo che il suo ordine mod p^2 può essere solo $ p-1 $ o $ p(p-1) $. Supponiamo che nessuno dei due sia un generatore mod $ p^2 $. Allora:
$ (g+p)^{p-1}\equiv (p-1)pg^{p-2}+g^{p-1} \equiv g^{p-1} $ (mod $ p^2 $).
$ (p-1)pg^{p-2}\equiv 0 $ (mod $ p^2 $).
Questo è impossibile quindi almeno uno dei due deve essere generatore.


(2) Lemma: $ a^p\equiv1 $ (mod $ p^k $) implica $ a\equiv1 $ (mod $ p^{k-1} $). Dim: vogliamo dimostrare che se $ p^k| (a-1)(a^{p-1}+\dots+1) $ allora $ (a^{p-1}+\dots+1) $ contiene esattamente un fattore $ p $. Si ha $ a^p\equiv1 $ (mod $ p^k $) $ \Rightarrow $ $ a^p\equiv a\equiv1 $ (mod $ p $). Posso quindi scrivere $ a=mp+1 $ per un certo $ m $. Sostituendo nell'espressione si ha:
$ (mp+1)^{p-1}+(mp+1)^{p-2}\dots +1\equiv (p-1)mp+1+(p-2)mp+1\dots+1 $ (mod $ p^2 $)
$ \equiv mp(\frac{(p-1)p}{2})+p \equiv mp^2(\frac{p-1}{2})+p\equiv p $ (mod $ p^2 $). Dunque l'espressione è multipla di $ p $ ma non di $ p^2 $, il che equivale alla tesi.

Ora mostriamo che se g è un generatore mod $ p^{k-1} $ allora lo è anche mod $ p^k $. Si ha: $ ord_{p^{k-1}}(g)|ord_{p^k}(g) $ e $ ord_{p^k}(g)|\phi(p^k) $. Si hanno quindi due possibilità per $ ord_{p^k}(g) $: $ p^{k-2}(p-1) $ o $ p^{k-1}(p-1) $. Supponiamo per assurdo che sia la prima. Si avrebbe:
$ g^{p^{k-2}(p-1)}\equiv (g^{p^{k-3}(p-1)})^p\equiv 1 $ (mod $ p^k $)
Grazie al lemma possiamo dire: $ g^{p^{k-3}(p-1)}\equiv 1 $ (mod $ p^{k-1} $). Applicandolo più volte arriviamo a concludere $ g^{p-1}\equiv 1 $ (mod $ p^2 $) ma questo è assurdo.

..E spero vivamente di non aver scritto cavolate