Twierdzenie chińskie o resztach

Zbiór wzorów, definicji i najczęściej poruszanych problemów z Algebry.
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 5843
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków

Twierdzenie chińskie o resztach

Post autor: mol_ksiazkowy » 7 paź 2010, o 20:34

Twierdzenie (wersja klasyczna) Niech dane będą liczby \(\displaystyle{ m_1,...,m_n}\) parami względnie pierwsze. I niech \(\displaystyle{ M=m_1...m_n}\) oraz \(\displaystyle{ a_j}\) są to dowolne reszty i niech \(\displaystyle{ b_j}\) będą określone \(\displaystyle{ y=b_j}\) jako rozwiązanie kongruencji (*) \(\displaystyle{ y\frac{M}{m_j} \equiv 1 \ (mod \ m_j)}\) dla \(\displaystyle{ j=1,...,n}\) Wtedy ogólnym rozwiązaniem układu \(\displaystyle{ \begin{cases} x \equiv a_1 \ (mod \ m_1) \\x \equiv a_2 \ (mod \ m_2) \\...\\x \equiv a_{n-1} \ (mod \ m_{n-1}) \\x \equiv a_n \ (mod \ m_n) \end{cases}}\) jest \(\displaystyle{ x \equiv a_1b_1\frac{M}{m_1}+...+a_nb_n\frac{M}{m_n} \ (mod \ M)}\) Uwagi: Założenie iż liczby są parami względnie pierwsze jest istotne. Dzięki niemu liczby \(\displaystyle{ b_j}\) istnieją gdyż \(\displaystyle{ m_j}\)i \(\displaystyle{ \frac{M}{m_j}}\) są względnie pierwsze i kongruencje pomocnicze (*) mają rozwiązanie \(\displaystyle{ y}\). Istnieje najmniejsza liczba naturalna \(\displaystyle{ x}\), będąca rozwiązaniem układu (i można ją wprost obliczyć). Metoda graficzna Przykład (\(\displaystyle{ n=2}\)) \(\displaystyle{ \begin{cases} x \equiv 10 \ (mod \ 6) \\x \equiv 17 \ (mod \ 5) \end{cases}}\) Rysuje się kwadrat o boku \(\displaystyle{ 30}\) (tj. \(\displaystyle{ m_1m_2}\)), I na jego przekątnej ustawia kolejne liczby naturalne. Kwadrat dzieli się i rozcina na prostokąty \(\displaystyle{ 6 \times 5}\) (bo \(\displaystyle{ m_1=6, \ m_2=5}\)), które następnie nakłada się na siebie uzyskując macierz \(\displaystyle{ M}\). Wyszukuje się liczby \(\displaystyle{ c_1 \in \{ 1,2,3,4,5,6 \}}\) takiej że \(\displaystyle{ c_1 \equiv 10 \ (mod \ 6)}\) oraz \(\displaystyle{ c_2 \in \{ 1,2,3,4,5 \}}\) takiej że \(\displaystyle{ c_2 \equiv 17 \ (mod \ 5)}\), tj. \(\displaystyle{ c_1=4 , \ c_2=2}\). Element leżący na przecięciu wiersza o numerze \(\displaystyle{ c_1}\) i kolumny o numerze \(\displaystyle{ c_2}\) daje w \(\displaystyle{ M}\) rozwiązanie (\(\displaystyle{ M_{4,2}=22}\)) \(\displaystyle{ M=\left[\begin{array}{cccccc}1&7&13&19&25\\26&2&8&14&20\\21&27&3&9&15\\16&22&28&4&10\\11&17&23&29&5\\6&12&18&24&30\end{array}\right]}\) Uwagi: Dzięki założeniu iż \(\displaystyle{ m_1}\) i \(\displaystyle{ m_2}\) są względnie pierwsze żadne dwa elementy nie nałożą się i cała macierz \(\displaystyle{ M}\) zostanie wypełniona. Przykład \(\displaystyle{ \begin{cases} x \equiv 1 \ (mod \ 2) \\x \equiv 1 \ (mod \ 3)\\x \equiv 2 \ (mod \ 5)\\x \equiv 4 \ (mod \ 7) \end{cases}}\) Rozwiązanie Wystarczy rozwiązać kongruencje pomocnicze: \(\displaystyle{ b_1=1, \ b_2=1, \ b_3=3, \ b_4=4}\) a więc \(\displaystyle{ x \equiv 907 \equiv 67 \ (mod \ 210)}\). Można też \(\displaystyle{ x}\) obliczyć w w nieco inny sposób, tj. redukując ilość kongruencji (przez zastąpienie ich równoważnymi): w tym zadaniu mogłoby to wyglądać np. tak: \(\displaystyle{ \begin{cases} x \equiv 1 \ (mod \ 6) \\x \equiv 32 \ (mod \ 35) \end{cases}}\) stąd \(\displaystyle{ x=32+35m}\), i \(\displaystyle{ m \in \{0,1,2,3,4,5 \}}\). Dla \(\displaystyle{ m=0 \ x=32}\) tj. wynik błędny ale druga próba \(\displaystyle{ m=1, \ x=67}\) jest udana. Twierdzenie chińskie o resztach (wersja uogólniona (algebra)) Załóżmy, że \(\displaystyle{ A_1, ...,A_n}\) (\(\displaystyle{ n>1}\) ) są to ideały w pierścieniu przemiennym \(\displaystyle{ R}\) z jedynką, takie że jeśli \(\displaystyle{ i \neq j}\) to \(\displaystyle{ A_i+A_j=R}\) Wtedy jeśli \(\displaystyle{ b_1,...,b_n \in R}\) to istnieje \(\displaystyle{ b \in R}\) takie, że: \(\displaystyle{ b \equiv b_j \ (mod \ A_j)}\) dla \(\displaystyle{ j=1,...,n}\) oraz \(\displaystyle{ b}\) jest wyznaczone jednoznacznie modulo \(\displaystyle{ A_1 \cap ... \cap A_n}\) Jako wniosek uzyska się CRT (twierdzenie klasyczne) biorąc pierścień liczb całkowitych \(\displaystyle{ Z}\) i zbiory \(\displaystyle{ A_j}\) które tworzą wszystkie całkowite wielokrotności liczby \(\displaystyle{ j}\). Notka historyczna: Twierdzenie chińskie o resztach (ang. skrót CRT) jest jednym ze starszych odkryć z teorii liczb. Opisane zostało w księdze Mathematical Treatise in Nine Sections (z 1247 r.) napisanej przez Qin Jiushao, choć znane było Chińczykom jeszcze wcześniej; pisze o nim też Fibonacci w swym dziele Liber Abaci, ok. 1202 r. Sens jego brzmi: „Zawsze można znaleźć liczbę, która w dzieleniu przez zadany układ (parami względnie pierwszych liczb da zadany układ reszt.” Praktyczne zastosowanie CRT wynika ze sposobu, dzięki możliwościom jakie dają komputery, zakodowania dużych liczb przez pewien układ warunków z użyciem liczb dużo mniejszych.W programie Mathematica, istnieje funkcja ChineseRemainder\(\displaystyle{ [\{r1, r2, ...\}, \{m1, m2, ...\}]}\), której wynikiem jest najmniejsza liczba \(\displaystyle{ x}\), taka że \(\displaystyle{ x \equiv r_i \ (mod \ m_i)}\) dla \(\displaystyle{ i=1,..,n}\). Zadania do pracy własnej: (Uwaga: Prosze nie pisac tu rozwiazań ) 1. (Czech-Slovak, 1994r.) Wykazać, że istnieje rosnący ciąg liczb naturalnych \(\displaystyle{ a_n}\) mający tę własność iż przy dowolnym \(\displaystyle{ k \geq 0}\) w ciągu \(\displaystyle{ b_n=k+a_n}\) jest tylko skończona ilość wyrazów które są liczbami pierwszymi 2. Niech \(\displaystyle{ n}\) będzie dowolną liczbą całkowitą większą od zera. Wykaż że istnieje \(\displaystyle{ n}\) kolejnych dodatnich liczb całkowitych, które nie są potęgami liczb naturalnych o wykładniku większym od \(\displaystyle{ 1}\). 3. Znajdź najmniejszą liczbę naturalną \(\displaystyle{ n}\), taką, że liczby: \(\displaystyle{ \sqrt[5]{\frac{n}{143}},\sqrt[7]{\frac{n}{77}}, \sqrt[11]{\frac{n}{65}}, \sqrt[13]{\frac{n}{35}}}\) są całkowite. 4. Reszta przy dzieleniu liczby całkowitej \(\displaystyle{ m}\) przez \(\displaystyle{ 23}\) wynosi \(\displaystyle{ 22}\) , zaś reszta przy dzieleniu \(\displaystyle{ m}\) przez \(\displaystyle{ 17}\) to \(\displaystyle{ 13}\). Oblicz resztę przy dzieleniu liczby \(\displaystyle{ m}\) przez \(\displaystyle{ 391}\). Znajdź możliwie najmniejszą liczbę o tej własności 5. Dla dowolnie ustalonej liczby naturalnej obliczyć ile jest liczb całkowitych \(\displaystyle{ x}\) z przedziału \(\displaystyle{ <1,n>}\) takich, że \(\displaystyle{ x^3-x}\) jest podzielne przez \(\displaystyle{ n}\) 6. Niech \(\displaystyle{ a}\) i \(\displaystyle{ n}\) to będą liczby naturalne takie iż \(\displaystyle{ 1+a^2}\) dzieli się przez \(\displaystyle{ n}\). Wykazać, że istnieje liczba naturalna \(\displaystyle{ b}\), taka iż \(\displaystyle{ 1+b^2}\) dzieli się przez \(\displaystyle{ n(n^2+1)}\) 7*. (USA, 1997r.) Wykaż, że dla dowolnej liczby naturalnej \(\displaystyle{ n}\) istnieje jeden jedyny wielomian \(\displaystyle{ Q}\) o współczynnikach ze zbioru \(\displaystyle{ \{0,1,...,9 \}}\) taki, że \(\displaystyle{ Q(-2)=Q(-5)=n}\) 8*. Bez pomocy komputera znajdź \(\displaystyle{ x}\) takie, że: \(\displaystyle{ \begin{cases} x \equiv 1 \ (mod \ 2) \\x \equiv 4 \ (mod \ 5) \\x \equiv 2 \ (mod \ 7) \\x \equiv 6 \ (mod \ 19)\\x \equiv 33 \ (mod \ 83) \end{cases}}\) 9. Wyznacz najmniejszą możliwie czwórkę kolejnych liczb naturalnych, które dzielą się bez reszty kolejno przez \(\displaystyle{ 3,5,7,11}\) 10. Korzystając z CRT rozwiąż kongruencję \(\displaystyle{ 19x \equiv 1 \ (mod \ 140)}\)

ODPOWIEDZ