Układ kongruencji

[SwiatoweSpiski]

Witam. Mam do rozwiązania następujący układ kongruencji:
\(\displaystyle{ \begin{cases}x\equiv1(mod 13)\\
x\equiv4(mod 15)\end{cases}}\)
Mam do tego rozwiązanie, także nie pytam o wynik, mianowicie chodzi mi o to, że dochodzę do momentu, w którym mam:
\(\displaystyle{ 13s\equiv1(mod 15) ;s=7}\)
Chciałbym wiedzieć, skąd wzięło się to s=7 ?

[kicaj]

To proste \(\displaystyle{ x\equiv 336 \mbox{ mod } 543}\)

[Chewbacca97]

kicaj, na pewno?

Mnie wyszło, że \(\displaystyle{ x \equiv 79 \pmod{195}}\) i chyba się zgadza!

SwiatoweSpiski, nie rozumiem czym u Ciebie jest \(\displaystyle{ s}\). Mógłbyś mi to wyjaśnić?

[Melisandre]

\(\displaystyle{ 7}\) to \(\displaystyle{ 13^{-1}}\) w pierścieniu \(\displaystyle{ \mathbb{Z} _{15}}\). Można to obliczyć korzystając z algorytmu Euklidesa.

[SwiatoweSpiski]

Chewbacca97, no właśnie chciałbym wiedzieć W każdym jednym przykładzie jest moment przed, tak jak tutaj, gdzie:
\(\displaystyle{ 13y\equiv3(mod 15)}\)
I dalej y zmienia się na s, po \(\displaystyle{ \equiv}\) liczba zmienia się na 1. Ogółem wygląda to tak w tym przykładzie:
\(\displaystyle{ 13y\equiv3(mod 15)\\
13s\equiv1(mod 15);s=7\\
13(3*7)\equiv3(mod 15)}\)
Ostatecznie: \(\displaystyle{ x=1+13y=1+13*21=274}\)
Skąd te s=7, skąd te 3 w nawiasie?
.//edit
Dobra, mam rozwiązanie. Należy zrobić tabelkę ai, qi, si i ti. Wynik w si, jest rozwiązaniem tej liczby s, natomiast druga liczba w nawiasie (3), to ta, która została zamieniona na 1 Można zamknąć.

[Mariusz M]

\(\displaystyle{ 15-13=2\\
13-6 \cdot 2=1\\
13-6\left(15-13 \right)=1\\
7 \cdot 13-6 \cdot 15=1\\
7 \cdot 13 \cdot 4-6 \cdot 15 \cdot 1=364-90=274 \\
x\equiv 79(\mod 195 )\\}\)