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$

Ví dụ 4. Tìm tất cả cặp số nguyên dương $(x,y)$ sao cho $x^{2}y+x+y$ là một bội của $xy^{2}+y+7$ .

Lời giải 1. Các cặp phải tìm là $(11,1),$ $(49,1)$ , và $(7k^2, 7k)$ ( $k\in\mathbb{N}^*$ ). Giả sử $(x,y)$ là một cặp số có các tính chất trong đề bài. Khi đó tồn tại số nguyên dương $k$ sao cho

$k(xy^2+y+7) = x^2y+x+y.\quad (1)$

Viết lại (1) dưới dạng $7k-y = (xy+1)(x-ky).\quad (2)$

Hai vế của (2) không âm. Thật vậy, nếu $7k-y < 0$ thì

$\mid 7k-y\mid < y < xy+1 \leq \mid xy+1\mid \mid x-ky\mid ,$ vô lý. Bây giờ ta xét hai trường hợp:

Trường hợp 1: Cả hai vế của (2) bằng không. Khi đó $(x,y) = (7k^2, 7k)$ .

Trường hợp 2: Cả hai vế của (2) dương. Khi đó $x > ky$ và $7k > 7k-y = (xy+1)(x-ky) \geq xy+1 > y^2k+1.$ Suy ra $y < 3$ . Đến đây ta chỉ cần xét các trường hợp $y = 1$ và $y=2$ . $\Box$

Lời giải 2. Giả sử $(x,y)$ là một cặp số có các tính chất trong đề bài. Khi đó

$xy^2+y+7 \mid 7x-y^2.\quad (3)$

Nếu $7x-y^2=0$ thì theo định lí 1 ta có $(x,y)=(7k^2, 7k)$ , trong đó $k$ là một số nguyên dương. Trong trường hợp còn lại, từ (3) ta có

$xy^2+y+7 \le \mid 7x-y^2\mid < 7x+y^2,$ suy ra $y^2(x-1) < 7x.$ Từ bất đẳng thức cuối ta thu được $y \le 3$ và lại làm tiếp như lời giải đầu. $\Box$

Với hai số nguyên $a$ và $b$ , số nguyên $d$ được gọi là một ước chung của $a$ và $b$ nếu $d \mid a$ và $d\mid b.$ Nếu $a$ và $b$ không đồng thời bằng không thì tập các ước chung của $a$ và $b$ là một tập hữu hạn và khác rỗng, phần tử lớn nhất của tập này được gọi là ước chung lớn nhất của $a$ và $b.$

Định nghĩa 2. Cho $a$ và $b$ là hai số nguyên không đồng thời bằng không. Ước chung lớn nhất của $a$ và $b$ , ký hiệu là bởi $(a,b)$ , là số nguyên dương $d$ thỏa mãn các điều kiện sau:

(1) $d \mid a$ và $d \mid b$ .

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

Định lí sau nói rằng $(a, b)$ có thể biểu diễn như là một tổ hợp tuyến tính của $a$ và $b$ .

Định lí 3. Cho $a$ và $b$ là hai số nguyên không đồng thời bằng không. Khi đó tồn tại các số nguyên $x$ và $y$ sao cho $(a, b)=a x+b y.$

Chứng minh. Gọi $S$ là tập tất cả các số nguyên dương có dạng $a m+b n$ , trong đó $m$ và $n$ là các số nguyên. Ta nhận thấy $S$ là một tập hợp con khác rỗng của tập hợp số nguyên dương, nên có phần tử nhỏ nhất, ký hiệu bởi $d$ . Do $d$ là phần tử của $S$ nên có các số nguyên $x$ và $y$ sao cho $d=a x+by$ . Ta sẽ chứng minh $d=(a, b)$ . Theo định lí 1, tồn tại các số nguyên $q$ và $r$ để $a=q d+r$ và $0 \leq r<d$ . Ta có $r=a(1-q x)+b(-q y)$ và $r$ không thể dương do cách chọn $d$ , suy ra $r=0$ và bởi thế $a$ chia hết cho $d$ . Hoàn toàn tương tự, $d \mid b$ , do đó $d$ là một ước chung của $a$ và $b$ . Bây giờ gọi $c$ là một ước chung của $a$ và $b$ . Khi đó $c \mid a x+b y$ , nghĩa là $c \mid d,$ suy ra $c\leq |c| \leq d$ . Vậy $d=(a, b)$ . $\Box$

Chú ý 1. Định lí trên không cho ta cách tìm $x$ và $y$ . Khi học thuật toán Euclid ta sẽ trở lại vấn đề này.

Hệ quả 3.1. Cho $a$ và $b$ là hai số nguyên không đồng thời bằng không. Khi đó tập các số nguyên có dạng $a x+b y$ , trong đó $x$ và $y$ là các số nguyên, chính là tập các bội của $(a, b)$ .

Định nghĩa 3. Cho $a$ và $b$ là hai số nguyên không đồng thời bằng không. $a$ và $b$ được gọi là nguyên tố cùng nhau nếu $(a, b) = 1.$

Định lí 4. Cho $a$ và $b$ là hai số nguyên không đồng thời bằng không. Khi đó $a$ và $b$ nguyên tố cùng nhau khi và chỉ khi tồn tại hai số nguyên $x$ và $y$ sao cho $1 = ax + by.$

Hệ quả 4.1. Nếu $(a, b) = 1$ thì $(a^m,b^n)=1$ , với mọi số nguyên dương $m$ và $n$ .

Hệ quả 4.2. Nếu $a \mid c$ , $b \mid c$ , và $(a, b) = 1$ , thì $ab \mid c.$

Chứng minh. Vì $(a,b)=1$ nên ta có thể biểu diễn $1=ax+by$ , với hai số nguyên $x$ và $y$ . Từ biểu diễn này ta có $c=c.1=(ac)x+(bc)y,$ để ý thêm $a \mid c$ và $b \mid c$ , ta được $ab\mid c$ . $\Box$

Định lí 5 (Bổ đề Euclid). Nếu $a \mid b c$ và $(a, b)=1$ thì $a \mid c$ .

Hệ quả 5.1. Cho số nguyên $n>1$ và hai số nguyên dương $x$ , $y$ nguyên tố cùng nhau. Khi đó nếu $xy$ là lũy thừa bậc $n$ của một số nguyên dương thì $x$ và $y$ cũng là các lũy thừa bậc $n$ của một số nguyên dương.

Chứng minh. Từ giả thiết, tồn tại số nguyên dương $z$ sao cho $xy=z^n$ , hay $\displaystyle \frac{x}{z}=\frac{z^{n-1}}{y}.\quad (4)$

Đặt $d=(x,z)$ và viết $x=da$ , $z=db$ . Khi đó từ (4) và bổ đề Euclid, tồn tại số nguyên dương $k$ để $d^{n-1}=ka$ và $y=b^nk$ . Vì $x=da$ và $(x,y)=1$ nên $(k,d)=1$ , suy ra $(k,d^{n-1})=1$ . Bây giờ để ý thêm $k\mid d^{n-1}$ , ta sẽ có $k=1$ . Bởi vậy $x=d^n$ và $y=b^n$ . $\Box$

Bây giờ ta xét một số ví dụ liên quan đến ước chung lớn nhất của hai số nguyên.

Ví dụ 5. Chứng minh rằng số $\displaystyle \dfrac {(m, n)}{n} \dbinom {n}{m}$ là một số nguyên với mọi số nguyên dương $m$ và $n$ mà $n \ge m$ .

Lời giải. Theo định lí 3, $(m,n)=an+bm,$ với các số nguyên $a$ và $b$ nào đó. Từ đây và $n\geq m$ , ta có

$\displaystyle\frac{(m,n)}n\binom nm=a\binom nm +\frac{bm}n\binom nm=a\binom nm+b\binom{n-1}{m-1},$ là số nguyên. $\Box$

Ví dụ 6. Tìm tất cả các cặp số nguyên dương $(m,n)$ sao cho $\displaystyle \frac {n^3 + 1}{mn - 1}$ là một số nguyên.

Lời giải. Các cặp phải tìm là $(1,2),(2,1),(1,3),(3,1),(2,2),(2,5),(5,2),(3,5),(5,3).$ Kiểm tra thấy các cặp trong danh sách thỏa mãn yêu cầu của đề bài. Với hai số nguyên dương $m$ và $n$ bất kỳ ta có

$n^3(m^3+1)=(m^3n^3-1)+(n^3+1)$ nên theo bổ đề Euclid, $n^3+1$ chia hết cho $mn-1$ khi và chỉ khi $m^3+1$ chia hết cho $mn-1$ . Bởi vậy, cặp $(m,n)$ thỏa mãn yêu cầu của đề bài khi và chỉ khi cặp $(n,m)$ thỏa mãn yêu cầu của đề bài.

Bây giờ ta chỉ xét $m\geq n$ và giả sử $(m,n)$ là một cặp phải tìm.

Nếu $m=n$ , ta tìm được cặp $(2,2).$

Nếu $m>n=1$ , ta tìm được $(2,1)$ và $(3,1).$

Nếu $m>n>1$ , do số nguyên dương $\displaystyle \frac{n^3+1}{mn-1}+1$ là một bội của $n$ nên tồn tại số nguyên dương $k$ để $\displaystyle \frac{n^3+1}{mn-1}=kn-1.$ Từ đẳng thức này và $m>n>1$ ta có $\displaystyle kn-1<\frac{n^3+1}{n^2-1}=n+\frac{1}{n-1},$ suy ra $k=1.$ Từ đó thu được hai cặp $(5,2)$ và $(5,3).$ $\Box$

Ví dụ 7. Tìm tất cả các cặp số nguyên dương $(x,y)$ sao cho $x+y^2+z^3=x y z,$ ở đây $z$ là ước chung lớn nhất của $x$ và $y$ .

Lời giải. Các cặp $(x, y)$ cần tìm là $(4,2),(4,6),(5,2)$ , và $(5,3)$ .

Kiểm tra thấy các cặp trong danh sách thỏa mãn yêu cầu của đề bài. Bây giờ gọi $(x,y)$ là một cặp số nguyên dương thỏa mãn. Viết $x=zc$ và $y=zb$ . Khi đó đẳng thức trong đề bài trở thành

$c+z b^2+z^2=z^2 c b.\quad (5)$

Từ đẳng thức này ta có $c$ chia hết cho $a$ , hay $c=z a$ với số nguyên dương $a$ . Do không thể có $z=b=1$ , ta viết được (5) dưới dạng

$\displaystyle a=\frac{b^2+z}{z^2 b-1}.\quad (6)$

Đến đây ta xét ba trường hợp.

Trường hợp 1: $z=1$ . Từ (6) ta được hai cặp $(5,2)$ và $(5,3)$ .

Trường hợp 2: $z=2$ . Ta tìm được $(4,2)$ và $(4,6)$ .

Trường hợp 3: $z\geq 3$ . Từ (6) ta có $b+z^3$ chia hết cho $z^2b-1$ , suy ra ${b+z^3}\geq {z^2 b-1}$ hay $\displaystyle b \leq \frac{z^2-z+1}{z-1}.$ Từ bất đẳng thức này và $z \geq 3$ ta có $b \leq z$ , để ý lại (6) ta thu được $\displaystyle a \leq \frac{z^2+z}{z^2-1}<2,$ suy ra $a=1$ . Nhưng khi $a=1$ không khó khăn ta thấy (6) không đúng. $\Box$

Ví dụ 8. Cho số nguyên $k$ lớn hơn $1$ . Chứng minh rằng tích của ba số nguyên dương liên tiếp không phải là lũy thừa bậc $k$ của một số nguyên dương.

Lời giải. Giả sử ngược lại, khi đó tồn tại các số nguyên dương $x>1$ và $y$ sao cho $(x-1)x(x+1)=y^k.$ Viết đẳng thức này dưới dạng $x(x^2-1)=y^k$ , để ý rằng $x$ và $x^2-1$ là hai số nguyên dương nguyên tố cùng nhau, nên theo hệ quả 5.1, tồn tại các số nguyên dương $a$ và $b$ để $x=a^k$ và $x^2-1=b^k$ . Vì $k>1$ nên $\sum a^{2i}b^{k-i-1}>1$ , suy ra $1\not=a^{2k}-b^k$ , vô lý. $\Box$

Tổng quát hơn, quãng năm 1968, P. Erdos và J. L. Selfridge đã chứng minh được kết quả:

Định lí 6 (P. Erdos và J. L. Selfridge). Tích của hai hay nhiều hơn số nguyên dương liên tiếp không bao giờ là lũy thừa bậc lớn hơn $1$ của một số nguyên dương.

Trong một số cấu trúc không có quan hệ thứ tự, như tập các đa thức chẳng hạn, định lí sau thường được dùng để định nghĩa ước chung lớn nhất của hai phần tử.

Định lí 7. Cho $a$ và $b$ là hai số nguyên không đồng thời bằng không. Số nguyên dương $d$ là ước chung lớn nhất của $a$ và $b$ khi và chỉ khi hai điều kiện sau được thỏa mãn

(1) $d \mid a$ và $d \mid b$ .

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

Ước chung lớn nhất của hai số có thể được tìm bằng cách liệt kê tất cả ước chung của hai số và lấy số lớn nhất. Nhưng cách làm này khiến ta rất vất vả khi làm việc với các số lớn. Có một cách đơn giản hơn, dùng thuật toán Euclid. Thuật toán này có thể mô tả như sau: Xét hai số nguyên dương $a$ và $b$ thỏa mãn $a > b$ . Đầu tiên, theo thuật toán chia ta viết

$a=q_1 b+r_1, \quad 0 \leq r_1<b.$ Nếu $r_1=0$ thì $(a, b)=b$ , và dừng. Nếu không, dùng thuật toán chia ta viết $b=q_2 r_1+r_2, \quad 0 \leq r_2<r_1.$ Nếu $r_2=0$ thì dừng, nếu không, ta lại viết $r_1=q_3 r_2+r_3, \quad 0 \leq r_3<r_2.$ Quy trình này không thể tiếp tục mãi vì số dư giảm sau mỗi bước. Giả sử sau một số lần thực hiện ta có số dư $r_{n+1}=0$ .

$a=q_1 b+r_1, \quad 0<r_1<b$

$b =q_2 r_1+r_2, \quad 0<r_2<r_1$

$r_1 =q_3 r_2+r_3, \quad 0<r_3<r_2$

$\vdots$

$r_{n-2} =q_n r_{n-1}+r_n, \quad 0<r_n<r_{n-1}$

$r_{n-1} =q_{n+1} r_n+0.$

Đến đây ta cần một bổ đề, bạn đọc chứng minh nó xem như bài tập.

Bổ đề 1. Nếu $a=q b+r$ thì $(a, b)=(b, r)$ .

Theo bổ đề này thì $(a,b)=(b,r_1)=(r_1,r_2)=\ldots=(r_{n-1},r_n)=r_n.$

Ví dụ 9. Viết thuật toán Euclid cho $1728$ và $270$ ta có

$1728=6 \cdot 270+108$

$270 =2 \cdot 108+54$

$108 =2 \cdot 54+0.$

Suy ra $(1728,270)=54.$ Từ dãy đẳng thức trên ta tìm được cách biểu diễn $(1728,270)$ như là một tổ hợp tuyến tính của $1728$ và $270$ , thật vậy $54 =270-2\cdot 108=270-2(1728-6\cdot 270)=(-2) \cdot 1728+ 13 \cdot 270,$ do đó $(1728,270)= (-2) \cdot 1728+ 13 \cdot 270.$ $\Box$

Định nghĩa 4. Bội chung nhỏ nhất của hai số nguyên khác không $a$ và $b$ , ký hiệu bởi $[a,b]$ , là số nguyên dương $m$ thỏa mãn đồng thời hai điều kiện sau:

(1) $a\mid m$ và $b\mid m.$

(2) Nếu $c$ là một số nguyên dương thỏa mãn $a \mid c$ và $b \mid c$ , thì $m\leq c.$

Ta có ngay mối liên hệ giữa bội chung nhỏ nhất và ước chung lớn nhất.

Định lí 8. Với mỗi số nguyên dương $a$ và $b$ , $[a, b] \cdot (a, b) = ab.$

Khái niệm ước chung lớn nhất và bội chung nhỏ nhất của hai số nguyên có thể mở rộng một cách tự nhiên lên khái niệm ước chung lớn nhất và bội chung nhỏ nhất của nhiều số nguyên. Bạn đọc hãy chứng minh các kết quả sau xem như là các bài tập về nhà cuối cùng.

Định lí 9. Với các số nguyên không đồng thời bằng không $b_1, b_2, \cdots, b_n$ có ước chung lớn nhất là $g$ , tồn tại các số nguyên $x_1, x_2, \cdots, x_n$ để $g=\sum_{j=1}^n b_j x_j.$ Ước chung lớn nhất $g$ là giá trị dương bé nhất của tổng $\displaystyle\sum_{j=1}^n b_j y_j$ khi $y_j$ là các số nguyên, $g$ là ước dương chung của $b_1, b_2, \cdots, b_n$ chia hết cho mọi ước chung của chúng.

Định lí 10. Nếu $b$ là một bội chung của $a_1, a_2, \cdots, a_n$ , thì $\left[a_1, a_2, \cdots, a_n\right] \mid b$ . Nếu $m=\left[a_1, a_2, \cdots, a_n\right]$ thì $\{0, \pm m, \pm 2 m, \pm 3 m, \cdots\}$ là tập tất cả các bội chung của $a_1, a_2, \cdots, a_n.$

Định lí 11. Nếu $c_1,c_2,\ldots,c_n$ là các số nguyên khác không thì $(c_1,c_2,\ldots,c_n)=((c_1,c_2,\ldots,c_{n-1}),c_n)$ và $[c_1,c_2,\ldots,c_n]=[[c_1,c_2,\ldots,c_{n-1}],c_n].$

—

Các em học sinh chứng minh lại một cách chi tiết các định lí và hệ quả nhé! Đừng bỏ qua chúng! Những ví dụ trong bài các em cũng phải làm rõ hơn các lập luận. Do khuôn khổ của một bài viết trên blog nên tôi không cho thêm các ví dụ và bài tập liên quan đến Toán Olympic, tôi sẽ làm việc này vào một dịp khác. Bài viết cũng là tài liệu tự đọc cho các bạn học sinh lớp 9 và lớp 10 đang theo học tại $\mathbf{T}^{\prime}s\, \mathfrak{Lab}$ .

M	T	W	T	F	S	S
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

Divisibility theory in the integers

Published by Nguyen Trung-Tuan

3 thoughts on “Divisibility theory in the integers”

Leave a comment Cancel reply

Share this:

Related

Published by Nguyen Trung-Tuan

3 thoughts on “Divisibility theory in the integers”

Leave a comment Cancel reply