układ kongruencji

[tralalala]

hej, mam taki układ
\(\displaystyle{ x\equiv 2 \pmod{3}}\)
\(\displaystyle{ x\equiv 2 \pmod{5}}\)
\(\displaystyle{ x\equiv 3 \pmod{8}}\)

i na początku spoko x=2+3k
podstawiam pod dwa pozostałe równania i ostatecznie mam

\(\displaystyle{ 3k\equiv 0 \pmod{5}}\)
\(\displaystyle{ 3k\equiv 1 \pmod{8}}\)

licze odwrotność modulo i mam z pierwszego 2 a z drugiego 3, mnożę i wychodzi:
\(\displaystyle{ k\equiv 0 \pmod{5}}\)
\(\displaystyle{ k\equiv 3 \pmod{8}}\) i ktoś pomoże co dalej?

[Mariusz M]

\(\displaystyle{ \begin{cases} x\equiv 2\left( \mod 15\right) \\ x\equiv 3\left( \mod 8\right) \end{cases}}\)

Stosujesz chińskie twierdzenie o resztach

\(\displaystyle{ 1=2 \cdot 8-1 \cdot 15}\)

\(\displaystyle{ x\equiv 2 \cdot 8 \cdot 2-1 \cdot 15 \cdot 3\left( \mod 120\right)\\
x\equiv 107 \left( \mod 120\right) \\
x=107+120k \qquad k\in \mathbb{Z}}\)

[tralalala]

wytłumaczysz mi skad ten \(\displaystyle{ x\equiv 2 \pmod{15}}\) bo na ćwiczeniach jakoś robiliśmy tak że wynik z pierwszego pod drugie i tak dalej, taką jakby redukcje a Ty robisz w jakiś inny sposób, jest krótszy więc jeśli możesz to proszę wytłumacz, może będzie prostszy:)

[Mariusz M]

\(\displaystyle{ x\equiv 2 \pmod{3}}\)
\(\displaystyle{ x\equiv 2 \pmod{5}}\)

Tutaj x daje taką samą resztę przy dzieleniu przez 3 co przy dzieleniu przez 5
a ponieważ \(\displaystyle{ \gcd\left( 3,5\right)=1}\) to x daje też taką samą resztę przy dzieleniu przez 15

\(\displaystyle{ 1=2 \cdot 3-1 \cdot 5}\)

Gdyby zastosować chińskie twierdzenie o resztach to mielibyśmy

\(\displaystyle{ x\equiv 2 \cdot 3 \cdot 2-1 \cdot 5 \cdot 2 \pmod{15}\\
x\equiv 2\pmod{15}\\}\)


\(\displaystyle{ 1=2 \cdot 3-1 \cdot 5}\)

Ta równość to największy wspólny dzielnik modułów wyrażony przez ich kombinację liniową

Rozszerzony algorytm Euklidesa różni się właśnie tym od algorytmu Euklidesa
że daje również kombinację liniową argumentów