$\textbf{Bài toán 1 (Brazil National Olympiad 2009).}$ Cho $p,q$ là các số nguyên tố thỏa mãn $q=2p+1$. Chứng minh rằng tồn tại một bội của $q$ mà tổng các chữ số trong biểu diễn thập phân của nó không vượt quá $3$.
$\textbf{Lời giải.}$
Rõ ràng $q\geq 5$. Xét $q=5$ thì $10$ là bội của $5$ và tổng của các chữ số của $10$ là $1$ (thỏa mãn)
Nếu $q>5$ thì $(q,10)=1$. Áp dụng định lý Fermat nhỏ, ta được: $10^{q-1}\equiv 1 (\text{mod q})\Rightarrow 10^{2p}\equiv 1 (\text{mod q})\Rightarrow q | (10^p+1)(10^p-1)$
$\textbf{Trường hợp 1.}$ $q|10^p+1$ thì rõ ràng $10^p+1$ là một bội của $q$ mà tổng các chữ số trong biểu diễn thập phân của nó là $2$ nên bài toán được chứng minh
$\textbf{Trường hợp 2.}$ $q|10^p-1$. Gọi $h=ord_q(10)$ thì $h=1$ hoặc $h=p$. Rõ ràng $h=1$ vô lí vì nếu $h=1$ thì $q|9$. Do đó $h=p$ hay nói cách khác $p$ là cấp của $10$ theo modulo $q$
Suy ra khi ta đem chia các số $10^1,10^2,...,10^p$ cho $q$ thì chúng sẽ lần lược nhận các số dư phân biệt theo thứ tự là $r_1,r_2,...,r_p$ với $1\leq r_i\leq 2p(i=\overline{1,p})$
Nếu $r_i=p$ thì $2.10^i+1\equiv 2r_i+1=2p+1\equiv 0(\text{mod q})$ nên đây cũng là một bội của $q$ có tổng các chữ số là $3$. Tương tự với $r_i=2p$ thì ta cũng thấy thỏa mãn
Trong trường hợp trong $p$ số trên không có số nào khi chia $q$ có số dư là $p$ hoặc $2p$ thì ta phân hoạch $2p-2$ số dư còn lại trong tập hợp số dư thành $p-1$ tập con như sau $$\left \{ 1,2p-1 \right \},\left \{ 2,2p-2 \right \},...,\left \{ p-1,p+1 \right \}$$
Có $p$ số mà chỉ có $p-1$ tập con nên theo nguyên lí Dirichlet thì tồn tại hai số $r_i,r_j$ sao cho $r_i+r_j=2p$. Tức là $10^i+10^j+1 \equiv 2p+1\equiv 0(\text{mod q})$. Mà $10^i+10^j+1$ là một số biểu diễn trong hệ thập phân có tổng các chữ số là $3$ nên trường hợp nãy vẫn thỏa mãn
Vậy ta có điều phải chứng minh
Bài viết đã được chỉnh sửa nội dung bởi KietLW9: 14-08-2022 - 07:14