Układ kongruencji mod

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
oszust001
Użytkownik
Użytkownik
Posty: 57
Rejestracja: 25 lut 2007, o 15:55
Płeć: Mężczyzna
Lokalizacja: Krasno
Podziękował: 1 raz

Układ kongruencji mod

Post autor: oszust001 »

Jak rozwiązać taka kongruencję?
\(\displaystyle{ \begin{cases} 3x^{2}+x\equiv0\ mod\ 5\\
2x+3\equiv 0\ mod\ 7\end{cases}}\)
rubik1990
Użytkownik
Użytkownik
Posty: 520
Rejestracja: 28 sty 2009, o 19:39
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 14 razy
Pomógł: 86 razy

Układ kongruencji mod

Post autor: rubik1990 »

Ja to robię w ten sposób :
Z pierwszego równania wyciągam \(\displaystyle{ x}\): \(\displaystyle{ x(3x+1)\equiv _{5}0 \Leftrightarrow x\equiv _{5}0 \vee 3x+1\equiv _{5}0}\)
Z drugiego równania mamy \(\displaystyle{ 2x+3\equiv _{7}0 \Leftrightarrow 2x\equiv _{7}-3 \Leftrightarrow 2x\equiv _{7}4 \Leftrightarrow x\equiv _{7}2}\).
Czyli musimy rozróżnić dwa przypadki:
1. \(\displaystyle{ x\equiv _{5}0 \wedge x\equiv _{7}2}\)
Z pierwszego równania wynika że \(\displaystyle{ x=5k, k\in\mathbb{Z}}\) a z drugiego \(\displaystyle{ x=7s+2, s\in\mathbb{Z}}\). Należy więc rozwiązać równanie diofantyczne \(\displaystyle{ 5k-7s=2}\). Rozwiązaniami tego równania są pary \(\displaystyle{ (k,s)=(6+7t,4+5t),t\in\mathbb{Z}}\). Stąd zaś wynika że \(\displaystyle{ x=5(6+7t)=7(4+5t)+2,t\in\mathbb{Z}}\)
2.\(\displaystyle{ 3x+1\equiv _{5}0 \Leftrightarrow 3x\equiv _{5}-1 \Leftrightarrow 3x\equiv _{5}9 \Leftrightarrow x\equiv _{5}3}\)
Dalej robimy tak samo. Powinno wyjść \(\displaystyle{ x=7(5t+3)+2=5(7t+4)+3, t\in\mathbb{Z}}\)

Ogólnie to założyłem że umiesz rozwiązywać równania diofantyczne postaci \(\displaystyle{ ax+by=c}\) gdzie \(\displaystyle{ a,b,c}\) są ustalone. Równanie to ma rozwiązanie wtedy i tylko wtedy gdy \(\displaystyle{ NWD(a,b)}\) dzieli \(\displaystyle{ c}\). Wtedy jeżeli para liczb \(\displaystyle{ (x_{0},y_{0})}\) jest rozwiązaniem tego równania to wszystkei rozwiązania dane są równaniami \(\displaystyle{ x=x_{0}+\frac{b}{NWD(a,b)}t}\), \(\displaystyle{ y=y_{0}-\frac{a}{NWD(a,b)}t}\) gdzie \(\displaystyle{ t\in\mathbb{Z}}\)
ODPOWIEDZ