Make a video on how to solve this---Topic I-07 Cycling Around
Consider the whole numbers from 0 up to d - 1 arranged in increasing order, evenly spaced around a circle, starting with 0 at the top. Take a fixed whole multiplier m, where 0 < m <= d. For each n on the circle, draw a straight line with an arrow from n to [n x m]_d. Here, [x]_d is the remainder of x when divided by d.
For example, 16 ÷ 14 = 1 r 2 and 4 ÷ 14 = 0 r 4, so we say [16]_14 = 2 and [4]_14 = 4.
Figure 1: A diagram showing all the connections from n to [n x m]_d for d = 14 and m = 2. Cycles are coloured.
By following the above procedure, with d = 14 and m = 2, one can create a diagram as seen in Figure 1. Here are some notable features:
- Numbers like 2, 4, and 8 form a cycle of length three, while 6, 10 and 12 form a different cycle of length three.
- Some numbers like 1, 3, 5, 9, 11, and 13 start outside of, but then become part of a cycle.
- Lastly, there is a path from 7 going to 0, which then stays there.
- Create a diagram for the values d = 10 and m = 7 and comment on any features you observe.
- Is there always guaranteed to be at least one cycle for any pair of values d, m? Provide an explanation.
- Can you devise a way to determine how many cycles there are, from a given d and m, without drawing all of the lines?
- If you can determine there is a cycle, can you determine what length it will be?
---
Chart Description (Figure 1):
* **Type:** Circle diagram representing nodes (numbers) and directed edges (arrows) showing transformations based on modulo arithmetic.
* **Main Elements:**
* **Points:** Numbers 0 through 13 are arranged in a circle. Number 0 is at the top, 1 is to its right, and numbers increase clockwise around the circle up to 13.
* **Lines:** Directed lines (arrows) connect the numbers. The lines are colored green and pink, and some are grey and dotted.
* Green lines form a cycle: 2 -> 4 -> 8 -> 2.
* Pink lines form a cycle: 6 -> 12 -> 10 -> 6.
* Grey dotted lines show paths leading into cycles or other numbers:
* 1 -> 2 (into the green cycle)
* 3 -> 6 (into the pink cycle)
* 5 -> 10 (into the pink cycle)
* 7 -> 0
* 9 -> 4 (into the green cycle)
* 11 -> 8 (into the green cycle)
* 13 -> 12 (into the pink cycle)
* Arrow from 0 to 0 (a self-loop at 0, implied by [0*2]_14 = 0). This line is not explicitly drawn but is implied by the text "a path from 7 going to 0, which then stays there".
* **Labels:** Each point on the circle is labeled with a number from 0 to 13.
* **Overall Structure:** Numbers are positioned around a circle, representing nodes in a directed graph where edges are determined by the function n -> (n * m) mod d. Cycles are highlighted with colors.
视频信息
答案文本
视频字幕
Welcome to our exploration of cycling around with modular arithmetic. We have numbers zero to d minus one arranged around a circle. For each number n, we draw an arrow to the remainder when n times m is divided by d. Let's see how this creates fascinating patterns with cycles and paths.
Now let's examine a specific example with d equals ten and m equals seven. We calculate each transformation: zero maps to zero, one maps to seven, two maps to four, and so on. This creates four distinct cycles. We have two cycles of length one at zero and five, and two cycles of length four. Notice that all numbers are part of cycles with no external paths leading into them.
A fundamental question arises: is there always guaranteed to be at least one cycle for any pair of values d and m? The answer is definitively yes. Since we have a finite set of numbers from zero to d minus one, and each number maps to exactly one other number, any sequence must eventually repeat a value. Once repetition occurs, we have formed a cycle. Additionally, zero always maps to itself, guaranteeing at least one cycle of length one.
We can determine the number of cycles without drawing all the lines using mathematical formulas. The key insight is that numbers on cycles are precisely the multiples of the greatest common divisor of m and d. We then count cycles in a reduced mapping. The formula involves Euler's totient function and multiplicative orders. For cycle lengths, each cycle containing number n has length equal to the multiplicative order of m modulo d divided by the greatest common divisor of n and d.
To summarize what we've learned: modular arithmetic mapping creates beautiful cycle patterns in directed graphs. We proved that cycles are always guaranteed to exist. Mathematical formulas using greatest common divisors and multiplicative orders can predict both the number of cycles and their lengths without drawing the complete diagram. These concepts have important applications in cryptography, computer algorithms, and advanced number theory.