układ kongurencji

[kasia00]

czy mógłby ktoś wyjaśnić mi po kroku jak rozwiązać taki układ:

\(\displaystyle{ x \equiv 2(mod 9)}\)
\(\displaystyle{ x \equiv 11 (mod 28)}\)
\(\displaystyle{ x \in [0,251]}\)

Dziękuję

[squared]

Skorzystaj z chińskiego twierdzenia o resztach.

[kasia00]

właśnie nie za bardzo wiem jak

Licząc na piechotę będzie to 83 i 236? Jak to będzie wyglądać w przypadku tego twierdzenia?

[squared]

212625.htm

Masz tutaj rozwiązany przykład, robimy analogicznie. Spróbuj rozpisać, a nie liczyć na "gotowca". Rób krok po kroku jak w podanym przykładzie.

[kerajs]

Licząc na piechotę będzie to 83 i 236?

Chyba nie, bo:
\(\displaystyle{ 83=2 \cdot 28+27\\
236=8 \cdot 28+12}\)
Raczej spełnia układ tylko liczba \(\displaystyle{ 11}\)

[kasia00]

Dochodzę do momentu
\(\displaystyle{ 9t = 9 mod 28}\)
Co dalej?

[Chewbacca97]

To może coś takiego?

\(\displaystyle{ \begin{cases} x \equiv 2 \pmod{9} \\ x \equiv 11 \pmod{28} \end{cases} \\ \begin{cases} 28x \equiv 56 \pmod{252} \\ 9x \equiv 99 \pmod{252} \end{cases} \\ \begin{cases} 28x \equiv 56 \pmod{252} \\ 27x \equiv 45 \pmod{252} \end{cases} \\ \\ 28x - 27x \equiv 56 - 45 = 11 \pmod{252}}\)

Zatem rozwiązania są postaci: \(\displaystyle{ 252k + 11}\), gdzie \(\displaystyle{ k\in \mathbb{Z}}\). Biorąc pod uwagę, że \(\displaystyle{ x\in \left[ 0;251\right]}\) to \(\displaystyle{ x = 11}\).

[kasia00]

To może coś takiego?

\(\displaystyle{ \begin{cases} x \equiv 2 \pmod{9} \\ x \equiv 11 \pmod{28} \end{cases} \\ \begin{cases} 28x \equiv 56 \pmod{252} \\ 9x \equiv 99 \pmod{252} \end{cases} \\ \begin{cases} 28x \equiv 56 \pmod{252} \\ 27x \equiv 45 \pmod{252} \end{cases} \\ \\ 28x - 27x \equiv 56 - 45 = 11 \pmod{252}}\)

Zatem rozwiązania są postaci: \(\displaystyle{ 252k + 11}\), gdzie \(\displaystyle{ k\in \mathbb{Z}}\). Biorąc pod uwagę, że \(\displaystyle{ x\in \left[ 0;251\right]}\) to \(\displaystyle{ x = 11}\).

Jak powstało to drugie przekształcenie?
\(\displaystyle{ \begin{cases} 28x \equiv 56 \pmod{252} \\ 9x \equiv 99 \pmod{252} \end{cases} \\ \begin{cases} 28x \equiv 56 \pmod{252} \\ 27x \equiv 45 \pmod{252} \end{cases} \\}\)

[Chewbacca97]

Po kolei wygląda to tak:
\(\displaystyle{ 27x \equiv 297 \equiv 45 \pmod{252}}\)

[kasia00]

Bardziej mi chodzi jak z \(\displaystyle{ 9x}\) robi się \(\displaystyle{ 27x}\)

[dec1]

Mnożysz obustronnie przez \(\displaystyle{ 3}\)

[kasia00]

Rozwiązuję analogicznie kolejny przykład:
\(\displaystyle{ \begin{cases} x \equiv -3 \pmod{7} \\ x \equiv 9 \pmod{11} \end{cases} \\}\)

i doszłam do :
\(\displaystyle{ \begin{cases} 11x \equiv -33 \pmod{77} \\ 7x \equiv63 \pmod{77} \end{cases} \\}\)

jak teraz "skrócić" tego x? Albo może ktoś pokaże mi jak by wyglądało zastosowanie na tym przykładzie chińskiego twierdzenia o resztach, bo tego też nie zbyt rozumiem?

[Chewbacca97]

Możesz pierwsze pomnożyć przez \(\displaystyle{ 5}\), drugie przez \(\displaystyle{ 8}\).

[Mariusz M]

\(\displaystyle{ 1=-3 \cdot 7+2 \cdot 11\\
-3 \cdot 7 \cdot 9+2 \cdot 11 \cdot \left( -3\right) \\
=-189-66\equiv -255+308\equiv 53\\
x\equiv\left(53 \mod 77\right)}\)

kasia00, przypomnij sobie rozszerzony algorytm Euklidesa
Oprócz dzielnika otrzymujesz także kombinację liniową modułów
W założeniu chińskiego twierdzenia o resztach masz że NWD modułów jest równe jeden
(dokładniej moduły są parami względnie pierwsze)