Mam problem z jednym układem kongruencji:
\(\displaystyle{ 11x - 12y \equiv 13 \pmod{23}}\)
\(\displaystyle{ 7x + 5y \equiv 4 \pmod{23}}\)
Próbowałem już kilku metod jednak nie mogę wpaść na rozwiązanie.. mógłby mnie ktoś nakierować?
Dziękuję!
Rozwiązać układ kongruencji
-
- Użytkownik
- Posty: 85
- Rejestracja: 18 mar 2012, o 11:01
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 20 razy
- 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
Re: Rozwiązać układ kongruencji
Mnożąc pierwszą kongruencję stronami przez \(\displaystyle{ 7}\), a drugą przez \(\displaystyle{ 11}\), po czym odejmując stronami przekształconą pierwszą od drugiej, mamy \(\displaystyle{ 139y \equiv -47\pmod{23}}\), czyli po odpowiednich redukcjach modulo dwadzieścia trzy \(\displaystyle{ y\equiv 22\pmod{23}}\).
Analogicznie mnożąc pierwszą kongruencję stronami przez \(\displaystyle{ 5}\), a drugą przez \(\displaystyle{ 12}\), po czym dodając stronami, otrzymujemy, że \(\displaystyle{ 139x \equiv 113\pmod{23}}\), czyli znów po redukcjach nodulo dwadzieścia trzy dostajemy \(\displaystyle{ x \equiv 21\pmod{23}}\). Pozostaje jeszcze sprawdzenie, bo wykorzystywaliśmy implikacje, a nie równoważności.
Odpowiedź: \(\displaystyle{ x=23s+21, y=23t+22,\ s,t \in \ZZ}\)-- 23 lis 2017, o 18:00 --Możemy tak sobie beztrosko pomnożyć te kongruencje, ponieważ liczba \(\displaystyle{ 23}\) jest pierwsza, więc w szczególności jest względnie pierwsza z liczbami \(\displaystyle{ 5,7,11,12}\) przez które mnożymy stronami.
Analogicznie mnożąc pierwszą kongruencję stronami przez \(\displaystyle{ 5}\), a drugą przez \(\displaystyle{ 12}\), po czym dodając stronami, otrzymujemy, że \(\displaystyle{ 139x \equiv 113\pmod{23}}\), czyli znów po redukcjach nodulo dwadzieścia trzy dostajemy \(\displaystyle{ x \equiv 21\pmod{23}}\). Pozostaje jeszcze sprawdzenie, bo wykorzystywaliśmy implikacje, a nie równoważności.
Odpowiedź: \(\displaystyle{ x=23s+21, y=23t+22,\ s,t \in \ZZ}\)-- 23 lis 2017, o 18:00 --Możemy tak sobie beztrosko pomnożyć te kongruencje, ponieważ liczba \(\displaystyle{ 23}\) jest pierwsza, więc w szczególności jest względnie pierwsza z liczbami \(\displaystyle{ 5,7,11,12}\) przez które mnożymy stronami.