Kongurencje problem

[Kanodelo]

Jak to rozwiązać?
1. \(\displaystyle{ 3x+31\equiv 15(mod47)}\)

\(\displaystyle{ 3x+31\equiv 15(mod47) \\
3x=31(mod47) \\
3x=47k-16 \\
141x=47(47k-16)}\)
i nie wiem co dalej

Albo to:
2.\(\displaystyle{ 3x\equiv 8 (mod13)}\)

\(\displaystyle{ 3x=8(mod13) \\
3x=13k-5 \\
13x-10x=13k+5 \\
-10x=13(k-x)+5 \\
-40x=13(4k-x)+20 \\
-x=13(4k-x)+20+39x \\
-x=13(4k+2x)+20}\)
I teraz nie wiem jak się pozbyć tego minusa.

Chyba że całkiem źle to robie

[Vax]

\(\displaystyle{ 3x+31 \equiv 15 (mod \ 47)}\)

\(\displaystyle{ 3x \equiv 31 (mod \ 47)}\)

Zauważamy, że \(\displaystyle{ x=26}\) spełnia daną kongruencje, skąd wynika, że:

\(\displaystyle{ x = 47n+26}\)

W 2 przykładzie podobnie, mamy:

\(\displaystyle{ 3x \equiv 8 (mod \ 13)}\)

Zauważając, że \(\displaystyle{ x=7}\) spełnia daną kongruencje otrzymujemy \(\displaystyle{ x=13n+7}\)

Jeżeli szukasz danego rozwiązania, możesz również ułożyć równanie diofantyczne, na przykładzie 1 mamy:

\(\displaystyle{ 3x \equiv 31 (mod \ 47)}\)

Szukamy takich całkowitych x,y, który by spełniały:

\(\displaystyle{ 3x = 47y+31}\)

Łatwo zauważyć, że dla \(\displaystyle{ y=1}\) prawa strona jest podzielna przez 3 i wychodzi \(\displaystyle{ x=26}\) tym samym otrzymujemy \(\displaystyle{ x=47n+26}\), można również wyznaczyć element odwrotny, \(\displaystyle{ b \equiv 3^{-1} (mod \ 47) \Rightarrow b=16}\) następnie mnożąc naszą kongruencje stronami przez kongruencje \(\displaystyle{ 16\equiv 16 (mod \ 47)}\) otrzymujemy:

\(\displaystyle{ 48x \equiv 496(mod \ 47) \Leftrightarrow x\equiv 26 (mod \ 47) \Leftrightarrow x = 47n+26}\)

Pozdrawiam.

[Kanodelo]

\(\displaystyle{ 3x+31 \equiv 15 (mod \ 47)}\)

\(\displaystyle{ 3x \equiv 31 (mod \ 47)}\)

Nie ogarniam czemu nagle z 15 zrobiło się 31.. Tu trzeba odjąć stronami to 31, więc tam nie powinno być -16?

[Vax]

Tak, ale zauważ, że:

\(\displaystyle{ -16 \equiv 31 (mod \ 47)}\)

Pozdrawiam.

[Kanodelo]

Masakra.. Czyli tak ajkby od lewej striony odjąć, a jak po prawej wychodzi minus, to trzeba dodać.. Może kiedyś to wreszcie skumam.

A to drugie, jak np nie zauważę że to akurat spełnia równanie, to nie da się jakimś prostrzym sposobem?

[Vax]

Pokazałem w poprzednim poście 2 szybsze sposoby Można ułożyć równanie diofantyczne, albo wyznaczyć element odwrotny tego, co stoi przy niewiadomej, a następnie pomnożyć przez niego naszą kongruencje otrzymując od razu rozwiązanie.

Pozdrawiam.