Month: October 2008

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

và \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}).

Vì k\leq p và \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.

Định lý của Fermat về tổng của hai bình phương


Bài này tôi sẽ giới thiệu nhiều cách chứng minh cho ”Định lý của Fermat về tổng của hai bình phương”:

Định lý. Một số nguyên tố lẻ p biểu diễn được dưới dạng p=x^2+y^2(x,y\in\mathbb{Z}) khi và chỉ khi p\equiv 1\pmod{4}.

CHỨNG MINH CỦA EULER

Chứng minh này được Euler tìm ra năm 1747 , chứng minh theo 5 bước

1. Nếu x và y là tổng của hai bình phương thì xy cũng thế.

Kết quả này được suy từ đẳng thức Brahmagupta-Fibonacci: (m^2+n^2)(x^2+y^2)=(mx+ny)^2+(my-nx)^2.

2. Nếu a và p là tổng của hai bình phương và p|a thì \dfrac{a}{p} cũng là tổng của hai bình phương.

Gỉa sử a=m^2+n^2 và p=x^2+y^2 với m,n,x,y\in\mathbb{Z}. Ta có p chia hết m^2p-ax^2=(my-nx)(my+nx) nên không giảm tổng quát ta có thể xem là p|my-nx. Bây giờ từ ap=(my-nx)^2+(mx+ny)^2 suy ra p|mx+ny, chia hai vế của đẳng thức này cho p^2 ta có điều cần chứng minh.

3. Nếu a có thể viết như là tổng của hai bình phương, d không thể viết dưới dạng tổng hai bình phương và d|n thì \dfrac{n}{d} có ít nhất một ước không viết được dưới dạng tổng của hai bình phương.

Gỉa sử a=dp_1\cdots p_n, ở đây p_1,\cdots, p_n là các số nguyên tố không cần phải khác nhau. Nếu tất cả các p_i đều viết được dưới dạng tổng của hai bình phương thì bằng cách chia liên tiếp a cho các p_i và dùng bước 2 ta có d là tổng của hai bình phương, vô lí!

4. Nếu a và b là nguyên tố cùng nhau thì mỗi ước của a^2+b^2 là tổng của hai bình phương.

Gỉa sử x là một ước của a^2+b^2 , viết a=mx+c,b=nx+d với |c|,|d|\leq x/2, m,n,c,d\in\mathbb{Z}. Ta có a^2+b^2=Ax+(c^2+d^2), như thế c^2+d^2 chia hết cho x, viết c^2+d^2=yx, có thể xem \gcd (c,d)=1 vì ước nguyên tố chung nếu có của c và d không thể là ước của x. Nếu x không phải là tổng của hai bình phương và nó là số bé nhất có tính chất đó, theo bước 3 , y có một ước z không là tổng của hai bình phương, mà zx\leq yx=c^2+d^2\leq \dfrac{x^2}{2} , suy ra z<x, vô lí!

5. Mỗi số nguyên tố p có dạng 4n+1 đều là tổng của hai bình phương.

Theo Định lý Fermat nhỏ ta có i^{4n}\equiv 1\pmod{p}\forall i=1,2,\cdots,4n do đó các số i^{4n}-(i-1)^{4n}, i=2,\cdots, 4n đều chia hết cho p. Các số này được viết ở dạng (a^{2n}+b^{2n})(a^{2n}-b^{2n}). Nếu p là ước của một trong các thừa số đầu thì theo 4, p sẽ là tổng của hai bình phương. Nếu p là ước của tất cả các thừa số sau thì bằng cách áp dụng phép toán sai phân nhiều lần trên dãy đó ta sẽ có p|(2n)!, vô lí!

Bài tập về ước và số ước của một số nguyên dương


Với mỗi số nguyên dương n, gọi d(n) là số ước dương của n. Trong bài này chúng ta sẽ trao đổi về hai loại bài tập sau đây

1-Tìm n khi biết d(n) hoặc biết vài mối quan hệ giữa các ước của n.

2-Chứng minh một vài tính chất của d(n).

Các kết quả sau đây sẽ được dùng nhiều

Định lý 1. Nếu n là một số nguyên dương và n=\prod_{p\in P}p^{e_p(n)} thì d(n)=\prod_{p\in P}(e_p(n)+1).

(Chú ý rằng mặc dù tập P các số nguyên tố là vô hạn nhưng chỉ có hữu hạn các số e_p(n) khác 0, nên các tích trên là các tích hữu hạn).

Định lý 2. Nếu n là một số nguyên dương và 1=d_1<d_2\cdots<d_k=n là tất cả ước dương của n thì d_1d_k=d_2d_{k-1}=\cdots=n.

Các bạn hãy tự chứng minh hai Định lý trên xem như bài tập.

Ví dụ 1. Tìm tất cả các số nguyên dương n có đúng 16 uớc dương 1=d_1<d_2<\cdots<d_{16}=n sao cho d_k=(d_2+d_4)d_6, ở đây k=d_5.

Hướng dẫn. Do Định lý 1 ta thấy n không thể có quá nhiều ước nguyên tố được , vì nếu không số ước dương của nó sẽ nhiều hơn 16 ngay. Vẫn theo Định lý 1, nếu p là ước nguyên tố của n thì e_p(n) cũng không được lớn quá.. Vậy muốn tìm n ta nên đi tìm càng nhiều ước nguyên tố của n càng tốt. Chú ý thêm là 4<d_5<17.

Ví dụ 2. Tìm các số nguyên dương n sao cho n=d^2(n).

Hướng dẫn. Nếu n là số thoả mãn thì n phải là số chính phương , viết n=p_1^{2k_1}\cdots p_m^{2k_m} thì đẳng thức trong đầu bài tương đương với (2k_1+1)\cdots (2k_m+1)=p_1^{k_1}\cdots p_m^{k_m}. Bây giờ chú ý là \lim_{n\to +\infty}\dfrac{a^n}{P(n)}=+\infty với a>1.

Bài tập.

Bài 1. Tìm tất cả các số nguyên dương n sao cho n có đúng 16 ước dương 1=d_1<d_2<\cdots<d_{16}=n thoả mãn d_{6}=18 và d_9-d_8=17.

Bài 2. Cho n là số nguyên dương và d_1<d_2<d_3<d_4 là bốn ước dương bé nhất của n. Tìm n sao cho n=d_1^2+d_2^2+d_3^2+d_4^2.

Bài 3. Với mỗi số nguyên dương n , gọi m là ước lẻ lớn nhất của n và g(n) là tổng các ước dương của n. Chứng minh rằng g(n)-d(m) là số chẵn với mỗi số nguyên dương n.

Bài 4. Tìm các số nguyên dương n sao cho d(n)=n/3.

Bài 5. Tìm các số nguyên dương n sao cho n có đúng 6 ước dương 1<d_1<d_2<d_3<d_4<n và 1+n=5(d_1+d_2+d_3+d_4).

Bài 6. Tìm các số nguyên dương n sao cho d^3(n)=4n.

Bài 7. Tìm tất cả số nguyên k sao cho có số nguyên dương n thoả mãn \dfrac{d(n^2)}{d(n)}=k.

Bài 8. Số nguyên dương n có k>21 ước dương 1=d_1<d_2<\cdots<d_k=n. Tìm n sao cho d_7^2+d_{10}^2=(n/d_{22})^2.

Bài 9. Cho n>1 là một số nguyên dương và 1=d_1<d_2<\cdots<d_k=n là tất cả các ước dương của n. Đặt S_n=d_1d_2+d_2d_3+\cdots+d_{k-1}d_k. Chứng minh rằng S_n<n^2 và tìm n để S_n|n^2.

Bài 10.  Cho số nguyên dương n, gọi A là tập các ước dương của n^2 có dạng 4k+1, B là tập các ước dương của n^2 có dạng 4k+3. So sánh |A| và |B|.

Bài 11. Chứng minh rằng dãy \{d([n^2+1]^2)\} không thể đơn điệu kể từ lúc nào đó.

Hai đường tròn tiếp xúc(Bài Kid hỏi)


Một đường thẳng đi qua tâm đường tròn nội tiếp I của tam giác ABC cắt AB, AC tại P,Q tương ứng . Chứng minh rằng đường tròn tiếp xúc với AB, AC tại P,Q tương ứng cũng tiếp xúc với đường tròn ngoại tiếp tam giác ABC.

Hướng dẫn: Gọi J là tâm của đường tròn đó. Từ tam giác vuông APJ tính được JP(là bán kính của (J)) và AJ, bằng định lý cosin trong tam giác AOJ sẽ tính được OJ (O là tâm đường tròn ngoại tiếp của tam giác ABC). Gìơ chứng minh OJ=R-IP là xong!(R là bán kính của đường tròn ngoại tiếp tam giác ABC).

Nguyên lý bù-trừ


Mở đầu

Bài viết xem như sự mở đầu của phương pháp SÀNG trong các bài toán đếm. Ở phương pháp này, khi muốn đếm số phần tử của một tập A, ta bắt đầu với một tập B chứa A, sau đó tìm cách loại đi các phần tử không nằm trong A.

Chúng ta biết rằng nếu A và B là các tập hữu hạn rời nhau thì |A\cup B|=|A|+|B|, tổng quát hơn ta có: Nếu A và B là các tập hữu hạn bất kỳ(không nhất thiết rời nhau) thì  |A\cup B|=|A|+|B|-|A\cap B|, đây chính là nguyên lý bù-trừ cho hai tập hợp, dễ hiểu tại sao người ta lại gọi đây là nguyên lý bù trừ. Với n>1 tập hợp ta có định lý sau

Định lý. Nếu A_1,A_2,\cdots,A_n là các tập hữu hạn thì |\cup_{i=1}^nA_i|=\sum_{1\leq i\leq n}|A_i|-\sum_{1\leq i<j\leq n}|A_i\cap A_j|+...+(-1)^{n+1}|\cap_{1\leq i\leq n}A_i|.

Ta sẽ chứng minh rằng rằng mỗi phần tử trong \cup_{i=1}^nA_i được đếm đúng một lần trong vế phải. Gọi x là một phần tử trong hợp đó và nó nằm trong dúng m tập A_i, khi đó trong vế phải nó sẽ được đếm đúng C_m^1-C_m^2+\cdots+(-1)^{m+1}C_m^m=1 lần (lưu ý (1-1)^m=0). Định lý được chứng minh.

Ngoài cách chứng minh trên các bạn có thể chứng minh Định lý bằng phương pháp quy nạp toán học, tôi chọn giới thiệu cách chứng minh đó vì phong cách Tổ hợp của nó.

Một áp dụng đẹp của nguyên lý bù-trừ là bài toán Bernoulli-Euler về các bức thư sai địa chỉ: Có n>1 bức thư khác nhau phải gửi đến n địa chỉ khác nhau. Có bao nhiêu cách gửi mà các bức thư đều đến không đúng địa chỉ của mình? Theo ngôn ngữ ánh xạ, bài toán được phát biểu như sau: Có bao nhiêu song ánh từ S={1,2,…,n} đến chính S sao cho nó không có điểm cố định? Ta đếm số các song ánh có điểm cố định, số này bằng C_n=|\cup_{1\leq i\leq n}A_i|, ở đây A_i là tập các song ánh nhận i làm điểm cố định. Theo nguyên lý bù-trừ dễ có C_n=\sum_{k=1}^nC_n^k(-1)^{k+1}(n-k)! và đáp số của bài toán là D_n=n!-C_n.

Bài tập.

Bài 1. Tìm số các số nguyên dương trong {1,2,…,500} chia hết cho 2 hoặc 3 hoặc 5.

Bài 2. Tính giá trị của phi hàm Euler tại n theo phân tích chính tắc của n.

Bài 3. Chứng minh nguyên lý bù-trừ bằng quy nạp toán học.

Bài 4. Cho X là một tập hữu hạn và A,B,C là các tập con của nó. Chứng minh rằng |\bar{A}\cap B|=|B|-|A\cap B| và |\bar{A}\cap\bar{B}\cap C|=|C|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.

Bài 5. Tìm số các số nguyên trong tập {1,2,…,1000} không chia hết cho 5, không chia hết cho 7, nhưng chia hết cho 3.

Bài 6. Có bao nhiêu số nguyên dương n sao cho n là ước của ít nhất một trong hai số 10^{40} và 20^{30}?

Bài 7. Với mỗi số nguyên dương n>1, gọi A_n là số các song ánh từ S đến S sao cho f(k) khác k+1 với mỗi k=1,2,…,n-1.

a)Tính A_n;

b)Chứng minh rằng A_n=D_n+D_{n-1} với mỗi n>1.

Bài 8. Tìm số các số nguyên dương là ước của ít nhất một trong các số 10^{60},20^{50},30^{40}.

Bài 9. Với k=1,2,…,1992 cho A_k là một tập với 44 phần tử. Gỉa sử rằng |A_i\cap A_j|=1 với mỗi i,j khác nhau trong {1,2,…,1992}. Tính |\cup_{i=1}^{1992}A_i|.

Bài 10. Cho A_1,A_2,\cdots,A_n là n tập hữu hạn. Chứng minh rằng |\cup_{i=1}^nA_i|\geq \sum_{i=1}^n|A_i|-\sum_{1\leq i<j\leq n}|A_i\cap A_j|. Sử dụng bất đẳng thức này để giải bài toán sau: Một hoán vị của {1,2,…,2n} được gọi là có tính chất P nếu có ít nhất hai số dạng k,n+k đứng cạnh nhau. Chứng minh rằng với mỗi số nguyên dương n, số các hoán vị có tính chất P nhiều hơn số các hoán vị không có tính chất đó.

Bài 11. Cho các số nguyên dương m\leq n và A,B là các tập có n,m phần tử tương ứng. Tìm số các toàn ánh từ A lên B. Từ đó suy ra \sum_{k=0}^n(-1)^kC_n^k(n-k)^n=n!.