Bài toán. Cho $n\ge 3$ là số tự nhiên lẻ. Chứng minh rằng $\left\{ 2^{1}-1, 2^{2}-1, .., 2^{n-1}\right\}$ có ít nhất một số chia hết cho $n$
Lời giải.
Giả sử trong tập hợp không có phần tử nào chia hết cho $n$. Dễ thấy $2^{n}-1$ chia cho $n$ không thể có số dư là $n-1$ nên tồn tại hai số $a\ge b$ thỏa mãn $$2^{a}-1\equiv 2^{b}-1(mod\; n) \rightarrow 2^{b}(2^{a-b}-1) \equiv 0 (mod \; n)$$ Do $2^{b}$ không chia hết cho $n$ nên $2^{a-b}-1 \equiv 0 (mod \; n)$. Suy ra $a-b$ chia hết cho $ord_{2}(n)$.
Mà $a-b \le n-2$ nên $ord_{n}(2) \le n-2$. Điều này mâu thuẫn với giả sử.
Vậy điều giả sử là sai. Suy ra đpcm
Bài toán trên được đăng trên group BÀI TOÁN HAY - LỜI GIẢI ĐẸP - ĐAM MÊ TOÁN HỌC
