zwykła kongruencja do rozwiązania

[leszczu450]

Na ćwiczeniach rozwiązujemy kongruencje tego typu w następujący sposób:

\(\displaystyle{ 3x \equiv 4 (\mod 7) \\ NWD(3,7)=1 \\ 1|4 \\ 7 = 2 \cdot 3 +1 \\ 1 = 7 -2 \cdot 3 \\ 3x \equiv 4 (\mod 7) \\ -6x \equiv -8 (\mod 7 ) \\ -6 \equiv 1 (\mod 7) \\ -8 \equiv 6 (\mod 7) \\ x \equiv 6 (\mod 7)}\)

Nie za bardzo rozumiem co tutaj sie dzieje i czemu taki sposób na to jest.

Znacie może jakieś inne sposoby rozwiązywania kongruencji? Albo bylibyście w stanie wytłumaczyć mi ten? : )

Z góry dzięki!

[yorgin]

Ten opiera się na algorytmie Euklidesa i poszukiwaniu elementów odwrotnych w danym pierścieniu. Ja tej metody nigdy się nie nauczyłem, sam nie do końca ją rozumiem.

Mam za to prosty wariant: postaraj się wymnożyć kongruencję stronami przez taką liczbę \(\displaystyle{ k}\), by \(\displaystyle{ k\cdot 3x\equiv x\mod 7}\)

Czyli uprościsz kongruencję do postaci

\(\displaystyle{ x\equiv \ell \mod 7}\)

gdzie \(\displaystyle{ \ell=4\cdot k}\)

[leszczu450]

yorgin, dałbyś mi może jakiś przykład żebym lepiej to widział? : )

[yorgin]

Podam Ci na przykładzie tego.

\(\displaystyle{ 3x\equiv 4\mod 7 \qquad |\cdot 5\\
15x\equiv 20 \mod 7\\
x\equiv 6\mod 7}\)

Tyle, nie bawię się w żadnego Euklidesa. W razie dalszych pytań odpowiem znacznie później.

[leszczu450]

yorgin, skąd ta trzecia linijka? :>-- 30 mar 2013, o 18:19 --Aaaaa już wiem! Bo:
\(\displaystyle{ 15 \equiv 1 (\mod 7) \\ 15x \equiv x (\mod 7)}\)