Chinese Remainder Theorem
- Yuki
- Aug 5
- 1 min read
It is possible to uniquely construct a number that satisfies several conditions simultaneously.
for example,
When divided by 3, the remainder is 2.
When divided by 5, the remainder is 3.
When divided by 7, the remainder is 2.
We will search for a number that satisfies all of the following conditions.
The smallest answer is 23 .
23≡2(mod3),23≡3(mod5),23≡2(mod7)
And importantly, if the numbers do not have any common divisors, like 3, 5, and 7, the answer is
3×5×7=1053\times5\times7=1053×5×7=105
It is determined to be unique, with a period of . In other words, the answer is
23, 128, 233,…23,\ 128,\ 233,\dots23, 128, 233,…
The idea of finding the point where "all conditions perfectly match."
Three different repetitions coincide only in the center of the stage.
The three cycles coincide at the light at the top of the stage.
Comments