If we divide the integers into groups of 3 ("ternary groups"), beginning with 3, we have group one $= 3,4,5$; group two $= 6,7,8$; and so on. If we ask which multiples of 5 belong to which groups, the answer is: 5 in group one, none in group two, 10 in group three, none in group four, and 15 in group five. So we have this pattern: $2\ \_\ 1\ \_\ 0$, where each value is the multiple of 5 modulo 3, and each index of the pattern corresponds to a ternary group. There are 5 places in the pattern, so the length of one cycle period is $5$. The blank value ("_") means no multiple of 5 is in the corresponding group. This pattern repeats for the next three multiples of 5, then the next three, on to infinity. The same applies to all values of $n$, e.g. the pattern for 7 is $\_\ 1\ \_\ 2\ \_\ \_\ 0$. The cycle is always of length $n$, and always ends with $3n \pmod 3$ (meaning it always end with 0, which corresponds to the third multiple of $n$). My question is, what is the formal rubric for this cycle? Where should I look to learn more about this phenomenon?
Answer
This is an example of the Chinese Remainder Theorem. If you have coprime moduli $a$ and $b$ you can solve the equations $$x \equiv c \pmod a\\ x \equiv d \pmod b$$ for any given $c,d$. The solutions will recur at intervals of $ab$. In your example when you note that $5$ is the middle of a group of $3$ you are solving $$x\equiv 2 \pmod 3 \\ x\equiv 0 \pmod 5$$ As you noticed the first solution is $x=5$ and the next is $15$ higher or $20$ and so on.
No comments:
Post a Comment