kongruencje, rozwiązanie krok po kroku

[bolt24]

Proszę o wskazówki jak krok po kroku rozwiązać następujące kongruencje:

a)

\(\displaystyle{ 4x+2\equiv _{15}8-4x}\)

b)

\(\displaystyle{ 2x-5\equiv _{9}5x+4}\)

c)

\(\displaystyle{ \begin{cases}6x-4y\equiv _{7}4\\ -5x+2y\equiv _{7}3\end{cases}}\)

[bartek118]

Pierwsza - mamy:
\(\displaystyle{ 8x - 6 \equiv_{15} 0 \\
8x \equiv_{15} 6}\)
Teraz należy znaleźć odwrotność \(\displaystyle{ 8}\) w \(\displaystyle{ \mathbb{Z}_{15}}\). Jest nią \(\displaystyle{ 2}\). Wobec tego mnożąc kongruencję stronami przez \(\displaystyle{ 2}\) mamy
\(\displaystyle{ x \equiv_{15} 12}\)

[bolt24]

Jak mam znaleźć odwrotność \(\displaystyle{ 8}\) w \(\displaystyle{ \mathbb{Z}_{15}\) ?

[bartek118]

Wykorzystując rozszerzony algorytm Euklidesa. Wiemy, że istnieją liczby \(\displaystyle{ k}\) i \(\displaystyle{ l}\) takie, że
\(\displaystyle{ 8k+15l = 1,}\)
co oznacza dokładnie tyle, że \(\displaystyle{ k}\) jest odwrotnością \(\displaystyle{ 8}\) w \(\displaystyle{ \mathbb{Z}_{15}}\). I właśnie to \(\displaystyle{ k}\) znajdujesz rozszerzonym algorytmem Euklidesa.