A proof of Schonemann’s criterion

Các em học sinh nên xem lại hai bài sau:

[1] https://nttuan.org/2009/01/11/poly02/

[2] https://nttuan.org/2018/08/25/poly03/

Định lý (Schonemann, 1846). Cho số nguyên tố $p$ , số nguyên dương $n$ , và một đa thức $f(x)$ với hệ số nguyên có dạng $f(x)=(g(x))^n+ph(x).$ Trong đó $g$ và $h$ là các đa thức với hệ số nguyên thỏa mãn:

(a) hệ số cao nhất của $g$ bằng $1$ và $g$ bất khả quy trong $\mathbb{F}_p[x]$ .

(b) $\deg (h)<\deg (f)$ và $(g,h)=1$ trong $\mathbb{F}_p[x]$ .

Khi đó $f$ bất khả quy trong $\mathbb{Q}[x]$ .

Chứng minh. Ta thấy hệ số cao nhất của $f$ bằng $1$ và $\deg (f)=n\deg (g).$ Giả sử $f$ khả quy trong $\mathbb{Q}[x]$ , suy ra $f=f_1f_2$ , với $f_1$ và $f_2$ là các đa thức khác hằng với hệ số nguyên cùng có hệ số cao nhất là $1$ . Khi đó trong $\mathbb{F}_p[x]$ ta có $g^n=f_1f_2,$ mà hệ số cao nhất của $g$ bằng $1$ và $g$ bất khả quy trong $\mathbb{F}_p[x]$ , suy ra trong $\mathbb{Z}[x]$ thì $f_1=g^r+pF_1$ và $f_2=g^{n-r}+pF_2,$ ở đây $r$ là số nguyên dương bé hơn $n$ , và $F_1$ , $F_2$ là hai đa thức với hệ số nguyên. Do đó trong $\mathbb{Z}[x]$ ta có đẳng thức

$h=F_1g^{n-r}+F_2g^r+pF_1F_2,$

suy ra $g\mid h$ trong $\mathbb{F}_p[x],$ điều này không thể xảy ra do $(g,h)=1$ trong $\mathbb{F}_p[x]$ . $\Box$

Tiêu chuẩn này là một tổng quát của tiêu chuẩn Eisenstein.

Polynomials with integer coefficients

Đây là bài thứ ba về đa thức của tôi, các bạn học sinh nên xem lại hai bài trước để học cho dễ dàng hơn. Như các bài trước, các bạn học sinh tự hoàn thiện các lời giải một cách chi tiết.

[1] https://nttuan.org/2023/06/30/poly01/

[2] https://nttuan.org/2023/08/11/poly02/

Mục đích của bài này là giới thiệu một số kết quả cơ bản về các đa thức với hệ số nguyên, chẳng hạn như định lí nghiệm hữu tỷ và tiêu chuẩn bất khả quy của Eisenstein.

Định lí 1 (Định lí nghiệm hữu tỷ). Cho số nguyên dương $n$ và đa thức

$P(x)=a_n x^n+a_{n-1} x^{n-1}+\ldots+a_1 x+a_0$

có bậc bằng $n$ với hệ số nguyên. Khi đó nếu $r / s$ là một nghiệm hữu tỷ khác không của $P(x)$ thỏa mãn $(r, s)=1$ , thì $r \mid a_0$ and $s \mid a_n$ .

Chứng minh. Từ giả thiết ta có $a_n r^n+a_{n-1} r^{n-1} s+\cdots+a_1 r s^{n-1}+a_0 s^n=0,$
suy ra $r \mid a_0 s^n$ và $s \mid a_n r^n$ . Nhưng $r$ và $s$ nguyên tố cùng nhau, nên $r \mid a_0$ và $s \mid a_n$ . $\Box$

Theo định lí này, khi $P$ có hệ số cao nhất bằng $1$ thì mọi nghiệm hữu tỷ của $P$ đều là số nguyên. Với một đa thức khác hằng với hệ số nguyên, từ định lí ta cũng thấy muốn tìm nghiệm hữu tỷ của đa thức ta chỉ cần tìm trong một tập hợp hữu hạn.

Ví dụ 1. Giả sử ta muốn tìm tất cả các nghiệm hữu tỷ của đa thức $P(x)=x^3-5x^2+x+10.$ Theo định lí, nghiệm hữu tỷ của $P$ phải là nghiệm nguyên và nó bằng $0$ hoặc là ước của $10$ . Suy ra nghiệm hữu tỷ của $P$ thuộc tập hợp $\{0,\pm 1,\pm 2,\pm 5,\pm 10\}.$ Kiểm tra trực tiếp ta thấy nghiệm hữu tỷ của đa thức là $2$ .

Định nghĩa 1. Một đa thức khác không với hệ số nguyên được gọi là nguyên bản nếu các hệ số của nó chỉ có ước dương chung là $1$ .

Định lí 2 (Bổ đề Gauss). Tích của hai đa thức nguyên bản là một đa thức nguyên bản.
Chứng minh. Giả sử $f(x)=g(x) h(x)$ là tích của hai đa thức nguyên bản và $p$ là một số nguyên tố chia hết mọi hệ số của $f$ . Viết $g(x)=\sum a_kx^k$ và $h(x)=\sum b_mx^m$ . Do $f$ và $g$ là nguyên bản nên ta có thể chọn các chỉ số $i$ và $j$ lớn nhất để $p\nmid a_i$ và $p\nmid b_j$ . Khi đó hệ số của $x^{i+j}$ trong $f$ bằng $a_ib_j$ , số này không chia hết cho $p$ , vô lý. $\Box$

Hệ quả. Cho $f(x)$ là một đa thức khác hằng với hệ số nguyên sao cho $f(x)=g(x)h(x)$ , ở đây $g$ và $h$ là các đa thức khác hằng với hệ số hữu tỷ. Khi đó $f$ là tích của hai đa thức với hệ số nguyên có bậc bằng bậc của $g$ và $h$ .
Chứng minh. Từ giả thiết ta có thể viết $\displaystyle f(x)=\frac{m}{n}g_1(x)h_1(x)$ , trong đó $m$ và $n$ là hai số nguyên dương nguyên tố cùng nhau, và $g_1,h_1$ là hai đa thức nguyên bản có bậc lần lượt bằng bậc của $g_1$ , $h_1$ . Nếu $a$ là một hệ số của $g_1h_1$ thì $n \mid m a$ do $f$ có hệ số nguyên, suy ra $n \mid a$ . Như vậy $n$ là số nguyên dương chia hết mọi hệ số của đa thức $g_1h_1$ , là một đa thức nguyên bản theo bổ đề Gauss, suy ra $n=1$ . Khi đó $f=(m g_1)(h_1)$ , đây là phân tích ta cần. $\Box$
Bằng quy nạp ta dễ dàng mở rộng kết quả trên cho nhiều hơn hai thừa số.

Định lí 3 (Tiêu chuẩn Eisenstein). Cho số nguyên dương $n$ và đa thức $f(x)=a_0+a_1x+\cdots+a_nx^n$ có bậc $n$ với hệ số nguyên. Giả sử có số nguyên tố $p$ sao cho $a_n$ không chia hết cho $p$ , các hệ số $a_0,a_1,\ldots,a_{n-1}$ chia hết cho $p$ và $a_0$ không chia hết cho $p^2$ . Khi đó $f$ là đa thức bất khả quy trên $\mathbb{Q}$ .

Chứng minh. Giả sử $f$ không bất khả quy trên $\mathbb{Q}.$ Khi đó theo hệ quả trên, tồn tại các đa thức khác hằng với hệ số nguyên $g$ và $h$ sao cho $f=gh.$ Viết $g(x)=b_0+b_1x+\cdots+b_kx^k$ và $h(x)=c_0+c_1x+\cdots+c_mx^m,$ trong đó $k$ , $m$ là các số nguyên dương và $b_kc_m\not=0.$ Vì $b_0c_0=a_0$ chia hết cho $p$ nhưng không chia hết cho $p^2$ nên $p\mid b_0$ hoặc $p\mid c_0$ và không xảy ra cả hai. Giả sử mà không làm mất tính tổng quát rằng $p\mid b_0$ và $p\nmid c_0.$

Nếu $b_0,b_1,\ldots,b_u (u<k)$ chia hết cho $p$ thì bằng cách để ý đến hệ số của $x^{u+1}$ trong hai vế của $f=gh$ ta có $b_{u+1}$ cũng chia hết cho $p.$ Vậy bằng quy nạp theo $l$ , ta có $p\mid b_l$ với mỗi $l=0,1,\ldots,k$ . Suy ra $a_n=b_kc_m$ chia hết cho $p$ , vô lý. $\Box$

Hệ quả. Với mỗi số nguyên tố $p$ , đa thức $\Phi_p(x)=1+x+\cdots+x^{p-1}$ bất khả quy trên $\mathbb{Q}$ .

Chứng minh. Xét một số nguyên tố $p$ . Ta có

$\displaystyle \Phi_p(x+1)=\frac{(x+1)^p-1}{x}=x^{p-1}+C_p^1x^{p-2}+C_p^2x^{p-3}+\cdots+p,$ và khi $1 \leq i \leq p-1$ thì $p$ chia hết $C_p^i$ . Suy ra theo tiêu chuẩn Eisenstein, đa thức $\Phi_p(x+1)$ bất khả quy trên $\mathbb{Q}$ , do đó $\Phi_p(x)$ bất khả quy trên $\mathbb{Q}$ . $\Box$

Continue reading →

A proof of Cauchy–Davenport theorem

Trong bài này tôi sẽ giới thiệu một chứng minh của định lí Cauchy-Davenport.

Định lí Cauchy – Davenport. Cho số nguyên tố $p$ và hai tập con khác rỗng $A,B$ của $\mathbb{Z}/p\mathbb{Z}.$ Khi đó

$|A+B|\geq\min (p,|A|+|B|-1).$

Chứng minh. Ta chứng minh khẳng định bằng quy nạp theo $|B|$ . Khi $|B|=1$ ta có

$|A+B|=|A|=\min (p,|A|)=\min (p,|A|+|B|-1).$ Suy ra khẳng định đúng khi $|B|=1$ . Khi $|B|=2$ ta viết $B=\{b_1,b_2\}$ và $A=\{a_1,a_2,\ldots,a_m\},$ ta có ngay $|A+B|\geq m$ .

Nếu $|A+B|= m$ thì $\{b_1+a_1,\ldots,b_1+a_m\}=\{b_2+a_1,\ldots,b_2+a_m\},$ suy ra $mb_1\equiv mb_2\pmod{p}$ , hay $m=p$ . Khi đó $|A+B|=p\geq\min (p,|A|+|B|-1).$

Nếu $|A+B|>m$ thì $|A+B|\geq m+1\geq\min (p,m+1)=\min (p,|A|+|B|-1).$

Vậy khẳng định đúng khi $|B|=2$ . Giả sử khẳng định đúng với mỗi tập $B$ thỏa mãn $|B|<n,$ trong đó $n\geq 3.$ Ta sẽ chứng minh khẳng định đúng với mọi tập $B$ có $|B|=n.$ Xét một tập $B$ thỏa mãn $|B|=n$ . Đặt $|A+B|=l,|A|=m$ và viết $B=\{b_1,b_2,\ldots,b_n\}.$ Xét ba trường hợp

Trường hợp 1. $l\geq p.$

Ta có $|A+B|=l\geq p\geq\min (p,|A|+|B|-1).$

Trường hợp 2. $m+n>p.$

Ta có $A+B=\{0,1,2,\ldots,p-1\}$ , thật vậy với mỗi $g\in \{0,1,2,\ldots,p-1\}$ , hai tập $g-A$ và $B$ có giao khác rỗng vì chúng là các tập con của tập $\{0,1,2,\ldots,p-1\}$ và có tổng số phần tử lớn hơn $p$ . Lấy $h\in g-A\cap B$ ta có ngay $g=b=g-a\,\, (a\in A,b\in B),$ suy ra $g=a+b\in A+B$ . Từ đây ta có $|A+B|=p\geq\min (p,|A|+|B|-1).$

Trường hợp 3. $l<p$ và $m+n\leq p.$

Ở trường hợp này thì $\min (p,|A|+|B|-1)=\min (p,m+n-1)=m+n-1.$ Áp dụng giả thiết quy nạp cho hai tập $C=A+B$ và $\{b_1,b_n\}$ ta có $|C+\{b_1,b_n\}|\geq\min (p,|C|+|\{b_1,b_n\}|-1)=\min (p,l+1)=l+1,$ suy ra $C+b_1\not = C+b_n$ , do đó tồn tại số nguyên $x$ sao cho $x-b_1\in A+B$ và $x-b_n\not\in A+B$ . Từ đây ta thấy tồn tại số nguyên dương $r<n$ sao cho $x-b_i\in A+B,\,\forall i=\overline{1,r}$ và $x-b_i\not\in A+B,\,\forall i=\overline{r+1,n}$ . Áp dụng giả thiết quy nạp cho hai tập $A$ và $B^{\prime}=\{b_{r+1},b_{r+2},\ldots,b_n\}$ ta có

$|A+B^{\prime}|\geq \min (p,|A|+|B^{\prime}|-1)=\min (p,m+n-r-1)=m+n-r-1.$ Ta có $x-b_i\not\in A+B^{\prime},\,\forall i=\overline{1,r}$ , vì nếu chẳng hạn $x-b_1\in A+B^{\prime}$ thì

$x-b_1= a+b_{s}\Rightarrow x-b_s\in A+B,$ điều này trái với cách chọn $r$ . Vậy $|A+B|\geq r+|A+B^{\prime}|\geq r+m+n-r-1=m+n-1,$ và định lí được chứng minh. $\Box$

Bằng quy nạp ta chứng minh được kết quả sau.

Hệ quả. Cho số nguyên dương $h>1,$ số nguyên tố $p$ và $h$ tập con khác rỗng $A_1,$ $A_2,\ldots,$ $A_h$ của $\mathbb{Z}/p\mathbb{Z}.$ Khi đó $\displaystyle \mid A_1+A_2+\cdots+A_h\mid \geq \min \left(p,\sum_{i=1}^h\mid A_i\mid-h+1\right).$

Combinations

Cho một tập $A$ có $n$ phần tử ( $n\in\mathbb{N}$ ) và $0\leq k\leq n$ là một số nguyên. Một $k-$ tổ hợp (một tổ hợp chập $k$ ) của $A$ là một tập con $k$ phần tử của $A$ .

Ví dụ 1. Các $3-$ tổ hợp của $A=\{a,b,c,d\}$ là

$\{a,b,c\},\{b,c,d\},\{c,d,a\},\{d,a,b\}.$

Định lí 1. Cho một tập $A$ có $n$ phần tử ( $n\in\mathbb{N}$ ) và $0\leq k\leq n$ là một số nguyên. Khi đó số $k-$ tổ hợp của $A$ bằng $C_n^k=\dfrac{A_n^k}{k!}=\dfrac{n!}{k!(n-k)!}.$

Chứng minh. Sự khác nhau giữa một $k-$ tổ hợp và một $k-$ hoán vị chính là một đằng không quan tâm đến thứ tự, trong khi đằng kia có quan tâm đến thứ tự. Tận dụng điều này ta có chứng minh như sau.

Một $k-$ hoán vị của $A$ có thể hình thành sau hai bước: Đầu tiên, chọn một $k-$ tổ hợp của $A$ ; sau đó xếp $k$ phần tử của tập này thành một hàng. Bởi vì có $C_n^k$ cách để làm bước một, $k!$ cách để làm bước hai nên theo nguyên lý nhân ta có $A_n^k=C_n^k\times k!.$ $\Box$

Ví dụ 2. Có bao nhiêu xâu nhị phân độ dài $7$ mà có đúng ba số $0$ ?

Lời giải. Một xâu nhị phân có tính chất như trong đề bài sẽ được hình thành khi ta chọn $3$ vị trí trong $7$ vị trí để viết số $0.$ Do đó số xâu thỏa mãn là $C_7^3.$ $\Box$

Ví dụ 3. Có bao nhiêu cách có thể thành lập một hội đồng gồm $5$ thành viên từ một nhóm có $11$ người chứa $4$ giáo viên và $7$ học sinh nếu

(1) Không có thêm điều kiện gì?

(2) Hội đồng chứa đúng $2$ giáo viên?

(3) Hội đồng chứa ít nhất $3$ giáo viên?

(4) Giáo viên $A$ và học sinh $B$ không thể cùng nằm trong hội đồng?

Hướng dẫn giải. (1) $C_{11}^5$ . (2) $C_4^2\times C_7^3$ . (3) $3$ hoặc $4$ giáo viên có thể nằm trong hội đồng, đáp số $91$ .

(4) Dùng quy tắc trừ, đáp số $378$ . $\Box$

Ví dụ 4. Cho $n$ là một số nguyên dương và $A$ là một tập có $2n$ phần tử. Có bao nhiêu cách phân hoạch $A$ thành các tập có $2$ phần tử?

Lời giải 1. Đầu tiên, cố định một phần tử $x$ của $A$ và chọn một phần tử trong $2n-1$ phần tử còn lại của $A$ để ghép lại với $x$ tạo thành một khối của phân hoạch; sau đó cố định một phần tử $y$ trong các phần tử còn lại của $A$ và chọn một phần tử trong $2n-3$ phần tử còn lại của $A$ để ghép lại với $y$ tạo thành một khối của phân hoạch; ta cứ làm như vậy cho đến khi còn $2$ phần tử thì đây chính là khối còn lại của phân hoạch. Theo quy tắc nhân, số phân hoạch thoả mãn là $(2n-1)\times (2n-3)\times\cdots\times 1$ . $\Box$

Lời giải 2. Chọn một tập con có $2$ phần tử của $A$ làm khối thứ nhất, sau đó chọn một tập con có $2$ phần tử của tập hợp gồm $2n-2$ phần tử còn lại làm khối thứ hai, ta cứ làm như vậy cho đến khi còn hai phần tử thì đây chính là khối thứ $n$ . Vì thứ tự các khối là không quan trọng nên số các phân hoạch thoả mãn là $\dfrac{C_{2n}^2\times C_{2n-2}^2\times\cdots\times C_2^2}{n!}$ . $\Box$

Lời giải 3. Ta xếp $2n$ phần tử của $A$ thành một hàng vào $2n$ vị trí như hình dưới đây

$\{(1),(2)\},\{(3),(4)\},\cdots,\{(2n-1),(2n)\}$ có $(2n)!$ cách để làm điều này. Vì trong mỗi tập con có $2$ phần tử thứ tự các phần tử là không quan trọng và thứ tự các khối của phân hoạch là không quan trọng nên số phân hoạch thoả mãn là