Congruenza quadratica

Salve a tutti.
Ultimamente è accaduto spesso che in alcuni esercizi dimostrativi andavo a parare in congruenze che non so risolvere, di questo tipo
$x^2\equiv a(modn)$
Purtroppo non conosco una regola generale per la diofantea che poi deriva.
Il criterio di Eulero mi è utile fino a un certo punto, perchè mi dice solo se $a$ è residuo quadratico o meno, ma non la famiglia di soluzioni di $x$.
Spero che possiate fornirmi un consiglio, una regola, una logica generica da seguire...

Grazie in anticipo, buona serata.
Stefano

[luca.barletta]

se hai $x^2-=y(modp)$ con $p$ primo, puoi trovare le radici quadrate in modo semplice solo se $p-=3(mod4)$:
$x-=y^((p+1)/4) (modp)$, se $y$ ammette radici quadrate modulo p allora queste sono $+-x$, altrimenti $-y$ ammette radici quadrate $+-x$.

Se hai $x^2-=y (modn)$, con $n$ composto, allora puoi usare il CRT per trovare tutte le radici.

Se hai voglia, prova a risolvere $x^2-=71(mod77)$

Ultima modifica di luca.barletta il 04/09/2007, 18:07, modificato 1 volta in totale.

$x-=y^((p+1)/4) (modp)$, se $y$ ammette radici quadrate modulo p allora queste sono $+-x$, altrimenti $-y$ ammette radici quadrate $+-x$.

Grazie per la risposta, mi è poco chiaro però questo pezzo.

Lavorando sull'esempio che mi hai proposto, abbiamo
$x^2\equiv5(mod11)$
$x^2\equiv1(mod7)$
Da quanto ho capito sembra che $y$ sia una specie di variabile ausiliaria
$x\equiv y^3(mod11)$
Forse intendevi dire "se x ammette radici quadrate mod p" invece che

se $y$ ammette radici quadrate modulo p

Scusami per la poca comprensione.

Ciao & Grazie

corretto, vedi sopra

Ok,grazie
Comunque la soluzione a
$x^2\equiv71(mod77)$ è
$x=15+77m$

Non sono sicuro di comprendere bene questa frase

$x-=y^((p+1)/4) (modp)$, se $y$ ammette radici quadrate modulo p allora queste sono $+-x$, altrimenti $-y$ ammette radici quadrate $+-x$.

Intendi dire: se il secondo membro ($y^((p+1)/4)$) ha esponente pari, allora le soluzioni sono $y=+-x$ ?
Posto l'esempio di prima, così magari mi fai vedere lì
$x^2\equiv5(mod11)$
$x^2\equiv1(mod7)$

$x\equiv5^3(mod11)$
$x\equiv1(mod7)$

Ultima cosa: puoi dirmi da dove discende tale algoritmo? Teorema, lemma, ecc.

Grazie per la disponibilità, ciao.
Stefano

Ok,grazie
Comunque la soluzione a
$x^2\equiv71(mod77)$ è
$x=15+77m$

Ne mancano altre 3 . Posta tutto lo svolgimento.

Non sono sicuro di comprendere bene questa frase

$x-=y^((p+1)/4) (modp)$, se $y$ ammette radici quadrate modulo p allora queste sono $+-x$, altrimenti $-y$ ammette radici quadrate $+-x$.

Intendi dire: se il secondo membro ($y^((p+1)/4)$) ha esponente pari, allora le soluzioni sono $y=+-x$ ?
Posto l'esempio di prima, così magari mi fai vedere lì
$x^2\equiv5(mod11)$
$x^2\equiv1(mod7)$

$x\equiv5^3(mod11)$
$x\equiv1(mod7)$

Se hai già studiato il simbolo di Legendre sai che
$(y/p)={(+1, " se " x^2-=y(modp) " ha soluzione"),(-1, " se " x^2-=y(modp) " non ha soluzione"):}$

quindi se $(y/p)=+1$ allora $+-x$ sono le radici quadrate di y modp, altrimenti se $(y/p)=-1$ hai anche che $-(y/p)=+1$ e quindi $+-x$ sono le radici quadrate di -y modp. Questo in generale.
Le radici $+-x$ si possono calcolare con quella formula che ho dato solo nel caso in cui $p-=3(mod4)$.
Nell'esempio:
$x^2-=5(mod11)$
$(5/11)=+1$, quindi $y-=+-5^3-=+-4 (mod11)$

Ultima cosa: puoi dirmi da dove discende tale algoritmo? Teorema, lemma, ecc.

Questa proposizione discende principalmente dal teorema di Fermat. Se vuoi ti posto il ragionamento.

Se hai già studiato il simbolo di Legendre sai che
$(y/p)={(+1, " se " x^2-=y(modp) " ha soluzione"),(-1, " se " x^2-=y(modp) " non ha soluzione"):}$

quindi se $(y/p)=+1$ allora $+-x$ sono le radici quadrate di y modp, altrimenti se $(y/p)=-1$ hai anche che $-(y/p)=+1$ e quindi $+-x$ sono le radici quadrate di -y modp. Questo in generale.
Le radici $+-x$ si possono calcolare con quella formula che ho dato solo nel caso in cui $p-=3(mod4)$.
Nell'esempio:
$x^2-=5(mod11)$
$(5/11)=+1$, quindi $y-=+-5^3-=+-4 (mod11)$

Ok, molto chiaro, ti ringrazio tanto.

Ne mancano altre 3. Posta tutto lo svolgimento.

Va bene.
Usando il teorema cinese del resto, giungiamo a
$x^2\equiv71(mod11)$
$x^2\equiv71(mod7)$
ovvero
$x^2\equiv5(mod11)$
$x^2\equiv1(mod7)$

Prendiamo la prima
Secondo quanto mia hai detto, risulta
$x\equiv+-5^3(mod11)->x\equiv+-4(mod11)$
Separandole
$x\equiv+4(mod11)$
$x\equiv-4(mod11)$
La prima restituisce
$x=-7-11alpha$ (1)
La seconda
$x=7-11beta$ (2)

La seconda congruenza del sistema è
$x^2\equiv1(mod7)$ che ammette soluzoni perchè 1 è residuo quadratico modulo 7
perciò
$x\equiv+-1(mod7)$
Sdoppiando
$x\equiv+1(mod7)$
$x\equiv-1(mod7)$
La prima mi dà
$x=1-7lambda$ (3)
La seconda
$x=-1-7gamma$ (4)

A questo punto, dal momento che mi dici che le soluzione devono essere 4, mi par d capire che devo "combinare la
(1) con la (3), poi con la (4), poi la (2) con la (3) e poi con la (4).
Confermi?

Questa proposizione discende principalmente dal teorema di Fermat. Se vuoi ti posto il ragionamento.

Va bene, se vuoi postami anche solo un link dove tratta la cosa, così magari posso generalizzare anche ai casi in cui
$p\equiv1(mod4)$

Ti ringrazio molto per la pazienza, buona giornata.
Stefano

A questo punto, dal momento che mi dici che le soluzione devono essere 4, mi par d capire che devo "combinare la
(1) con la (3), poi con la (4), poi la (2) con la (3) e poi con la (4).
Confermi?

confermo

Questa proposizione discende principalmente dal teorema di Fermat. Se vuoi ti posto il ragionamento.

Va bene, se vuoi postami anche solo un link dove tratta la cosa, così magari posso generalizzare anche ai casi in cui
$p\equiv1(mod4)$

ehm, il problema è che non ho link da consigliarti. Il caso $p-=1(mod4)$ è difficile da trattare, non ci sono formulette come quella che ho scritto.
Per farla breve il ragionamento è questo: supponi $y!in[0]_p$, allora per il th di Fermat si ha che
$x^4-=y^(p+1)-=y^2y^(p-1)-=y^2 (modp)$
visto anche come
$(x^2+y)(x^2-y)-=0 (modp)$, cioè $x^2-=+-y(modp)$.
Pertanto almeno uno tra $y$ e $-y$ è un quadrato modp.
Se supponi che entrambi $+-y$ siano quadrati modp, ossia $y-=a^2$ e $-y-=b^2$, allora $-1-=(a/b)^2$ (la frazione è da intendersi sempre in modp) il che significa che -1 è un quadrato modp: ciò è impossibile quando $p-=3(mod4)$. Segue che solo uno tra $y$ e $-y$ ha una radice quadrata modp.

Ti ringrazio.
L'ultimo post me lo leggo bene appena torno, dato che sto per uscire.
L'ho letto rapidamente, e ti chiedo una cosa, forse sciocca: il teorema di Fermat che citi, non ho ben capito qual'è, cercando rapidamente su google (anche perchè sono molti).
Il piccolo? L'Ultimo? Eulero-Fermat?
Scusa, ma devo saperlo
Grazie ancora, ciao.
Stefano

Mi riferisco a $y^(p-1)-=1 (modp)$