Một đồng dư modulo nguyên tố


Người dịch: Nguyễn Trung Tuân
Tặng Thầy nhân dịp 20-11-2007

Trong năm 1961, Erdos, Ginzburg, và Ziv [3] đã tìm ra định lý nổi tiếng sau đây, bây giờ nó là trung tâm của các bài toán 0- tổng( về các bài toán này các bạn có thể tìm trong [1],[2] và [5]).

Định lý EGZ. Giả sử n là một số nguyên dương. Khi đó với mỗi dãy a_1,a_2,\cdots,a_{2n-1} gồm 2n-1 số nguyên có một dãy con a_{i_1},a_{i_2},\cdots, a_{i_n} độ dài n sao cho tổng \sum_{j=1}^na_{i_j} chia hết cho n.

Dễ kiểm tra thấy rằng định lý EGZ là nhân tính, nghĩa là, nếu mệnh đề đúng với n=k và n=l thì nó cũng đúng với n=kl. Do đó chỉ cần chứng minh định lý đúng với n nguyên tố là đủ. Trong các chứng minh cổ điển của định lý, trường hợp n nguyên tố thường có được từ định lý Cauchy-Davenport hoặc định lý Chevalley-Waring (xem [6]). Tuy nhiên, với sự giúp đỡ của định thức Vandermonde, Gao [4] cho một chứng minh khác của định lý EGZ dựa trên đồng dư sau \sum_{I\subseteq\{1,\cdots,2p-1\},|I|=p}\;(\sum_{i\in I}a_i)^{p-1}\equiv 0\pmod{p},\; (*)
ở đó p là một số nguyên tố và a_1,\cdots,a_{2p-1} là các số nguyên bất kì. Chú ý rằng định lý EGZ là một hệ quả đơn giản của (*) vì theo định lý Fermat nhỏ chúng ta có

\left|\{I\subseteq\{1,2,\cdots,2p-1\}:\sum_{i\in I}a_i\equiv 0\pmod{p},|I|=p\}\right|\equiv
\equiv\sum_{I\subseteq\{1,\cdots,2p-1\},|I|=p}\;(1-(\sum_{i\in I}a_i)^{p-1})\equiv C_{2p-1}^p\equiv 1\pmod{p}.

Trong bài báo này, chúng tôi sẽ chứng minh định lý sau, mà đồng dư của Gao chỉ là một hệ quả đơn giản của nó:

Định lý. Giả sử p là một số nguyên tố và k là một số nguyên dương thỏa mãn k\leq p. Cho f(x_1,\cdots,x_k) là một đa thức đối xứng với hệ số nguyên biến x_1,\cdots,x_k. Nếu bậc của f nhỏ hơn k thì với một dãy bất kì gồm p+k-1 số nguyên a_1,a_2,\cdots,a_{p+k-1}, chúng ta có

\sum_{1\leq i_1<\cdots<i_k\leq p+k-1}\; f(a_{i_1},\cdots,a_{i_k})\equiv f(0,\cdots,0)\pmod{p} nếu k=p

\equiv 0\pmod{p} trong trường hợp còn lại.

Chứng minh. Chứng minh là sơ cấp, chỉ cần đến một tính chất số học cơ  bản của hệ số nhị thức: C_{p+k-1}^k\equiv 1\pmod{p} nếu k=p và \equiv 0\pmod{p} nếu 1\leq k<p.

Chúng tôi sẽ chứng minh định lý bằng quy nạp theo k. Khi k=1, vì \deg f<k nên f phải là một hằng số c. Trong trường hợp này \sum_{1\leq i\leq p}f(a_i)=p\cdot c\equiv 0\pmod{p}. Bây giờ giả sử rằng k>1 và định lý là đúng với tất cả các giá trị nhỏ hơn k. Đặt S_{f,k}(x_1,\cdots,x_{p+k-1})=\sum_{1\leq i_1<\cdots<i_k\leq p+k-1}\; f(x_{i_1},\cdots,x_{i_k}) và viết f(x_1,\cdots, x_k) dưới dạng f(x_1,\cdots,x_k)=\sum_{j=0}^{k-1}g_j(x_1,\cdots,x_{k-1})x_k^j, ở đây g_j là các đa thức biến x_1,\cdots,x_{k-1}. Từ tính đối xứng của f ta có S_{f,k} và tất cả g_j là các đa thức đối xứng.

Tiếp theo chúng ta thấy rằng

S_{f,k}(a_1,\cdots,a_{p+k-1})=\sum_{1\leq i_1<\cdots<i_k\leq p+k-2}\;f(a_{i_1},\cdots,a_{i_k})+
+\sum_{1\leq i_1<\cdots<i_{k-1}\leq p+k-2}\; f(a_{i_1},\cdots,a_{i_{k-1}},a_{p+k-1}).

Do đó S_{f,k}(a_1,\cdots,a_{p+k-1})-S_{f,k}(a_1,\cdots,a_{p+k-2} ,0)

=\sum_{1\leq i_1<\cdots<i_{k-1}\leq p+k-2}\;(f(a_{i_1},\cdots,a_{i_{k-1}},a_{p+k-1})-f(a_{i_1},\cdots,a_{i_{k-1}},0))

=\sum_{1\leq i_1<\cdots<i_{k-1}\leq p+k-2}\;\left(\sum_{j=0}^{k-1}g_j(a_{i_1},\cdots,a_{i_{k-1}})a_{p+k-1}^j-g_0(a_{i_1},\cdots,a_{i_{k-1}})\right)

=\sum_{j=1}^{k-1}a_{p+k-1}^j\;\sum_{1\leq i_1<\cdots<i_{k-1}\leq p+k-2}\;g_j(a_{i_1},\cdots,a_{i_{k-1}})

=\sum_{j=1}^{k-1}a_{p+k-1}^jS_{g_j,k-1}(a_1,\cdots,a_{p+k-2}).

k\leq p\deg g_j\leq \deg f-j<k-j, chúng ta có thể dùng giả thiết quy nạp để có

S_{g_j,k-1}(a_1,\cdots,a_{p+k-2})\equiv 0\pmod{p}\forall j=\overline{1,k-1}. Do đó

S_{f,k}(a_1,\cdots,a_{p+k-1})\equiv S_{f,k}(a_1,\cdots,a_{p+k-2},0)\pmod{p}. Từ đây, sử dụng tính đối xứng của S_{f,k}, chúng ta có S_{f,k}(a_1,\cdots,a_{p+k-1})\equiv S_{f,k}(0,\cdots,0)\pmod{p}.

Cuối cùng, bởi định nghĩa của S_{f,k}, ta có S_{f,k}(a_1,\cdots,a_{p+k-1})=C_{p+k-1}^kf(0,\cdots,0)\equiv f(0,\cdots,0)\pmod{p} nếu k=p và \equiv 0\pmod{p} nếu 1\leq k<p.

Định lý được chứng minh.

Tài liệu tham khảo

[1]N. Alon and M. Dubiner, Zero-sum sets of prescribed size, in: “Combinatorics, Paul Erdos is Eighty”, Bolyai Society, Mathematical Studies, Keszthely, Hungary, 1993, 33-50.

[2]Y. Caro, “Zero-sum problems: a survey” Discrete Math. , 152 (1996) pp. 93–113.

[3]Erdos, P., Ginzburg, A., Ziv, A. Theorem in additive number Theory,. Bull. Res. Council, Israel, 10 F(1961) 41–43.

[4]W. D. Gao – Two addition theorems on groups of prime order, J. Number Theory, Vol.56 (1996) 211-213.

[5]W.D. Gao, A. Geroldinger, On zero sum sequences in Zn ⊕ Zn Integers 3 (A8) (2003) 45 (electronic).

[6]M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets, 1996.

1 thought on “Một đồng dư modulo nguyên tố”

  1. Đây là định lý Chevalley-Warning với khá nhiều ứng sụng hay ho

    Lấy p là 1 số nguyên tố và \mathbb{F}_q là 1 trường hưu hạn q=p' phần tử . Với i=1,...,m ta lấy f_i(x_1,...,x_n) là 1 đa hức bậc d_i của n biến với hệ số thuộc \mathbb{F}_q .Lấy N là số n-tuples (x_1,...,x_n) các phần tử của \mathbb{F}_q sao cho :
    f_i(x_1,...,x_n)=0 với mọil i=1,...,m. Nếu \sum_{i=1}^{m}d_i < n
    thì N\equiv 0 (mod p).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s