Układ kongruencji

admi99 · Post autor: **admi99** » 19 cze 2007, o 17:28

Witajcie, proszę o pomoc w rozwiązaniu układu kongruencji :

\(\displaystyle{ \left\{\begin{array}{cc}x\equiv 10 & (mod \ 11)\\x\equiv 5 & (mod \ 15)\\x\equiv 3 & (mod \ 19)\end{array}}\)

kuch2r · Post autor: **kuch2r** » 19 cze 2007, o 17:38

z Chinskiego twierdzenia o resztach, powinno pojsc bez problemu
... o_resztach

admi99 · Post autor: **admi99** » 19 cze 2007, o 17:59

dziękuję,
wynik:
x = 725 + i * 3135

ro6erto · Post autor: **ro6erto** » 21 cze 2007, o 19:50

a takie pytanie co jeżeli moduły nie będą względnie pierwsze??

bondyros · Post autor: **bondyros** » 22 cze 2007, o 22:06

ro^etro ----- co jesli nie beda? a sprawdz na jakims przykladzie:P -- podpowiem Ci -- moze zademonstruje Ci na przykladzie :

x = 1 (mod 7)
x = 9 (mod 14)

z pierwszego dostajesz ze istnieje takie k, ze: x = 1 +7k
z drugiego dostajesz ze istnieje takie j, ze: x = 9 +14j
czyli 1 + 7k = 9 +14j, idac dalej 7k = 8 +14j czyli 7k = 8 (mod 14) brak rozwiazan poniewaz nie jest prawda ze: (7,14)|8 --- (7,14) = 7

na tym prostym przykladzie widzisz dlaczego musze byc wzglednie pierwsze, aby miec pewnosc ze rozwiazanie istnieje - po prsotu w ukladzie:

x=a1 (mod p1)
x=a2 (mod p2)
....
....
....
x=ak (mod pk)

musi byc spelnione:
dla kazdego i,j1 ) - chociazby x=7

ro6erto · Post autor: **ro6erto** » 22 cze 2007, o 22:23

aby istniało rozwiązanie moduły wcale nie muszą być względnie pierwsze!

bondyros · Post autor: **bondyros** » 23 cze 2007, o 12:36

ro6erto --- nie musza byc - wynika to chociazby z ostatniego przykladu ktory przytoczylem -- przeciez (4,2)=2>1 a rozwiazanie istnieje (niezrozumiales chyba uzasadnienia mego, albo nie zauwazyles zwrotu "MIEC PEWNOSC")...jesli "moduly" nie sa parami wzglednie pierwsze moze doprowadzic do sprzecznosci calego ukladu!! dlatego w chinskim twierdzeniu o resztach zalozono ze "moduly" sa wzglednie pierwsze --- aby miec pewnosc ze ow X istnieje