Competition problem — Number theory

Library / /325 of 520

Number theory Difficulty 6.2 National olympiad Prove it

Example 36([26.2]) Let $n, k$ be positive integers, $k$ and $n$ are coprime, and satisfy $0<k<n$ . Let the set $M=\{1,2, \cdots, n-1\}$ . Now, each number $i$ in set $M$ is painted blue or white, satisfying the following conditions:
(i) $i$ and $n-i$ must be painted the same color;
(ii) When $i \neq k$ , $i$ and $|k-i|$ must be painted the same color. Prove: All numbers are painted the same color.

Solution

Solution: See Chapter 3 § 2 Example 1. Here we need to use the property of the theory of divisibility: $k$ and $n$ are coprime if and only if there exist integers $x, y$ such that $k x + n y = 1$ (Chapter 1 § 3 Theorem 5 or § 4 Theorem 8).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.