Rozwiązać układ kongruencji

[matinf]

Witam,

Mam taki układ:

\(\displaystyle{ \begin{cases} x^2\equiv 1 (\mod 16) \\ x^2\equiv (\mod 49) \end{cases}}\)

Zupełnie nie wiem jak się do tego zabrać. Jak skutecznie wyznaczać wszystkie rozwiązania ?

Na oko widzę, że w obu przypadkach na pewno \(\displaystyle{ \pm 1}\), bo zwrotność kongruencji, ale inne ?

[robertm19]

A nie możesz policzyć wprost jakie rozwiązania pasują do równania pierwszego i skonfrontować je z równaniem drugim. Te które będą dobre dla obu będą rozwiązaniami.

[mariakow]

A w tym drugim równaniu to do czego przystaje \(\displaystyle{ x^2}\)?

[matinf]

do jedynki

[Qń]

Z drugiej kongruencji wynika, że:
\(\displaystyle{ 49|(x-1)(x+1)}\)
a ponieważ liczby w nawiasie różnią się o dwa, to nie mogą być jednocześnie podzielne przez \(\displaystyle{ 7}\), tak więc mamy tylko dwie możliwości:
\(\displaystyle{ x\equiv 1 \pmod{49}}\) lub \(\displaystyle{ x\equiv -1\pmod{49}}\)

Natomiast z pierwszej kongruencji wynika, że:
\(\displaystyle{ 16|(x-1)(x+1)}\)
Oczywiście będzie to prawdą, jeśli któryś nawias będzie podzielny przez \(\displaystyle{ 16}\), czyli gdy:
\(\displaystyle{ x\equiv 1 \pmod{16}}\) lub \(\displaystyle{ x\equiv -1\pmod{16}}\)
Nie jest natomiast możliwe by oba nawiasy dzieliły się przez \(\displaystyle{ 4}\), bo to liczby różniące się o dwa. Jest jednak możliwość, że jeden z nawiasów dzieli się przez \(\displaystyle{ 2}\), a drugi przez \(\displaystyle{ 8}\), ale nie przez \(\displaystyle{ 16}\). Nietrudno zauważyć, że daje nam to dwie nowe opcje:
\(\displaystyle{ x\equiv 9 \pmod{16}}\) lub \(\displaystyle{ x\equiv -9\pmod{16}}\)

Ostatecznie zatem wyjściowy układ kongruencji ma osiem rozwiązań, które można obliczyć z układów równań:
\(\displaystyle{ \begin{cases}
x\equiv a \pmod{16}\\
x\equiv b \pmod{49}\end{cases}}\)
gdzie \(\displaystyle{ a\in \{-9,-1,1,9\}}\) oraz \(\displaystyle{ b\in \{-1,1\}}\).

Q.

[matinf]

Ok, sprawa wygląda tak:
Należało rozwiązać równanie:

\(\displaystyle{ x^2 \equiv 1 (\mod 784)}\)
Rozumiem, że teraz każdy z 8-u układów rozwiązać z Chińskiego twierdzenia, a potem mamy już 8 rozwiązań tego równania. Tak ?

Potem wrzucę inne, ale ze swoją próbą (bo trudne to dla mnie jest dość)