Rozwiazania kongruencji

[fa1thly]

Witam, mam następujące pytanie. Posiadam do rozwiązania układ 4 kongruencji:
\(\displaystyle{ \begin{cases}x \equiv 6(mod11) \\x \equiv 9(mod13) \\x \equiv 6(mod12) \\x \equiv 9(mod15) \end{cases}}\)
Zastanawiam się czy powyższy układ ma rozwiązanie gdyż 12 i 15 nie są względnie pierwsze. A może źle stawiam sytuacje i to ze nie są względnie pierwsze świadczy tylko o tym że nie mogę zastosować chińskiego twierdzenia o resztach?

Z góry dziękuje za odpowiedz

[Vax]

Zauważ, że

\(\displaystyle{ x \equiv 6\pmod{12} \\ \\ \iff \\ \\ \begin{cases} x \equiv 6\equiv 0\pmod{3}\\ x \equiv 6 \equiv 2\pmod{4} \end{cases}}\)

Oraz:

\(\displaystyle{ x \equiv 9\pmod{15} \\ \\ \iff \\ \\ \begin{cases}x\equiv 9 \equiv 0\pmod{3} \\ x \equiv 9 \equiv 4\pmod{5} \end{cases}}\)

Więc:

\(\displaystyle{ \begin{cases}x \equiv 6(mod11) \\x \equiv 9(mod13) \\x \equiv 6(mod12) \\x \equiv 9(mod15) \end{cases} \iff \begin{cases} x \equiv 0 \pmod{3} \\ x \equiv 2\pmod{4} \\ x \equiv 4\pmod{5} \\ x \equiv 6\pmod{11} \\ x \equiv 9\pmod{13} \end{cases}}\)

A tutaj już możesz zastosować chińskie twierdzenie o resztach

[fa1thly]

No i sprawa jasna Teraz to już proste. Jeszcze jedno pytanie. W takim razie kiedy układ kongruencji nie ma rozwiązania?

[Vax]

Jak masz kongruencje liniową \(\displaystyle{ ax \equiv b\pmod{c}}\), to ma ona rozwiązanie wtedy i tylko wtedy, gdy \(\displaystyle{ (a,c) \mid b}\). Mając układ kongruencji patrzymy, czy żadne dwie kongruencje nie prowadzą do sprzeczności, to znaczy, mając np:

\(\displaystyle{ \begin{cases} x \equiv 6\pmod{12}\\ x \equiv 8\pmod{21} \end{cases}}\)

Widzimy, że w szczególności z pierwszej kongruencji wynika \(\displaystyle{ x \equiv 6\equiv 0\pmod{3}}\) a z drugiej \(\displaystyle{ x \equiv 8 \equiv 2\pmod{3}}\), czyli jakby istniało takie x, byłoby \(\displaystyle{ 2 \equiv 0\pmod{3}}\), czyli sprzeczność Jeżeli w układzie kongruencji nie ma takiej sytuacji, to dane kongruencje rozbijasz tak jak w moim 1 poście i stosujesz chińskie twierdzenie o resztach

[fa1thly]

Dzięki wielkie Sprawa wyjaśniona. Jeśli jesteś w stanie to zerknij na temat z rozwiązaniami diofantycznymi, tam mam troszkę większy problem -- 20 maja 2012, o 14:30 --Wybaczcie że zawracam znów głowę ale mam pytanie co do samego rozwiązania. Próbuje rozwiązać metodą podana na Ważniaku i wychodzi mi tak:
\(\displaystyle{ n=3*4*5*11*13=8530\\
M_{1} = 2860\\
M_{2}= 2145\\
M_{3}=1716\\
M_{4}=780\\
M_{5}=660\\

2860y_{1}\equiv1(mod3)\\
y_{1}=2\\
2145y_{2}\equiv1(mod4)\\
y_{2}=1\\
1716y_{3}\equiv1(mod5)\\
y_{3}=1\\
780y_{4}\equiv1(mod11)\\
y_{4}=10\\
660y_{5}\equiv1(mod13)\\
y_{5}=4\\

x= \sum_{i}^{} a_{i}y_{i}M_{i} + kn\\
x=2860*4 + 2145 + 1716 + 100*780+40*660 + k*8530=119701+k*8530=281+k*8530}\)

Jednak otrzymany wynik nie spełnia równań. Gdzieś popełniłem błąd ale nie jestem w stanie odleźć gdzie. Nie jestem pewien czy dobrze podstawiam pod równanie końcowe.