Divisibility theory in the integers

Trong bài này chúng tôi sẽ trình bày quan hệ chia hết trên tập các số nguyên. Bài viết là tài liệu tự học của các học sinh lớp 10 đang học tại T’s Lab, nhưng các bạn học sinh lớp 8 hoặc 9 xuất sắc có thể hiểu được toàn bài mà không gặp khó khăn nào. Nhiều chứng minh trong bài dùng tính chất sau của tập các số nguyên không âm.

Mỗi tập khác rỗng gồm các số nguyên không âm đều có phần tử nhỏ nhất.

Đầu tiên chúng ta đến với định lí nền tảng của toàn bài.

Định lí 1 (Thuật toán chia). Cho hai số nguyên $a$ và $b$ với $b>0.$ Khi đó tồn tại đúng một cặp số nguyên $(q,r)$ thỏa mãn

$a=q b+r$ và $0 \leq r<b$ . Hai số $q$ và $r$ lần lượt được gọi là thương và dư trong phép chia $a$ cho $b$ .

Chứng minh. Gọi $S$ là tập hợp tất cả các số nguyên không âm có dạng $a-xb$ , với một số nguyên $x$ . Ta thấy $S$ khác rỗng nên nó có phần tử nhỏ nhất, ký hiệu là $r$ . Từ định nghĩa của $S$ , ta có thể viết $r=a-q b,$ trong đó $q$ là một số nguyên. Nếu $r \geq b$ thì $a-(q+1)$ là một phần tử nhỏ hơn $r$ của $S$ , vô lý, do đó $r<b$ . Bây giờ giả sử $(q,r)$ và $(q^{\prime},r^{\prime})$ là hai cặp có tính chất nói đến trong định lí. Khi đó $a=q b+r=q^{\prime} b+r^{\prime}$ và $0 \leq r<b, 0 \leq r^{\prime}<b$ . Từ đây ta có $\left|r^{\prime}-r\right|=b\left|q-q^{\prime}\right|,$ để ý thêm $\left|r^{\prime}-r\right|<b$ , ta thu được $0 \leq\left|q-q^{\prime}\right|<1.$ Suy ra $q=q^{\prime}$ , và $r=r^{\prime}$ . $\Box$

Ví dụ 1. Từ định lí 1 ta thấy mọi số nguyên đều có thể viết được dưới dạng $2k$ hoặc $2k+1$ với một số nguyên $k.$ Tương tự, mọi số nguyên đều có thể viết được dưới dạng $3k$ , $3k+1$ , hoặc $3k+2$ với một số nguyên $k.$ $\Box$

Định nghĩa 1. Cho hai số nguyên $a$ và $b$ với $b$ khác $0$ . Khi đó $a$ được gọi là chia hết cho $b$ , ký hiệu $b \mid a$ , nếu tồn tại số nguyên $c$ sao cho $a=bc$ . Ta viết $b \nmid a$ khi $a$ không chia hết cho $b$ .

Khi $b \mid a$ , ta cũng nói $b$ là một ước của $a$ , hay $a$ là một bội của $b$ . Ta có ngay lập tức các tính chất sau, chứng minh của chúng là bài tập cho bạn đọc.

Định lí 2. Với các số nguyên $a$ , $b$ , và $c$ , ta có các tính chất sau:

(1) $a\mid 0,1\mid a, a \mid a$ .

(2) $a \mid 1$ khi và chỉ khi $a= \pm 1$ .

(3) Nếu $a \mid b$ và $c \mid d$ , thì $a c \mid b d$ .

(4) Nếu $a \mid b$ và $b \mid c$ , thì $a \mid c$ .

(5) $a \mid b$ và $b \mid a$ khi và chỉ khi $a= \pm b$ .

(6) Nếu $a \mid b$ và $b\neq 0$ , thì $\mid a\mid \leq \mid b\mid$ .

(7) Nếu $a \mid b$ và $a \mid c$ , thì $a \mid(b x+c y)$ với các số nguyên bất kỳ $x$ và $y$ .

Ta xét một số ví dụ có sử dụng các tính chất này.

Ví dụ 2. Cho $a$ , $b$ , $c$ , và $d$ là các số nguyên thỏa mãn $ad-bc>1$ . Chứng minh rằng ít nhất một bốn số đã cho không chia hết cho $ad-bc$ .

Lời giải. Giả sử ngược lại, khi đó cả bốn số $a$ , $b$ , $c$ , và $d$ đều chia hết cho $ad-bc$ . Suy ra $ad$ và $bc$ cùng chia hết cho $(ad-bc)^2$ , do đó $(ad-bc)^2\mid ad-bc,$ điều này không thể xảy ra vì $ad-bc>1$ . $\Box$

Ví dụ 3. Tìm tất cả bộ ba số nguyên $(a,b,c)$ sao cho $1<a<b<c$ và $(a-1)(b-1)(c-1)$ là một ước của $abc-1.$

Lời giải. Các bộ ba phải tìm là $(2,4,8)$ và $(3,5,15)$ . Giả sử $(a,b,c)$ là một bộ ba thỏa mãn các yêu cầu của đề bài. Khi đó ba số $a$ , $b$ và $c$ có cùng tính chẵn-lẻ, do đó $\displaystyle 2 < \frac{abc}{(a-1)(b-1)(c-1)}\leq \frac{a}{a-1} \cdot \frac{a+2}{a+1} \cdot \frac{a+4}{a+3},$ suy ra $a<4.$ Đến đây xét $a=2$ và $a=3$ ta có câu trả lời. $\Box$

Continue reading →

The fundamental theorem of arithmetic

Trong bài này chúng ta sẽ nói một ít về số nguyên tố, trình bày chứng minh định lí cơ bản của số học, và giới thiệu một số kết quả sơ cấp về số nguyên tố. Đây cũng là bài đọc cho các học sinh lớp 9 và các học sinh ôn thi chọn HSG QG tại T’s Lab. Để theo dõi cho dễ dàng bạn đọc nên xem lại bài viết sau:

[1] https://nttuan.org/2023/07/14/divisibility/

Một số nguyên tố là một số nguyên $n$ lớn hơn $1$ có đúng hai ước dương là $1$ và $n$ . Một số nguyên lớn hơn $1$ được gọi là hợp số nếu nó không phải là số nguyên tố. Các số $2,3,$ và $5$ là các số nguyên tố. Các số $4,15,$ và $18$ là các hợp số.

Định lí 1. Mỗi số nguyên lớn hơn $1$ có thể biểu diễn như là tích của các số nguyên tố.
Chứng minh. Giả sử $n$ là một số nguyên lớn hơn $1$ . Nếu $n$ là số nguyên tố thì nó là tích với một thừa số nguyên tố. Nếu không thì $n=n_1 n_2$ , trong đó $n_1$ và $n_2$ là các số nguyên lớn hơn $1$ và bé hơn $n$ . Nếu $n_1$ là một số nguyên tố, ta không làm gì; nếu không thì viết $n_1$ thành tích của hai số nguyên lớn hơn $1$ và bé hơn $n_1$ ; thao tác tương tự với $n_2$ . Tiếp tục thao tác như thế trên các thừa số mới. Quá trình này phải dừng vì không có dãy giảm nghiêm ngặt gồm vô hạn số nguyên dương, khi đó ta có một cách biểu diễn $n$ như là tích của các số nguyên tố. $\Box$

Từ dịnh lí trên, vì các thừa số nguyên tố không nhất thiết phải phân biệt nên mọi số nguyên $n$ lớn hơn $1$ có thể viết được dưới dạng $n=p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r},$
trong đó $p_1, p_2, \cdots, p_r$ là các số nguyên tố phân biệt và $\alpha_1, \alpha_2, \cdots, \alpha_r$ là các số nguyên dương. Biểu diễn này được gọi là phân tích chính tắc của $n$ thành các lũy thừa nguyên tố. Ta sẽ chứng minh rằng biểu diễn này là duy nhất theo nghĩa: đối với mỗi $n$ , bất kỳ biểu diễn nào khác chỉ là sự sắp xếp lại các thừa số.

Continue reading →

Absolute convergence

Cho $\displaystyle (u_n)_{n\geq 1}$ là một dãy các số thực. Chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_n$ được gọi là hội tụ tuyệt đối nếu chuỗi $\displaystyle\sum_{n=1}^{+\infty}\mid u_n\mid$ hội tụ. Chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_n$ được gọi là hội tụ có điều kiện nếu nó hội tụ nhưng không hội tụ tuyệt đối. Trong bài trước (xem [1]) ta đã biết chuỗi điều hòa thay phiên là một chuỗi hội tụ có điều kiện. Theo tiêu chuẩn Cauchy, mọi chuỗi hội tụ tuyệt đối đều là chuỗi hội tụ.

Khi làm việc với các chuỗi hội tụ, ta thường muốn việc nhóm vài số hạng liên tiếp hay sắp xếp lại các số hạng sẽ không ảnh hưởng đến sự hội tụ hoặc tổng của chuỗi. Không khó khăn lắm để thấy rằng việc nhóm các số hạng liên tiếp tạo ra một chuỗi hội tụ có tổng bằng tổng của chuỗi ban đầu. Ta có kết quả quan trọng sau liên quan đến sắp xếp các số hạng của chuỗi.

Định lý 1. Cho $\displaystyle (u_n)_{n\geq 1}$ là một dãy các số thực sao cho chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_n$ hội tụ tuyệt đối. Khi đó với mọi song ánh $\displaystyle\sigma :\mathbb{N}^*\to\mathbb{N}^*$ , chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_{\sigma (n)}$ hội tụ và tổng của nó bằng tổng của chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_n$ .

Chứng minh. Gọi $\displaystyle S$ là tổng của chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_n$ , và $\displaystyle\epsilon$ là một số thực dương bất kỳ. Khi đó tồn tại số nguyên dương $\displaystyle m$ đủ lớn sao cho $\displaystyle \mid S_m-S\mid<\epsilon/2$ và

$\displaystyle\sum_{k=m+1}^{+\infty}\mid u_k\mid <\epsilon/2,$

trong đó $\displaystyle (S_n)_{n\geq 1}$ là dãy các tổng riêng của chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_n$ .

Xét một song ánh $\displaystyle\sigma :\mathbb{N}^*\to\mathbb{N}^*$ . Gọi $\displaystyle (T_n)_{n\geq 1}$ là dãy các tổng riêng của chuỗi $\displaystyle\sum_{n=1}^{+\infty} u_{\sigma (n)}$ , và $\displaystyle N$ là một số nguyên dương sao cho các số $\displaystyle 1$ , $\displaystyle 2$ , $\displaystyle \ldots$ , $\displaystyle m$ đều thuộc tập hợp $\displaystyle\{\sigma (1),\sigma (2),\ldots,\sigma (N)\}.$ Với số nguyên $\displaystyle n>N$ , ta có

$\displaystyle \mid T_n-S\mid\leq \mid T_n-S_m\mid +\mid S_m-S\mid$

$\displaystyle\leq \sum_{k=m+1}^{+\infty}\mid u_k\mid +\mid S_m-S\mid<\epsilon/2+\epsilon/2=\epsilon.$

Suy ra $\displaystyle T_n\to S$ và ta có điều phải chứng minh. $\Box$

Bây giờ giả sử $\displaystyle (u_n)_{n\geq 1}$ là một dãy các số thực sao cho chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_n$ hội tụ có điều kiện. Ta thấy có vô hạn số hạng của dãy là số dương, và có vô hạn số hạng của dãy là số âm. Gọi $\displaystyle (d_i)_{i\geq 1}$ và $(a_i)_{i\geq 1}$ lần lượt là dãy con tất cả các số hạng không âm và dãy con tất cả các số hạng âm của dãy $\displaystyle (u_n)_{n\geq 1}$ . Hai chuỗi $\displaystyle\sum_{n=1}^{+\infty}d_n$ và $\displaystyle\sum_{n=1}^{+\infty}a_n$ đều phân kỳ. Cố định một số thực $\displaystyle \alpha$ . Lấy ra khỏi $\displaystyle (d_i)$ một vài số hạng đầu có tổng lớn hơn $\displaystyle\alpha$ , sau đó lấy ra khỏi $\displaystyle (a_i)$ một vài số hạng đầu để tổng các số được chọn (gồm cả những số được chọn từ $\displaystyle (d_i)$ ) nhỏ hơn $\displaystyle \alpha$ . Tiếp theo, trong dãy $\displaystyle (d_i)$ còn lại, lấy vài số hạng đầu để tổng các số được lấy (gồm cả những số được chọn từ các bước trước) lớn hơn $\displaystyle\alpha$ , sau đó trong dãy $\displaystyle (a_i)$ còn lại, lấy một vài số hạng đầu để tổng các số được lấy (gồm cả những số được chọn từ các bước trước) nhỏ hơn $\displaystyle \alpha$ . Cứ tiếp tục như vậy ta có một chuỗi có tổng bằng $\displaystyle\alpha$ . Ta đã mô tả chứng minh của kết quả sau, chi tiết có trong [2].

Định lý 2 (Định lý chuỗi Riemann). Cho $\displaystyle (u_n)_{n\geq 1}$ là một dãy các số thực sao cho chuỗi $\displaystyle\sum_{n=1}^{+\infty}u_n$ hội tụ có điều kiện. Khi đó với mỗi số thực $\displaystyle\alpha$ , có song ánh $\displaystyle \sigma :\mathbb{N}^*\to\mathbb{N}^*$ sao cho chuỗi $\displaystyle \sum_{n=1}^{+\infty}u_{\sigma (n)}$ hội tụ và tổng của nó bằng $\displaystyle \alpha$ .

Tài liệu tham khảo

[1] https://nttuan.org/2018/12/30/series/

[2] Walter Rudin. Principles of Mathematical Analysis. McGraw Hill, 1976.

Lagrange interpolating polynomial

Đây là bài thứ bốn về đa thức của tôi, các bạn học sinh nên xem lại ba bài trước để học cho dễ dàng hơn.

[1] https://nttuan.org/2007/10/26/poly01/

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

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

—

Đa thức có thể được sử dụng để xấp xỉ các đường cong phức tạp, hay tính giá trị của các hàm logarit và lượng giác. Đầu tiên, chọn một vài dữ liệu đã biết, sau đó tìm một đa thức có bậc đủ bé có cùng dữ liệu đã chọn, cuối cùng xem đa thức vừa tìm được như là hàm số đang xét. Điều này dẫn đến việc tính toán nhanh hơn đáng kể.

Định lí. Cho số nguyên dương $n$ và $n+1$ số phức đôi một khác nhau $x_0,$ $x_1,$ $\ldots,$ $x_{n}.$ Khi đó với mỗi $n+1$ số phức $y_0,$ $y_1,$ $\ldots,$ $y_n,$ có đúng một đa thức $P(x)$ với hệ số phức có bậc không lớn hơn $n$ sao cho

$P(x_i)=y_i,\quad \forall i=\overline{0,n}.$

Chứng minh. Nếu $P$ và $Q$ là các đa thức thỏa mãn các điều kiện của định lí thì đa thức $P-Q$ có bậc không lớn hơn $n$ và có ít nhất $n+1$ nghiệm, suy ra $P-Q$ là đa thức không và $P=Q.$ Mặt khác, đa thức $\displaystyle P(x)=\sum_{i=0}^ny_i\prod_{j\not =i}\frac{x-x_j}{x_i-x_j}$ thỏa mãn $P(x_i)=y_i,\quad \forall i=\overline{0,n},$ do đó định lí được chứng minh. $\Box$

Hệ quả (Công thức nội suy Lagrange). Cho số nguyên dương $n$ và đa thức $P(x)$ với hệ số phức có bậc không lớn hơn $n.$ Khi đó với mỗi $n+1$ số phức đôi một khác nhau $x_0,$ $x_1,$ $\ldots,$ $x_{n},$ ta có

$\displaystyle P(x)=\sum_{i=0}^nP(x_i)\prod_{j\not =i}\frac{x-x_j}{x_i-x_j}.$

Trong công thức trên, $n+1$ số phức $x_0,$ $x_1,$ $\ldots,$ $x_{n}$ được gọi là các nút nội suy. Ta thường dùng công thức nội suy Lagrange trong tình huống: Biết thông tin của $P$ tại các $x_i$ , cần tìm thông tin của $P$ tại $y\not\in \{x_i\}.$

Ví dụ 1. Cho hai đa thức $A(x)=x^{81}+x^{49}+x^{25}+x^9+x$ và $B(x)=x^3-x.$ Tìm dư khi chia $A(x)$ cho $B(x).$

Lời giải. Giả sử $Q(x)$ và $R(x)$ lần lượt là thương và dư trong phép chia $A(x)$ cho $B(x).$ Ta có $A(x)=B(x)Q(x)+R(x)$ và $\deg R<3.$ Vì $B(0)=B(1)=B(-1)=0$ nên $R(0)=0,$ $R(1)=5$ và $R(-1)=-5,$ do đó áp dụng công thức nội suy Lagrange cho $R$ với các nút $0;1$ và $-1$ ta có

$\displaystyle R(x)=R(0).\frac{(x-1)(x+1)}{(0-1)(0+1)}+R(1).\frac{(x-0)(x+1)}{(1-0)(1+1)}+R(-1).\frac{(x-0)(x-1)}{(-1-0)(-1-1)}$

$\displaystyle =\frac{5}{2}x(x+1)-\frac{5}{2}x(x-1)=5x.$ $\Box$

Ví dụ 2. Cho số nguyên dương $n$ và đa thức $P$ có bậc $n$ thỏa mãn $\displaystyle P(k)=\frac{k}{k+1},\quad \forall k=\overline{0,n}.$ Tính $P(n+1).$

Lời giải. Do $P$ có bậc $n$ nên áp dụng công thức nội suy Lagrange cho $P$ với $n+1$ nút $0,$ $1,$ $\ldots,$ $n$ ta có $\displaystyle P(x)=\sum_{k=0}^nP(k)\prod_{j\not =k}\frac{x-j}{k-j}$

$\displaystyle =\sum_{k=0}^n\frac{k}{k+1}\prod_{j\not =k}\frac{x-j}{k-j}=\sum_{k=0}^n\frac{(-1)^{n-k}k}{(k+1)!(n-k)!}\prod_{j\not =k}(x-j),\quad\forall x\in\mathbb{R}.$ Suy ra

$\displaystyle P(n+1)=\sum_{k=0}^n\frac{(-1)^{n-k}k}{(k+1)!(n-k)!}\prod_{j\not =k}(n+1-j)$

$\displaystyle =\sum_{k=0}^n\frac{(-1)^{n-k}k}{(k+1)!(n-k)!}.\frac{(n+1)!}{n+1-k}$

$\displaystyle =\frac{1}{n+2}\sum_{k=0}^nk(-1)^{n-k}C^{k+1}_{n+2}=\frac{1}{n+2}\sum_{k=0}^n\left[(k+1)(-1)^{n-k}C_{n+2}^{k+1}+(-1)^{n-k+1}C_{n+2}^{k+1}\right]$

$\displaystyle =\frac{1}{n+2}\left(\sum_{k=0}^n(-1)^{n-k}(n+2)C_{n+1}^k+\sum_{i=1}^{n+1}(-1)^{n+2-i}C_{n+2}^i\right)=\dfrac{n+1+(-1)^{n+1}}{n+2}. \Box$

Ví dụ 3. Cho số nguyên dương $n$ và các số nguyên $x_0 > x_1 > \ldots > x_n.$ Chứng minh rằng một trong các số $|F(x_0)|,$ $|F(x_1)|,$ $|F(x_2)|,$ $\ldots,$ $|F(x_n)|$ lớn hơn hoặc bằng $\displaystyle \frac{n!}{2^n}.$ Trong đó

$F(x) = x^n + a_1x^{n-1} + \cdots+ a_n$

là một đa thức với hệ số thực.

Lời giải. Giả sử $\displaystyle |F(x_i)|<\dfrac{n!}{2^n},\quad \forall i=\overline{0,n}.$ Áp dụng công thức nội suy Lagrange cho $P$ với $n+1$ nút $x_0,$ $x_1,$ $\cdots,$ $x_n$ ta có

$\displaystyle x^n + a_1x^{n-1} + \cdots+ a_n\equiv \sum_{k=0}^nF(x_k)\prod_{j\not =k}\frac{x-x_j}{x_k-x_j},$ để ý đến hệ số của $x^n$ trong hai vế ta có $\displaystyle 1=\left|\sum_{k=0}^n\prod_{j\not =k}\frac{F(x_k)}{x_k-x_j}\right|\leq \sum_{k=0}^n\prod_{j\not =k}\frac{|F(x_k)|}{|x_k-x_j|}<$ $\displaystyle \sum_{k=0}^n\prod_{j\not =k}\frac{\frac{n!}{2^n}}{|x_k-x_j|}\leq \sum_{k=0}^n\prod_{j\not =k}\frac{\frac{n!}{2^n}}{|k-j|}=1,$ không thể xảy ra điều này. $\Box$

Ví dụ 4. Chứng minh rằng với mỗi số thực $a$ và với mỗi số nguyên dương $n$ ta có

$\displaystyle \sum_{k = 0}^n( - 1)^k\binom{n}{k}(a - k)^n = n!.$

Lời giải. Vế trái là đa thức của $a$ nên chỉ cần chứng minh đẳng thức khi $a$ là số nguyên. Sau đây ta chứng minh đẳng thức khi $a= 0$ và $n\geq 3$ , hay chứng minh

$\displaystyle \sum_{k = 0}^n( - 1)^{n + k}\binom{n}{k}k^n = n!.$ Theo công thức nội suy Lagrange với các nút $1,$ $2,$ $\ldots,$ $n$ ta có $\displaystyle x^n - (x - 1)(x - 2)\cdots (x - n) \equiv \sum_{k = 1}^nk^n\cdot\prod_{i\not = k}\dfrac{x - i}{k - i},\quad\forall x\in\mathbb{R}.$ Nói riêng, khi $x = 0$ ta có $\displaystyle ( - 1)^{n + 1}\cdot n! = \sum_{k = 1}^nk^n\cdot \dfrac{1}{k}\cdot \dfrac{( - 1)^{n - 1}\cdot n!}{(k - 1)!\cdot (n - k)!\cdot ( - 1)^{n - k}},$ từ đây thu được điều cần chứng minh. $\Box$ .

Continue reading →