Witam.
Mam problem z wyszukaniem kolejnych rozwiązań kongruencji
w zakresie \(\displaystyle{ x \in \ZZ, 0 \le x \le m-1}\)
kongruencja: \(\displaystyle{ -12x\equiv 6 \pmod{21}}\)
\(\displaystyle{ NWD(-12,21)=3}\) - zatem będą 3 rozwiązania
Pierwsze to będzie \(\displaystyle{ x\equiv3 \pmod{21}}\)
Proszę o wyjaśnienie jak wyznaczyć dwa kolejne, tak, aby mieściły się w przedziale.
Serdecznie pozdrawiam.
Kolejne rozwiązania kongruencji
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Kolejne rozwiązania kongruencji
\(\displaystyle{ -12 x \equiv 6\pmod{21} \Leftrightarrow -4x \equiv 2 \pmod{7} \Leftrightarrow 3x \equiv 2 \pmod{7}}\)
- myślę, że to dużo uprości.
Generalnie takie zadania wygodnie rozwiązuje się przy użyciu rozszerzonego algorytmu Euklidesa.
-- 16 wrz 2016, o 01:00 --
Przy pomocy rozszerzonego algorytmu Euklidesa znajdujemy element odwrotny do \(\displaystyle{ 3}\) w \(\displaystyle{ \ZZ_7*}\)tj. takie \(\displaystyle{ s \in \left\{ 1,2,3,4,5,6\right\}}\), że
\(\displaystyle{ 3s \equiv 1\pmod{7}}\) (tj. że istnieje takie całkowite \(\displaystyle{ t}\), iż \(\displaystyle{ 3s=7t+1}\)), a
następnie mnożymy kongruencję
\(\displaystyle{ 3x \equiv 2 \pmod{7}}\)
stronami przez wyżej wspomniane \(\displaystyle{ s}\).
- myślę, że to dużo uprości.
Generalnie takie zadania wygodnie rozwiązuje się przy użyciu rozszerzonego algorytmu Euklidesa.
-- 16 wrz 2016, o 01:00 --
Przy pomocy rozszerzonego algorytmu Euklidesa znajdujemy element odwrotny do \(\displaystyle{ 3}\) w \(\displaystyle{ \ZZ_7*}\)tj. takie \(\displaystyle{ s \in \left\{ 1,2,3,4,5,6\right\}}\), że
\(\displaystyle{ 3s \equiv 1\pmod{7}}\) (tj. że istnieje takie całkowite \(\displaystyle{ t}\), iż \(\displaystyle{ 3s=7t+1}\)), a
następnie mnożymy kongruencję
\(\displaystyle{ 3x \equiv 2 \pmod{7}}\)
stronami przez wyżej wspomniane \(\displaystyle{ s}\).