Uklad kongruencji

Mikus933 · Post autor: **Mikus933** » 22 cze 2015, o 19:13

Prosze o rozwiazanie ukladu kongruencji
\(\displaystyle{ \begin{cases} x \equiv 1 \pmod{7} \\ x \equiv 3 \pmod{8} \end{cases}}\)
Mi wyszlo \(\displaystyle{ k=7u+5}\) i nie wiem czy dobrze. Prosze o pomoc

Medea 2 · Post autor: **Medea 2** » 22 cze 2015, o 19:42

Z tego układu łatwo widać, że \(\displaystyle{ x = 56 k + l}\), gdzie (wstępnie) \(\displaystyle{ l \in \{1,8,15,22,29,36,43,50\}}\), a do tego \(\displaystyle{ l \in \{3,11,19,27,35,43,51\}}\). Jak widać, \(\displaystyle{ 43}\) się powtarza.

mol_ksiazkowy · Post autor: **mol_ksiazkowy** » 25 cze 2015, o 13:04

Jak widać, 43 się powtarza.

Fajnie zapamiętac sobie też tę metode:
\(\displaystyle{ 7 \perp 8}\) (tj. są względnie pierwsze) więc znajdujemy ich "kombinację liniowa" która jest równa 1. np.
\(\displaystyle{ -1 \cdot 7 + 1 \cdot 8 =1}\)
I teraz domnażamy ją przez reszty:
\(\displaystyle{ 3(-1 \cdot 7) + 1(1 \cdot 8 )=-13}\). Jest to rozwiązanie (\(\displaystyle{ -13+ 7 \cdot 8 = 43}\))