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 1 of 5: The multiples of

k

permute

M

Previous step Next step

In plain words

Multiplying by $k$ modulo $n$ just relabels the numbers $1,\dots,n-1$ in a new order, like shuffling a deck without losing or duplicating any card, precisely because $k$ shares no common factor with $n$ .

\{k,2k,\dots,(n-1)k\} \equiv \{1,2,\dots,n-1\} \pmod n

Detailed analysis

Since $\gcd(n,k)=1$ , multiplication by $k$ is a bijection on residues mod $n$ ; write $r_i$ for the representative of $ik\bmod n$ lying in $\{1,\dots,n-1\}$ (nonzero because $0<i<n$ and $\gcd(k,n)=1$ force $ik\not\equiv0$ ). As $i$ ranges over $1,\dots,n-1$ , the values $r_i$ run through all of $M$ exactly once, in some order.