Bài 2

Cho

n

và

k

là các số nguyên dương nguyên tố cùng nhau với

k < n

. Tập

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

được tô bởi hai màu, mỗi số một màu xanh hoặc trắng, sao cho: (i) với mỗi

i \in M

, hai số

i

và

n-i

cùng màu; và (ii) với mỗi

i \in M

mà

i \ne k

, hai số

i

và

|i-k|

cùng màu. Chứng minh rằng mọi số trong

M

đều cùng một màu.

Bước 1 trên 5: Các bội của

k

hoán vị tập

M

Bước trước Bước tiếp

Hiểu nôm na

Nhân với $k$ theo modulo $n$ chỉ đơn giản là đánh số lại các số $1,\dots,n-1$ theo một thứ tự mới, giống như xáo một bộ bài mà không mất hay lặp lá nào, chính vì $k$ không có ước chung với $n$ .

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

Phân tích chi tiết

Vì $\gcd(n,k)=1$ nên phép nhân với $k$ là một song ánh trên các lớp thặng dư modulo $n$ ; gọi $r_i$ là đại diện của $ik\bmod n$ nằm trong $\{1,\dots,n-1\}$ (khác 0 vì $0<i<n$ và $\gcd(k,n)=1$ nên $ik\not\equiv0$ ). Khi $i$ chạy từ $1,\dots,n-1$ , các giá trị $r_i$ chạy qua đúng một lần tất cả các phần tử của $M$ , theo một thứ tự nào đó.