+Steven+ ha scritto: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
luca.barletta ha scritto:$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.