kongruencje liniowe z jedną niewiadomą
kongruencje liniowe z jedną niewiadomą
Zawsze można rozwiązać i zobaczyć, czy są rozwiązania. Jeśli chcemy tylko sprawdzić, czy są rozwiązania, to proponuję następujący sposób:
1. Każdą kongruencję \(\displaystyle{ ax\equiv b \pmod{p_1^{k_1}\cdot p_2^{k_2}\cdot\ldots\cdot p_l^{k_l}}}\) zamieniamy na układ \(\displaystyle{ l}\) kongruencji (modulo \(\displaystyle{ p_1^{k_1}}\), modulo \(\displaystyle{ p_2^{k_2}}\) itd.)
2. Dla każdej liczby pierwszej \(\displaystyle{ p}\) sprawdzamy, czy wszystkie otrzymane kongruencje modulo \(\displaystyle{ p^k}\) są zgodne, czyli wybieramy kongruencję z największym wykładnikiem i patrzymy czy pozostałe z niej wynikają, czy są z nią sprzeczne.
1. Każdą kongruencję \(\displaystyle{ ax\equiv b \pmod{p_1^{k_1}\cdot p_2^{k_2}\cdot\ldots\cdot p_l^{k_l}}}\) zamieniamy na układ \(\displaystyle{ l}\) kongruencji (modulo \(\displaystyle{ p_1^{k_1}}\), modulo \(\displaystyle{ p_2^{k_2}}\) itd.)
2. Dla każdej liczby pierwszej \(\displaystyle{ p}\) sprawdzamy, czy wszystkie otrzymane kongruencje modulo \(\displaystyle{ p^k}\) są zgodne, czyli wybieramy kongruencję z największym wykładnikiem i patrzymy czy pozostałe z niej wynikają, czy są z nią sprzeczne.
- 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
kongruencje liniowe z jedną niewiadomą
Można na to spojrzeć również przez pryzmat twierdzenia chińskiego o resztach. Pod pewnymi bardzo prostymi założeniami (parami względnie pierwsze moduły kongruencji) dostajemy istnienie rozwiązania.
Ale oczywiście trafna jest uwaga od KAMAZ, by najpierw przekształcić równania i/lub je uprościć.
Ale oczywiście trafna jest uwaga od KAMAZ, by najpierw przekształcić równania i/lub je uprościć.
-
- Użytkownik
- Posty: 613
- Rejestracja: 18 gru 2011, o 11:41
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów/Kraków
- Podziękował: 265 razy
- Pomógł: 5 razy
kongruencje liniowe z jedną niewiadomą
a moglibyście mi jeszcze napisać tak z grubsza co zrobić w tym wypadku:
\(\displaystyle{ \begin{cases} x \equiv 17 \left( mod 24\right) \\ x \equiv 11 \left( mod 18\right) \\ x \equiv 13 \left( mod 15\right) \end{cases}}\)
a co by było, gdybym 13 zmienił na 8?
bardzo proszę o pomoc, bo chciałbym to jak najlepiej zrozumieć przed egzaminem. Dzięki!
\(\displaystyle{ \begin{cases} x \equiv 17 \left( mod 24\right) \\ x \equiv 11 \left( mod 18\right) \\ x \equiv 13 \left( mod 15\right) \end{cases}}\)
a co by było, gdybym 13 zmienił na 8?
bardzo proszę o pomoc, bo chciałbym to jak najlepiej zrozumieć przed egzaminem. Dzięki!
-
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 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
kongruencje liniowe z jedną niewiadomą
\(\displaystyle{ 24=3\cdot 8, \mbox{NWD}(3,8)=1\\
\\
x \equiv 17\mod 24 \Rightarrow \\
x \equiv 17\mod 3 \wedge x\equiv 17\mod 8 \Rightarrow\\
x \equiv 2\mod 3 \wedge x\equiv 1 \mod 8}\)
Tak samo robisz ze wszystkimi warunkami, potem duble usuwasz, oraz usuwasz te kongruencje, które wynikają z innych.
\\
x \equiv 17\mod 24 \Rightarrow \\
x \equiv 17\mod 3 \wedge x\equiv 17\mod 8 \Rightarrow\\
x \equiv 2\mod 3 \wedge x\equiv 1 \mod 8}\)
Tak samo robisz ze wszystkimi warunkami, potem duble usuwasz, oraz usuwasz te kongruencje, które wynikają z innych.