zastosowanie symbolu Legendre'a

[wiosna]

Dla jakich liczb pierwszych \(\displaystyle{ p}\) kongruencja \(\displaystyle{ x ^{2}\equiv7(mod p)}\) ma rozwiązanie?

[max]

Tutaj nie mam prostszego pomysłu niż skorzystać z prawa wzajemności reszt kwadratowych obliczając reszty kwadratowe modulo 7 i otrzymując 6 układów dwóch kongruencji o modułach \(\displaystyle{ 7, 4}\) i z chińskiego tw o resztach przerabić je na kongruencje modulo \(\displaystyle{ 28.}\)

Dokładniej chodzi o to, że z prawa wzajemności reszt kwadratowych mamy dla \(\displaystyle{ p > 2}\) (jeśli \(\displaystyle{ p = 2,}\) to \(\displaystyle{ 7\equiv 1 \equiv 1^{2}\pmod{2}}\)):
\(\displaystyle{ \left(\frac{7}{p}\right)\cdot \left(\frac{p}{7}\right) = (-1)^{\frac{(p-1)(7-1)}{4}} = (-1)^{\frac{p-1}{2}} = \begin{cases}1, \ p\equiv 1\pmod{4} \\ -1, \ p\equiv 3\pmod{4}\end{cases}}\)
Z drugiej strony resztami kwadratowymi modulo \(\displaystyle{ 7}\) są \(\displaystyle{ 1, 4, 2}\) więc:
\(\displaystyle{ \left(\frac{p}{7}\right) = \begin{cases}1, \ p \equiv 1, 2, 4\pmod{7}\\ -1, \ p\equiv 3, 5, 6\pmod{7}\end{cases}}\)
Nas interesuje sytuacja gdy \(\displaystyle{ 7}\) jest resztą kwadratową modulo \(\displaystyle{ p}\), czyli:
\(\displaystyle{ \left(\frac{7}{p}\right) = 1}\)
A z pierwszej równości będzie tak wtedy i tylko wtedy, gdy:
\(\displaystyle{ (-1)^{\frac{p-1}{2}} = 1 \wedge \left(\frac{p}{7}\right) = 1}\)
bądź
\(\displaystyle{ (-1)^{\frac{p-1}{2}} = -1 \wedge \left(\frac{p}{7}\right) = -1}\)
i z wypisanych wyżej równości dostajemy układy dwóch kongruencji o modułach \(\displaystyle{ 4, 7}\) i dalej pozostaje zapisać każdy taki układ jako jedną kongruencję o module \(\displaystyle{ 28.}\)

[Maciej87]

Można podrasować ten kawałek gdzie rozdzielamy na przypadki, układy kongruencji i obyć się bez:
\(\displaystyle{ 1=\left(\frac{-7}{p} \right) = \left(\frac{-1}{p} \right) \left( \frac{7}{p} \right)}\).
Z prawa wzajemności i rozpatrzenia możliwości \(\displaystyle{ p \equiv -1,1 \mod 4}\) wynika że dla \(\displaystyle{ p\not = 2}\) tak czy siak \(\displaystyle{ \left(\frac{-7}{p} \right) = \left( \frac{p}{7} \right)}\).
Dostajemy stąd po prostu \(\displaystyle{ p \equiv 1,2,4 \mod 7}\)

[max]

Chyba nie.

\(\displaystyle{ p := 3, \ x := 1}\)

i kongruencja zachodzi, ale

\(\displaystyle{ p\not\equiv 1,2,4\pmod{7}.}\)

[Maciej87]

Jasne. Myślałem nad \(\displaystyle{ \left( \frac{-7}{p} \right)}\) a tu jest przecież \(\displaystyle{ 7}\)...
Poplątałem, nie ten wątek.