problem z CRT

[Kera]

Witam.
Mam problem z chińskim twierdzeniem o resztach, co zrobiłem nie tak.
\(\displaystyle{ x\equiv 1 \pmod {11}}\)
\(\displaystyle{ x\equiv 2 \pmod {23}}\)
\(\displaystyle{ x\equiv 3 \pmod {5}}\)
wyliczyłem że:
\(\displaystyle{ x=1 \cdot 115 \cdot 5 + 2 \cdot 55 \cdot 9 +3 \cdot 253 \cdot 3 \pmod {1265}}\)
\(\displaystyle{ x= 47}\)
co nijak nie pasuje, gdzie popełniłem błąd?

[Jan Kraszewski]

Pokaż jak liczyłeś.

JK

[PoweredDragon]

Nie rozumiem sposobu liczenia(może nie znam jakiejś dziwnej metody?)
Poniżej rozwiązanie, nie sprawdzaj go od razu, później sobie z nim wynik możesz sprawdzić

Ukryta treść:    

Z pierwszego:
\(\displaystyle{ x = 1+11i}\)
\(\displaystyle{ 1+11i \equiv_5 3}\), z czego wynika, że \(\displaystyle{ \min (i) = 2}\)
\(\displaystyle{ x \equiv_{55} 23}\)

Dalej robisz \(\displaystyle{ 23+55k \equiv_{23} 2}\) - na razie opuszczamy 23, ale potem musimy o nim pamiętać!
\(\displaystyle{ 55 \equiv_{23} 9}\)
\(\displaystyle{ 55k \equiv_{23} 2 \Rightarrow 9k \equiv_{23} 2}\)
Szukasz i znajdujesz \(\displaystyle{ \min (k) = 13}\)
\(\displaystyle{ 140 = 23+9 \cdot 13 \equiv_{23} 2 \Rightarrow 738 = 23+55 \cdot 13 \equiv_{23} 2}\)

\(\displaystyle{ x \equiv_{1265} 738}\)

Pokaż obliczenia, będzie nam łatwiej pomóc

[Kera]

skorzystałem ze wzoru Sun Zi ( chiński matematyk), z książki Teoria Liczb w Informatyce.
W najbliższym czasie podam jak to liczyłem.

-- 27 sty 2017, o 00:56 --

wzór:
\(\displaystyle{ x\equiv\sum_{i=1}^{n}a_{i}M_{i}M^{'}_{i} \pmod{m}}\)

gdzie:

\(\displaystyle{ m=m_{1}m_{2} \cdot \cdot \cdot m_{3}}\)

\(\displaystyle{ M_{i}= \frac{m}{m_{i}}}\)

\(\displaystyle{ M^{'}_{i}= M^{-1}_{i} \pmod{m_{i}}}\)

\(\displaystyle{ i=1,2,....,n}\)

poniżej jak liczyłem:

\(\displaystyle{ m=m_{1}m_{2}m_{3}= 11 \cdot 23 \cdot 5 =1265}\)

\(\displaystyle{ M_{1}= \frac{m}{m_{1}}= \frac{1265}{11}= 115}\)

\(\displaystyle{ M^{'}_{1}=M^{-1}_{1} \pmod{m_{1}} = 115^{-1}\pmod{11}= 5}\)

\(\displaystyle{ M_{2}= \frac{m}{m_{2}}= \frac{1265}{23}= 55}\)

\(\displaystyle{ M^{'}_{2}=M^{-1}_{2} \pmod{m_{2}} = 55^{-1}\pmod{23}= 9}\)

\(\displaystyle{ M_{3}= \frac{m}{m_{3}}= \frac{1265}{5}= 253}\)

\(\displaystyle{ M^{'}_{3}=M^{-1}_{3} \pmod{m_{3}} = 253^{-1}\pmod{5}= 3}\)

stąd:

\(\displaystyle{ x=a_{1}M_{1}M^{'}_{1}+a_{2}M_{2}M^{'}_{2}+a_{3}M_{3}M^{'}_{3} \pmod{m}}\)

\(\displaystyle{ x=1 \cdot 115 \cdot 5+2 \cdot 55 \cdot 9+3 \cdot 253 \cdot 3 \pmod{1265}= 47}\)

wynik wyszedł tylko że źle.

[Chewbacca97]

Źle policzyłeś \(\displaystyle{ M^{'}_{1}, M^{'}_{2}, M^{'}_{3}}\).

prawidłowo:    

\(\displaystyle{ M^{'}_{1} = 9 \\ M^{'}_{2} = 18 \\ M^{'}_{3} = 2}\)
Po podstawieniu do końcowego równania wynika, że \(\displaystyle{ x=1265k + 738, k\in \mathbb{Z}}\).

[Kera]

Chewbacca97nie mam pojęcia jak zgodnie ze wzorem wynikiem jest \(\displaystyle{ 9}\)
możesz go rozpisać?

\(\displaystyle{ M^{'}_{1}=M^{-1}_{1} \pmod{m_{1}} = 115^{-1}\pmod{11}= 9}\)

[Jan Kraszewski]

Ja bym się raczej zapytał, skąd wytrzasnąłeś

\(\displaystyle{ 115^{-1}\pmod{11}= \red 5}\)...

Bo podejrzewam, że pomyliłeś mnożenie z dodawaniem.

JK

[Chewbacca97]

Kera, chętnie pomogę, ale nie znam wzoru, z którego korzystałeś - zapisz go tutaj.

[Jan Kraszewski]

Kera podał ten wzór, ale niepoprawnie go zastosował, bo niepoprawnie wyznaczał elementy odwrotne.

JK

[Kera]

Matematyka nigdy mnie nie lubiła, ale czy ten post https://www.matematyka.pl/78980.htm
jest odpowiedzią na temat wyznaczania elementów odwrotnych?
Wybrałem Teorię Liczb bo jest najbardziej interesującą, a że traktuję ją jako hobby to pytam zamiast błądzić.

[Jan Kraszewski]

Matematyka nigdy mnie nie lubiła, ale czy ten post https://www.matematyka.pl/78980.htm
jest odpowiedzią na temat wyznaczania elementów odwrotnych?

Może być.

Po prostu algorytm Euklidesa i odwrotny algorytm Euklidesa. Z tym, że do CRT nie jest to niezbędne - Twój wzór może ładnie wygląda, ale rozwiązania nie skraca. Szybciej jest to zrobić wprost.

JK

[Kera]

Dzięki Jan Kraszewski i pozostałym chętnym za pomoc, ok kumam już.