Rozwiązać układ kongruencji

[squeaky]

Mam taki układ równań, jak go rozwiązać?

\(\displaystyle{ \begin{cases} 3\equiv a(mod5) \\ 5 \equiv a(mod6) \end{cases}}\)

[Szemek]

mi wyszło takie rozwiązanie:
\(\displaystyle{ a \{ ..., 23, 53, 83, ... \}}\)
ogólnie: \(\displaystyle{ a=23+30k}\), gdzie \(\displaystyle{ k}\) należy do liczb całkowitych

[squeaky]

mi wyszło takie rozwiązanie:
\(\displaystyle{ a \{ ..., 23, 53, 83, ... \}}\)

Ale jak do tego dojść?

[Szemek]

wyliczyłem to na piechotę
pierwszy warunek układu spełniają wszystkie \(\displaystyle{ a}\), takie że: \(\displaystyle{ a\in \{..., 3,8,13,18,23,28,33,...\}}\)
drugi warunek układu spełniają wszystkie \(\displaystyle{ a}\), takie że: \(\displaystyle{ a\in \{..., 5,11,17,23,29,35,41,...\}}\)
w obu "zbiorach" znalazła się liczba \(\displaystyle{ 23}\),
zauważmy, że każde dwie kolejne liczby spełniające oba warunki będą się różnić od siebie o \(\displaystyle{ 5 6 = 30}\)

\(\displaystyle{ a=23+30k}\), gdzie \(\displaystyle{ k}\) należy do liczb całkowitych

[Wasilewski]

No to bardziej elegancko; mnożymy pierwszą kongruencję przez 6, a drugą przez 5:
\(\displaystyle{ \begin{cases} 18 \equiv 6a (mod \ 30) \\ 25 \equiv 5a (mod \ 30) \end{cases}}\)
Odejmujemy stronami:
\(\displaystyle{ a \equiv -7 \equiv 23 (mod \ 30)}\)

[squeaky]

Na piechotę to faktycznie łatwo ale ja myślałam o jakimś takim bardziej profesjonalnym sposobie :p
Bo gdyby za 3 i 5 podstawić x a pod a gdyby były liczby to wtedy umiem policzyć bo nam profesor podał jak to się liczy. Ale w drugą stronę już nie bardzo.
To co Wasilewski zrobił to chyba najlepszy sposób na rozwiązanie tego układu. Ale w tym układzie to już chyba nie bardzo, co?

\(\displaystyle{ \begin{cases} 1 \equiv a(mod4) \\ 8 \equiv a(mod9) \end{cases}}\)

Aha i dzięki za pomoc

[Wasilewski]

Też się da. Najpierw przemnożymy pierwszą przez 9 i dostaniemy:
\(\displaystyle{ 9 \equiv 9a (mod \ 36)}\)
Teraz zabawmy się drugą. Najpierw mnożenie przez 4:
\(\displaystyle{ 32 \equiv 4a (mod \ 36)}\)
A teraz mnożymy ją przez dwa, ale w inny sposób (tylko liczbę i resztę):
\(\displaystyle{ 64 \equiv 28 \equiv 8a (mod \ 36)}\)
I teraz odejmiemy to od pierwszej kongruencji:
\(\displaystyle{ -55 \equiv -19 \equiv 17 \equiv a (mod \ 36) \\
a \equiv 17 (mod \ 36)}\)

[squeaky]

A faktycznie, dzięki wielkie