[conami]

Nguyên văn bởi namdung

2. (VMO 2004, Trung bình khó) Gọi S(n) là tổng các chữ số của số nguyên dương n viết trong hệ thập phân. Hãy tìm giá trị nhỏ nhất của S(n) trong đó n là số nguyên dương chia hết cho 2003.

Bài 2 này sử dụng một số tính chất của số chính phương modulo.
Đặt $p=2003 $, $p $ là số nguyên tố.
Trước hết ta dễ dàng thấy được $S(n) > 1 $ vì $10^{k} $ không là bội của $2003 $.
Xét$ S(n)=2 $, có $2 $khả năng xảy ra
TH1:$ n=2.10^{k} $. Trường hợp này không thoả mãn do $p $ không là ước của $10^{k} $và $2 $.
TH2: $n=10^{a}+10^{b} (0 \ge b < a) $
Vì $n \vdots 2003 \Rightarrow 10^{a} \equiv -10^{b} (mod p) \Rightarrow 10^{a-b} \equiv -1 (mod p) $
Đặt $k = a - b \Rightarrow 10^{k} \equiv 10^{a-b} \equiv -1 (mod p) $
Do $2^{10} = 1024 \equiv 10^{7} (mod p) $ nên ta có:
$(2^{5k})^{2} = 2^{10k} \equiv (10^{7})^{k} \equiv -1 (mod p) $
Do đó $-1 $ là số chính phương modulo $p $, suy ra $p $ có dạng $4t+1 $, đây là điều vô lí.
Xét $S(n)=3 $. Ta chứng minh đây là giá trị nhỏ nhất của $S(n) $
Thật vậy, ta có:
$2^{10} \equiv 10^{7} (mod p) \Rightarrow 2 \cdot 10^{700} \equiv 2^{1001} = 2^{\dfrac{p-1}{2}} \equiv -1 (mod p) $
(do $2003 $ không co dạng $8t+1 $ hay $8t-1 $ nên $2 $không phải là số chính phương modulo $p $)
$\Rightarrow 2 \cdot 10^{700} + 1 \vdots p $
Đặt $n=2 \cdot 10^{700} + 1. $Rõ ràng $n $ là bội của $p=2003 $ và $S(n)=3 $.
Vậy $S(n) $ nhỏ nhất bằng $3 $.

Thầy Nam Dũng cho em hỏi là các bổ đề liên quan đến số chính phương modulo nếu muốn áp dụng thì có cần phải chứng minh lại hay không ạ? Em thấy các bổ đề này nó đều liên quan tới nhau. Nếu trình bày đầy đủ tất cả phần chứng minh các bổ đề vào bài thì thì ít nhất cũng phải mất 3,4 trang giấy...

(ví dụ chứng minh luật tương hỗ Gauss )

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]