Twierdzenie chińskie o resztach

Zbiór wzorów, definicji i najczęściej poruszanych problemów z Algebry.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11265
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Twierdzenie chińskie o resztach

Post autor: mol_ksiazkowy »

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)}\)
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11265
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Re: Twierdzenie chińskie o resztach

Post autor: mol_ksiazkowy »

Przykład Rozwiązać układ kongruencji
\(\displaystyle{ \begin{cases}
x \equiv 1 \ (mod \ 2) \\
x \equiv 1 \ (mod \ 3) \\
x \equiv 4 \ (mod \ 5) \end{cases}}\)


Rozwiązanie
Jeśli \(\displaystyle{ x=6k+1=5n+4}\), to \(\displaystyle{ k \equiv 6k \equiv 3 \ (mod \ 5)}\) tj. \(\displaystyle{ x= 30m+19}\)

Zadanie 11
Udowodnić, że
i) jeśli \(\displaystyle{ m}\) jest dowolną liczbą naturalną, to istnieje ciąg \(\displaystyle{ m}\) kolejnych liczb naturalnych, z których żadna nie jest potęgą liczby naturalnej o wykładniku większym od \(\displaystyle{ 1}\)
Ukryta treść:    
ii) dowolny rosnący ciąg arytmetyczny liczb całkowitych zawiera dowolnie długie podciągi kolejnych wyrazów, w których nie ma liczb pierwszych

Zadanie 12. Rozwiązać układ
\(\displaystyle{ \begin{cases}
x \equiv 1 \ (mod \ 2) \\
x \equiv 3 \ (mod \ 7) \\
x \equiv 6 \ (mod \ 11) \\
x \equiv 9 \ (mod \ 15) \end{cases}}\)
Ukryta treść:    
Zadanie 13. (A. Shapiro); Punkt kratowy \(\displaystyle{ (x,y)}\) nazywa się widzialnym , jeśli \(\displaystyle{ x}\) i \(\displaystyle{ y}\) są względnie pierwsze. Udowodnić, że istnieje krata \(\displaystyle{ 100 \times 100}\), która nie ma żadnych punktów widzialnych.
Ukryta treść:    
14. Rozwiązać układ kongruencji
\(\displaystyle{ \begin{cases}13x \equiv 1 \ (mod \ 19) \\
17x \equiv 6 \ (mod \ 8) \end{cases}}\)
Ukryta treść:    
:arrow:
Ukryta treść:    
ODPOWIEDZ