Problem 2

Let

n

and

k

be relatively prime positive integers with

k < n

. The set

M = \{1, 2, \ldots, n-1\}

is colored so that each number is either blue or white, subject to: (i) for each

i \in M

, the numbers

i

and

n-i

have the same color; and (ii) for each

i \in M

with

i \ne k

, the numbers

i

and

|i-k|

have the same color. Prove that all the numbers in

M

must have the same color.

Step 2 of 5: Two ways consecutive residues can differ

Previous step Next step

In plain words

Walking from one labeled point to the next around the cycle of residues, each step is a jump of size $k$ — except that once you pass the top of the cycle ( $n$ ), you land $n$ lower than the plain sum suggests.

r_{i+1} = r_i + k \quad\text{or}\quad r_{i+1} = r_i + k - n

Detailed analysis

By definition $r_{i+1}-r_i \equiv k \pmod n$ , and since both $r_i,r_{i+1}\in\{1,\dots,n-1\}$ , the actual (non-modular) difference is either exactly $k$ , or $k-n$ (when adding $k$ overshoots past $n$ and wraps around).