kongruencja 2 przyklady

[kur4s]

\(\displaystyle{ 1647x\equiv1(mod788)

643x\equiv1(mod2000)

x nalezy do calkowitych}\)

[filip.wroc]

\(\displaystyle{ a \equiv b (mod c)}\)
znaczy tyle:
\(\displaystyle{ a/c + S = b/c +S}\)
rozpisujac to co masz:
\(\displaystyle{ 1647x\equiv1(mod788)

643x\equiv1(mod2000)

x nalezy do calkowitych}\)
dostajemy:
\(\displaystyle{ 1647x/788 + S = 1/788 + S

643x/2000 + S' = 1/2000 + S'}\)
S, S' to stale calkowite. W sumie one nas beda obchodzic najbardziej.
1/788 w dzieleniu calkowitym daje 0, podobnie 1/2000. Oba daja reszte 1, czyli S = S' =1.
Masz z tego:
\(\displaystyle{ 1647x/788 +1 =1

643x/2000 + 1 = 1}\)
i teraz to grzecznie liczysz. Moge sie mylic, bo jest pozno, moglem gdzies wstawic / zamiast *, etc. Mimo to wierze ze sobie poradzisz

[Qń]

Powyższa propozycja rozwiązania wydaje się być błędna, aczkolwiek głowy nie dam, bo jest napisana mało zrozumiale.

Z uwagi na \(\displaystyle{ 1647=2 \cdot 788 + 71}\) pierwsza kongruencja równoważna jest:
\(\displaystyle{ 71x \equiv 1 \mod 788}\)

Wystarczy w obu przypadkach użyć algorytmu Euklidesa w następujący sposób:

Przykład: \(\displaystyle{ 5x \equiv 1 \mod 13}\)

\(\displaystyle{ 13 = 2 \cdot 5 + 3 \\
5= 1 \cdot 3 + 2 \\
3 = 1 \cdot 2 +1}\)
Stąd: \(\displaystyle{ 1= 3-2 = 3- (5-3) = 2 \cdot 3 - 5 = 2\cdot (13 - 2\cdot 5) - 5 = 2 \cdot 13 - 5\cdot 5}\).
Tak więc modulo \(\displaystyle{ 13}\) mamy:
\(\displaystyle{ 1 \equiv (-5) \cdot 5 \equiv 8 \cdot 5}\)
więc rozwiązaniem kongruencji jest \(\displaystyle{ x=8}\).

Q.