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!
zwykła kongruencja do rozwiązania
- leszczu450
- Użytkownik
- Posty: 4414
- Rejestracja: 10 paź 2012, o 23:20
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 1589 razy
- Pomógł: 364 razy
- yorgin
- Użytkownik
- Posty: 12762
- Rejestracja: 14 paź 2006, o 12:09
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 17 razy
- Pomógł: 3440 razy
zwykła kongruencja do rozwiązania
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}\)
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
- Użytkownik
- Posty: 4414
- Rejestracja: 10 paź 2012, o 23:20
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 1589 razy
- Pomógł: 364 razy
zwykła kongruencja do rozwiązania
yorgin, dałbyś mi może jakiś przykład żebym lepiej to widział? : )
- yorgin
- Użytkownik
- Posty: 12762
- Rejestracja: 14 paź 2006, o 12:09
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 17 razy
- Pomógł: 3440 razy
zwykła kongruencja do rozwiązania
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.
\(\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
- Użytkownik
- Posty: 4414
- Rejestracja: 10 paź 2012, o 23:20
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 1589 razy
- Pomógł: 364 razy
zwykła kongruencja do rozwiązania
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)}\)
\(\displaystyle{ 15 \equiv 1 (\mod 7) \\ 15x \equiv x (\mod 7)}\)