Witam wszystkich forumowiczów. Potrzebuje pomocy w jednym małym równaniu modularnym ^^ tzn. potrzebuje wyniku tego równania i uzasadnienia dlaczego taki a nie inny
Równanie:
ax\(\displaystyle{ \equiv_{n}}\)b
a = 13863
b = 12282
n = 32394
Drogą na około x wyszedł 10418 i jeżeli się nie pomyliłem to ten wynik jest dobry, ale sposób obliczenia tej wartości jest zły;) więc liczę na pomoc jakiegoś śmiałka, który ma 5 min.
thx
Proste równanie modularne;)
-
frej
Proste równanie modularne;)
Chodzi o to, że jak masz takie coś \(\displaystyle{ ax \equiv b (mod n)}\), to jak znajdziesz takie \(\displaystyle{ c}\), że \(\displaystyle{ ac \equiv 1 (mod n)}\) i pomnożysz początkowe równanie przez \(\displaystyle{ c}\) , to otrzymasz \(\displaystyle{ acx \equiv x \equiv bc (mod n)}\) i będziesz miał wynik. Cały szkopuł polega więc na znalezieniu elementu odwrotnego do \(\displaystyle{ a}\) w ciele \(\displaystyle{ Z_n}\). Pewnie o tym nie słyszałeś, nie?
to powinno Ci przybliżyć temat znajdowania elementów odwrotnych
A co do równania to możesz podzielić przez \(\displaystyle{ 3}\) i wtedy otrzymasz:
\(\displaystyle{ 4621x \equiv 4094 (mod 10798)}\). Znajdźmy teraz element odwrotny do \(\displaystyle{ 4621}\) w ciele \(\displaystyle{ Z_{10798}}\).
\(\displaystyle{ 4621p \equiv 1 (mod 10798)}\)
\(\displaystyle{ 4621p +10798q=1}\)
\(\displaystyle{ 10798=2\cdot 4621+1556}\)
\(\displaystyle{ 4621=2\cdot 1556 + 1509}\)
\(\displaystyle{ 1556=1\cdot 1509 + 47}\)
\(\displaystyle{ 1509=32\cdot 47+5}\)
\(\displaystyle{ 47=9\cdot 5 +2}\)
\(\displaystyle{ 5=2\cdot 2+1}\)
\(\displaystyle{ 1=5-2\cdot 2=5-2(47-5\cdot 9)=19\cdot 5 -2\cdot 47=19(1509 -32\cdot 47) -2\cdot 47= 19\cdot 1509 -610 47= 19\cdot 1509 -610 (1556-1509)= 629 1509 -610\cdot 1556=629(4621-2\cdot 1556)-610\cdot 1556=629\cdot 4621 -1868\cdot 1556=629\cdot 4621 -1868(10798-2\cdot 4621)=4365\cdot 4621 -1868\cdot 10798}\)
zatem \(\displaystyle{ 4621^{-1}= 4365 \quad Z_{10798}}\).
Wróćmy teraz do równania \(\displaystyle{ 4621x \equiv 4094 (mod 10798)}\). Obie strony pomnóżmy przez \(\displaystyle{ 4365}\).
\(\displaystyle{ 4621\cdot 4365 x \equiv 4094 4365 (mod 10798)}\). Korzystając z tego, że \(\displaystyle{ 4621\cdot 4365 \equiv 1 (mod 10798)}\) (bo to jest element odwrotny, który znaleźliśmy) mamy:
\(\displaystyle{ 4621\cdot 4365 x \equiv 4094 4365 (mod 10798) x \equiv 4094 4365 x\equiv 10418 (mod 10798)}\)
Voila
to powinno Ci przybliżyć temat znajdowania elementów odwrotnych
A co do równania to możesz podzielić przez \(\displaystyle{ 3}\) i wtedy otrzymasz:
\(\displaystyle{ 4621x \equiv 4094 (mod 10798)}\). Znajdźmy teraz element odwrotny do \(\displaystyle{ 4621}\) w ciele \(\displaystyle{ Z_{10798}}\).
\(\displaystyle{ 4621p \equiv 1 (mod 10798)}\)
\(\displaystyle{ 4621p +10798q=1}\)
\(\displaystyle{ 10798=2\cdot 4621+1556}\)
\(\displaystyle{ 4621=2\cdot 1556 + 1509}\)
\(\displaystyle{ 1556=1\cdot 1509 + 47}\)
\(\displaystyle{ 1509=32\cdot 47+5}\)
\(\displaystyle{ 47=9\cdot 5 +2}\)
\(\displaystyle{ 5=2\cdot 2+1}\)
\(\displaystyle{ 1=5-2\cdot 2=5-2(47-5\cdot 9)=19\cdot 5 -2\cdot 47=19(1509 -32\cdot 47) -2\cdot 47= 19\cdot 1509 -610 47= 19\cdot 1509 -610 (1556-1509)= 629 1509 -610\cdot 1556=629(4621-2\cdot 1556)-610\cdot 1556=629\cdot 4621 -1868\cdot 1556=629\cdot 4621 -1868(10798-2\cdot 4621)=4365\cdot 4621 -1868\cdot 10798}\)
zatem \(\displaystyle{ 4621^{-1}= 4365 \quad Z_{10798}}\).
Wróćmy teraz do równania \(\displaystyle{ 4621x \equiv 4094 (mod 10798)}\). Obie strony pomnóżmy przez \(\displaystyle{ 4365}\).
\(\displaystyle{ 4621\cdot 4365 x \equiv 4094 4365 (mod 10798)}\). Korzystając z tego, że \(\displaystyle{ 4621\cdot 4365 \equiv 1 (mod 10798)}\) (bo to jest element odwrotny, który znaleźliśmy) mamy:
\(\displaystyle{ 4621\cdot 4365 x \equiv 4094 4365 (mod 10798) x \equiv 4094 4365 x\equiv 10418 (mod 10798)}\)
Voila
Proste równanie modularne;)
Dzięki Ci zdziwię Cię, ale słyszałem o elemencie odwrotnym i nawet zaimplementowałem sobie rozszerzony algorytm Euklidesa i mam ten element od razu;) ale dzięki za wyjaśnienia, bo nie do końca wiedziałem jak go wyliczyć "normalnie", tak więc to co napisałeś nie poszło na marne ^^ Teraz tylko zaimplementować to wszystko i koniec ;] Jeszcze raz dzięki.
-
mac_23
- Użytkownik
- Posty: 62
- Rejestracja: 16 lis 2009, o 22:53
- Płeć: Mężczyzna
- Lokalizacja: polska
- Podziękował: 11 razy
Proste równanie modularne;)
Witam wszystkich!
Może mi ktoś powiedzieć jak mam rozwiązać takie zadnie \(\displaystyle{ 18x \equiv 33 (mod 15)}\)?
Z gory dzieki i pozdrawaim!
Może mi ktoś powiedzieć jak mam rozwiązać takie zadnie \(\displaystyle{ 18x \equiv 33 (mod 15)}\)?
Z gory dzieki i pozdrawaim!