Why does the theorem work?
If we look at the following system:
≡ 1 ≡ 2
1 2 …
≡
We know that the solution is given by:
1
2
≡ 1
1
+ 2
2
+ ⋯+
Note that:
= 1
2
…
Hence:
𝑀 1
≡ 1
1
1
Since ≡ 0 1 . Therefore in order to obtain the original equation: ≡ 1
1
The following must be true:
𝑀 1
1
≡ 1 1
The rest of the congruences can be proved similarly. 4 We have introduced the term for different
terms and such value can be computed by Euclid’s
Algorithm.
Test yourself: Can you solve the following problem using the Chinese Remainder Theorem?
Comets 2P/Encke, 4P/Faye, and 8P/Tuttle have orbital periods of 3 years, 8 years, and 13 years, respectively. The last perihelions 5 of each of these comets were in 2017, 2014, and 2008, respectively. Assuming that time is measured in whole numbers of years and that each orbital period is constant, what is the next year in which all three of these comets will achieve perihelion in the same year? 6
4 http://www.math.tamu.edu/~jon.pitts/courses/2005c/470/supplements/chinese.pdf 5 Perihelion: the point at which the celestial body is closest to the sun in its orbit 6 Problem extracted from https://brilliant.org/wiki/chinese-remainder-theorem/
Made with FlippingBook - professional solution for displaying marketing and sales documents online