Đa thức chia đường tròn và dạng yếu của định lí Dirichlet


Trong bài này, qua các bài toán tôi sẽ giới thiệu các tính chất của các đa thức chia đường tròn, từ các tính chất đó tôi giới thiệu dạng yếu của định lí Dirichlet. Phần cuối của bài viết là một số bài toán thi chọn học sinh giỏi liên quan. Bạn đọc có thể xem thêm về định lí Dirichlet tại https://nttuan.org/2016/02/11/topic-746/.

Định nghĩa. Cho số nguyên dương n. Đa thức chia đường tròn thứ n, ký hiệu \Phi_n, là đa thức monic có các nghiệm là các căn nguyên thủy bậc n của đơn vị, nghĩa là \displaystyle \Phi_n(x)=\prod_{\omega_n\in U_n}(x-\omega_n), ở đây U_n là tập tất cả các căn nguyên thủy bậc n của đơn vị.

|U_n|=\varphi (n)\,\,\forall n\geq 1 nên \deg\Phi_n=\varphi (n)\,\,\forall n\geq 1.

Ví dụ. 10 đa thức chia đường tròn đầu tiên là

\Phi_1(x)=x-1,\,\, \Phi_2(x)=x+1,\,\, \Phi_3(x)=x^2+x+1,\,\, \Phi_4(x)=x^2+1,

\Phi_5(x)=x^4+x^3+x^2+x+1,\,\, \Phi_6(x)=x^2-x+1,\,\,\Phi_7(x)=x^6+x^5+x^4+x^3+x^2+x+1,

\Phi_8(x)=x^4+1,\,\, \Phi_9(x)=x^6+x^3+1,\,\,\Phi_{10}(x)=x^4-x^3+x^2-x+1.

Bài 1. Chứng minh rằng với mỗi số nguyên dương n ta có \displaystyle x^n-1=\prod_{d|n}\Phi_d(x). Từ đó suy ra \displaystyle n=\sum_{d|n}\varphi (d).

Bài 2. Chứng minh \Phi_n(x)\in\mathbb{Z}[x]\,\,\forall n\geq 1.

Bài 3. Chứng minh rằng nếu an là các số nguyên dương nguyên tố cùng nhau thì \Phi_n(x^a)=\prod_{d|a}\Phi_{nd}(x).

Bài 4. Cho số nguyên dương n và số nguyên tố p. Chứng minh rằng

\displaystyle \Phi_{pn}(x)=\begin{cases}\Phi_n(x^p),\quad p|n\\ \frac{\Phi_n(x^p)}{\Phi_n(x)},\quad p\not|n.\end{cases}

Bài 5. Cho số nguyên dương n, d<n là một ước dương của n, và a là một số nguyên. Giả sử p là một ước nguyên tố chung của \Phi_n(a)\Phi_d(a). Chứng minh rằng p|n.

Bài 6. Cho mn là các số nguyên dương. Giả sử rằng tồn tại số nguyên a sao cho \gcd (\Phi_m(a),\Phi_n(a))>1. Chứng minh rằng \dfrac{m}{n} là lũy thừa nguyên của một số nguyên tố.

Bài 7. Cho số nguyên dương n và số nguyên a. Chứng minh rằng mỗi ước nguyên tố p của \Phi_n(a) phải thỏa mãn p|n hoặc p\equiv 1\pmod{n}.

Bài 8. (Dạng yếu của định lý Dirichlet) Cho số nguyên dương n. Chứng minh rằng có vô hạn số nguyên tố p thỏa mãn p\equiv 1\pmod{n}. Continue reading “Đa thức chia đường tròn và dạng yếu của định lí Dirichlet”

Các trường hợp đặc biệt của định lý Dirichlet về cấp số cộng


Ta biết là có định lý sau đây

Định lý Dirichlet. Cho hai số nguyên dương nguyên tố cùng nhau ad. Khi đó có vô hạn các số nguyên tố có dạng a+dk (k là số tự nhiên.)

Trong topic này tôi giới thiệu một bài viết có chứng minh của các trường hợp đặc biệt của định lý trên:

a=1,d=4;a=1,d=6;a=1,d=8a=1, d bất kỳ. Continue reading “Các trường hợp đặc biệt của định lý Dirichlet về cấp số cộng”

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.