Chińskie twierdzenie o resztach

[TrzyRazyCztery]

Witam, mam taki problem, w miarę idzie mi rozwiązywanie podstawowych zadan z twierdzenia o resztach typu
\(\displaystyle{ \begin{cases} x \equiv 2\pmod{3}\\ x \equiv 3\pmod{4}\\ x \equiv 1\pmod{5} \end{cases}}\)
rozwiązuje je w taki sposob ze dla pierwszego szukam takiego i że
\(\displaystyle{ 2 + 3i \equiv 1\pmod{5}}\)

znajduje \(\displaystyle{ i = 3}\) i zapisuje
\(\displaystyle{ x \equiv 11 \pmod{3 \cdot 4}\\ 11+(3 \cdot 4)i\\i=0\\11 \mod 5 = 1}\)
Wiec rozwiazaniem jest \(\displaystyle{ 11+(3 \cdot 4 \cdot 5) \cdot k: k \in \ZZ?}\) a najmniejszym rozwiazaniem jest \(\displaystyle{ 11}\)
Czy to jest poprawne rozwiązanie? ponieważ mam problem ze zrobieniem tego dla takich danych jak
\(\displaystyle{ \begin{cases} 2x \equiv 1 \pmod{3}\\ 3x \equiv 1\pmod{4}\\ 4x \equiv 4\pmod{7} \end{cases}}\)

[Ponewor]

Nie wiem jakiego sposobu użyłeś do rozwiązania pierwszego układu, ale wynik otrzymałeś dobry, więc zakładam, że takie układy rozwiązywać umiesz. Drugi układ można łatwo sprowadzić do postaci przypominającej pierwszy układ.
Gdy masz równanie \(\displaystyle{ ax \equiv b \pmod{c}}\) i \(\displaystyle{ \left(a, \ c\right)=1}\), to możesz pomnożyć stronami razy \(\displaystyle{ a^{-1}}\) i otrzymasz:
\(\displaystyle{ x\equiv a^{-1}b \pmod{c}}\)
W przypadku równania \(\displaystyle{ 4x\equiv 3 \pmod{4}}\) należy pomnożyć je stronami razy \(\displaystyle{ 2}\) (bo \(\displaystyle{ 2\cdot 4 \equiv 1 \pmod{7}}\), czyli \(\displaystyle{ 4^{-1} \equiv 2 \pmod{7}}\)) i otrzymasz:
\(\displaystyle{ x\equiv 3 \cdot 2 \equiv 6 \pmod{7}}\)

[TrzyRazyCztery]

Przepraszam ale kompletnie nie zrozumiałem tego co napisałeś, skąd \(\displaystyle{ 4x\equiv 3 \pmod{4}}\)?

[VillagerMTV]

Jakiś błąd, bo \(\displaystyle{ 4 \pmod{4}}\) to \(\displaystyle{ 0}\), więc nie ma liczby, która da resztę \(\displaystyle{ 3}\).

Ale sens wypowiedzi jest w sumie zachowany.

[TrzyRazyCztery]

Tylko ja poprostu nie rozumiem dalej co z czego wynika

[VillagerMTV]

Dzięki podanej przez Ponewor instrukcji, może równania, których nie umiesz rozwiązać sprowadzić do takich, które umiesz (z samym \(\displaystyle{ x}\), a ni np. \(\displaystyle{ 3x}\))

Gdy masz równanie \(\displaystyle{ ax \equiv b \pmod{c}}\) i \(\displaystyle{ \left(a, \ c\right)=1}\), to możesz pomnożyć stronami razy \(\displaystyle{ a^{-1}}\) i otrzymasz:
\(\displaystyle{ x\equiv a^{-1}b \pmod{c}}\)

[TrzyRazyCztery]

ok, a co oznacza zapis \(\displaystyle{ \left(a, \ c\right)=1}\)?

[VillagerMTV]

Że ich\(\displaystyle{ NWD}\) jest równe \(\displaystyle{ 1}\), czyli są względnie pierwsze

[TrzyRazyCztery]

ok, zaczynam łapać tylko zastanawiam sie jeszcze np jak mam \(\displaystyle{ 2x \equiv 1 \pmod{3}}\)to \(\displaystyle{ 2}\) i \(\displaystyle{ 3}\) sa względnie pierwsze ale wyjdzie mi cos takiego \(\displaystyle{ x \equiv \frac{1}{2} \pmod{3}}\)a czy to jest poprawne? skoro twierdzenie mówi o liczbach całkowitych?

[Hydra147]

Nie chodzi o to, że \(\displaystyle{ a ^{-1}= \frac{1}{a}}\). \(\displaystyle{ a^{-1}}\) modulo \(\displaystyle{ c}\) to po prostu taka liczba całkowita, że \(\displaystyle{ a \cdot a^{-1} \equiv 1 \pmod{c}}\).

[TrzyRazyCztery]

aaaa to oznacza element odwrotny do a wzgledem tego mnożenia wiec np \(\displaystyle{ 2}\) sie łapie bo \(\displaystyle{ 2 \cdot_{3} 2 = 1}\) wiec mogę to zamienić na \(\displaystyle{ x \equiv 1 \cdot 2 \pmod{c}}\)?
Jesli tak to pytanko takie czy działanie ktore wykonuje po prawej stronie jest zwykłym mnożeniem czy mnożeniem modulo?

[VillagerMTV]

Wszystko jest modulo

[Ponewor]

Przepraszam ale kompletnie nie zrozumiałem tego co napisałeś, skąd \(\displaystyle{ 4x\equiv 3 \pmod{4}}\)?

Przepraszam, miało być \(\displaystyle{ 4x \equiv 3 \pmod{7}}\), moja literówka, bo dalej już dobrze pisałem. W przeciwnym razie \(\displaystyle{ \left(4, \ 4\right)=4>1}\) i wówczas tej operacji wykonać się nie da, a równanie jest sprzeczne.

[TrzyRazyCztery]

Więc
\(\displaystyle{ \begin{cases} 2x \equiv 1 \pmod{3}\\ 3x \equiv 1\pmod{4}\\ 4x \equiv 4\pmod{7} \end{cases}}\)
\(\displaystyle{ 2x \equiv 1 \pmod{3} \cdot 2}\)
\(\displaystyle{ 3x \equiv 1\pmod{4} \cdot 3}\)
\(\displaystyle{ 4x \equiv 4\pmod{7} \cdot 2}\)
\(\displaystyle{ \begin{cases} x \equiv 2 \pmod{3}\\ x \equiv 3\pmod{4}\\ x \equiv 1\pmod{7} \end{cases}}\)
\(\displaystyle{ x \equiv 11 \pmod{3 \cdot 4}}\) wiec \(\displaystyle{ x = 71}\) bo \(\displaystyle{ 71 \equiv 1 \pmod{4}}\)
Czyli ogolnym rozwiązaniem jest \(\displaystyle{ 71 + (3 \cdot 4 \cdot 7)\cdot k : k\in \mathbb{Z}}\) a najmniejszym dla dodatnich całkowitych jest 71. Czy to sie zgadza?

[Ponewor]

Tak.