Układ kongruencji?

niuka_25 · Post autor: **niuka_25** » 18 sty 2010, o 22:03

Jak rozwiązać układ kongruencji? Wiem, że w tej sytuacji podany układ należy sprowadzić do prostszej postaci, tak aby można było zastosować chińskie twierdzenie o resztach . . .
\(\displaystyle{ X\equiv9(mod10)}\)
\(\displaystyle{ X\equiv10(mod15)}\)
\(\displaystyle{ X\equiv11(mod12)}\)

BettyBoo · Post autor: **BettyBoo** » 18 sty 2010, o 22:36

Ano trzeba. Do tego służy własność:

\(\displaystyle{ NWD(m,n)=1\ \Rightarrow \ [\ a\equiv b\mod mn\ \Leftrightarrow \ (a\equiv b\mod m\ \wedge\ a\equiv b\mod n)]}\)

Rozpisujesz każde równanie na tyle, żeby uprościć do względnie pierwszych modułów.

Pozdrawiam.

niuka_25 · Post autor: **niuka_25** » 18 sty 2010, o 22:42

Otrzymałam cos takiego:
\(\displaystyle{ X\equiv9(mod2)}\)
\(\displaystyle{ X\equiv9(mod5)}\)
\(\displaystyle{ X\equiv10(mod3)}\)
\(\displaystyle{ X\equiv10(mod5)}\)
\(\displaystyle{ X\equiv11(mod3)}\)
\(\displaystyle{ X\equiv11(mod4)}\)

Po uproszczeniu otrzymuję:
\(\displaystyle{ X\equiv1(mod2)}\)
\(\displaystyle{ X\equiv4(mod5)}\)
\(\displaystyle{ X\equiv1(mod3)}\)
\(\displaystyle{ X\equiv0(mod5)}\)
\(\displaystyle{ X\equiv2(mod3)}\)
\(\displaystyle{ X\equiv3(mod4)}\)
W jaki sposób mam to dalej uprościć? Proszę o pomoc:)

BettyBoo · Post autor: **BettyBoo** » 18 sty 2010, o 22:51

To już koniec - popatrz, masz np w tym układzie dwa równania \(\displaystyle{ X\equiv0(mod5)\ \wedge\ X\equiv4(mod5)}\). Oczywiście niemożliwe jest, żeby znaleźć taki \(\displaystyle{ X}\) (wiadomo dlaczego?), wobec tego te dwa równania są sprzeczne, czyli cały układ jest sprzeczny.

Pozdrawiam.

niuka_25 · Post autor: **niuka_25** » 18 sty 2010, o 23:00

Chodzi o to, że:
z równania \(\displaystyle{ X\equiv0(mod5)}\) wynika, że 5|x. Z równania natomiast \(\displaystyle{ X\equiv4(mod5)}\) wynikałoby, że 5|x-4 a to jest niemożliwe, gdyż musiałaby istnieć liczba całkowita k taka, że x-4=5k. Zauważmy, że 5=qx, gdzie q jest liczbą całkowitą. Z tego wynika, że x-4=zx, dalej x=4/(1-z). Nie bardzo rozumiem:(

BettyBoo · Post autor: **BettyBoo** » 18 sty 2010, o 23:03

Chodzi o to, że równanie \(\displaystyle{ X\equiv0(mod5)}\) oznacza, że resztą z dzielenia \(\displaystyle{ X}\) przez 5 jest 0. Drugie równanie oznacza, że resztą z dzielenia \(\displaystyle{ X}\) przez 5 jest 4, a to jest oczywiście niemożliwe, bo reszta z dzielenia jest określona jednoznacznie.

Pozdrawiam.

niuka_25 · Post autor: **niuka_25** » 18 sty 2010, o 23:28

Mam jeszcze problem z jednym układem:
\(\displaystyle{ 5x\equiv1(mod12)}\)
\(\displaystyle{ 5x\equiv2(mod8)}\)
\(\displaystyle{ 7x\equiv3(mod11)}\)
Po przekształceniu:
\(\displaystyle{ x\equiv5(mod12)}\)
\(\displaystyle{ x\equiv2(mod8)}\)
\(\displaystyle{ x\equiv2(mod11)}\)
Pozbywając się kongruencji drugiej, tzn. \(\displaystyle{ x\equiv2(mod8)}\), otrzymujemy kolejno:
\(\displaystyle{ x\equiv5(mod12)}\)
\(\displaystyle{ x\equiv2(mod11)}\), dalej
x=5+12t,
\(\displaystyle{ 5+12t\equiv2(mod11)}\) \(\displaystyle{ \Leftrightarrow}\) \(\displaystyle{ t\equiv8(mod11)}\)\(\displaystyle{ \Leftrightarrow}\) t=8+11u.
x=5+12(8+11u)=101+132u, tak więc x=101+132u <- rozwiązanie ogólne podanego układu kongruencji. Dobrze to jest rozwiązane?

BettyBoo · Post autor: **BettyBoo** » 19 sty 2010, o 00:06

Kongruencje przekształciłaś dobrze, ale pojęcia nie mam, co Ty tu dalej zrobiłaś

Z pierwszej kongruencji masz m.in. \(\displaystyle{ x\equiv1(mod4)\ \Leftrightarrow \ x\equiv1(mod8)\ \vee\ x\equiv5(mod8)}\) i znowu sprzeczność z równaniem drugim.

Pozdrawiam.

niuka_25 · Post autor: **niuka_25** » 19 sty 2010, o 00:20

Skąd to się bierze?:>

BettyBoo · Post autor: **BettyBoo** » 19 sty 2010, o 00:31

Z własności podzielności. Skoro \(\displaystyle{ X}\) przy dzieleniu przez 4 daje resztę 1, to \(\displaystyle{ X=4k+1}\). Jeśli \(\displaystyle{ k=2t}\), to \(\displaystyle{ X=8t+1}\), jeśli \(\displaystyle{ k=2t+1}\), to \(\displaystyle{ X=8t+5}\), czyli wówczas \(\displaystyle{ X}\) daje resztę z dzielenia przez 8 równą 1 lub 5.

Pozdrawiam.

niuka_25 · Post autor: **niuka_25** » 19 sty 2010, o 00:42

Nie rozumiem zbytnio dlaczego tak to na końcu można rozpisać:(
Dzięki za wyjaśnienia:)

BettyBoo · Post autor: **BettyBoo** » 19 sty 2010, o 00:44

Czego nie zrozumiałaś?

Pozdrawiam.

niuka_25 · Post autor: **niuka_25** » 19 sty 2010, o 00:55

Czy każdą kongruencję z własności podzielności mogę sobie w taki spos rozpisywać jak Ty rozpisałas?:>

BettyBoo · Post autor: **BettyBoo** » 19 sty 2010, o 01:01

To jest zbyt ogólne pytanie, żebym mogła Ci odpowiedzieć jednoznacznie. Podaj jakiś przykład, to Ci powiem, czy dobrze.

Pozdrawiam.

niuka_25 · Post autor: **niuka_25** » 19 sty 2010, o 01:05

\(\displaystyle{ x\equiv9(mod2)}\)\(\displaystyle{ \Leftrightarrow}\)\(\displaystyle{ x\equiv9(mod4)}\)\(\displaystyle{ \vee}\)\(\displaystyle{ x\equiv10(mod4)}\). Dlaczego tam ma być lub?:>