Ước chung lớn nhất và Bội chung nhỏ nhất - Phạm Thị Thu Hiền

ƯỚC CHUNG LỚN NHẤT, BỘI CHUNG NHỎ NHẤT VÀ LIÊN HỆ GIỮA CHÚNG

PHẠM THỊ THU HIỀN Chuyên Hùng Vương - Phú Thọ Email: Phamhienchv@gmail.com Các khái niệm ước số chung lớn nhất (GCD) và bội số chung nhỏ nhất (LCM) là những khái niệm cơ bản của số học. Cách đây khoảng 2000 năm, con người đã biết đến thuật toán Euclid nổi tiếng và có lẽ là thuật toán cổ nhất của toán học để tìm ước số chung lớn nhất của hai số nguyên a và b với b 6= 0. Với mục đích tìm hiểu sâu hơn sự vận dụng của hai khái niệm này, báo cáo tập trung trình bày một số tính chất của ước số chung lớn nhất, bội số chung nhỏ nhất và mối liên hệ giữa chúng cùng các ví dụ điển hình được chọn lọc từ các cuộc thi chọn học sinh giỏi của các nước.

1 Ước chung lớn nhất

Định nghĩa 1.1. Cho hai số nguyêna và b trong đó ít nhất một số khác 0 . Số nguyên dương d được gọi là ước số chung lớn nhất của a và b nếu:

(i) d | a và d | b (d là ước số chung của a và b), (ii) Nếu c | a và c | b thì c | d.

Kí hiệu ước số chung lớn nhất của a và b là gcd (a, b) hoặc (a, b). Nếu gcd (a, b) = 1 thì ta nói a và b là hai số nguyên tố cùng nhau.

Tính chất 1.2. Sau đây là một số tính chất của ước số chung lớn nhất

(i) gcd (a, b) =d ⇔ gcd a

d; b d

= 1.

(ii) Choclà một số nguyên dương. Khi đó ta cógcd (ca, cb) =c.gcd (a, b). (iii) gcd (a, b) = 1 và b | ac thì b | c.

(iv) Nếu gcd (a, b) = 1 và gcd (a, c) = 1 thì gcd (a, bc) = 1.

(v) Nếu a = bq +r thì gcd (a, b) = gcd (b, r).

(vi) Nếu a = p^α₁¹.p^α₂²...p^α_k^k và b = p^β₁¹.p^β₂²...p^β_k^k với α_i, β_i ∈ N, αi+β_i ≥1, i = 1,2, ..., k, thì gcd (a, b) = p^min₁ ^{α1,β1}.p^min₂ ^{α2,β2}...p^min_k ^{αk,βk}.

Khái niệm ước số chung lớn nhất được mở rộng tự nhiên cho trường hợp có hơn hai số theo cách như sau

gcd (a1, a₂, ..., a_n−1, a_n) = gcd (gcd (a1, a₂, ..., a_n−1), a_n).

Định lí 1.3 (Bachet - Bezout). Với hai số nguyên dương a và b, luôn tồn tại các số nguyên x và y sao cho ax+ by = gcd (a, b).

Định lí 1.4. Với các số nguyên a, b ta có a², b²

= (a, b)².

Chứng minh. Trước hết ta chứng minh bổ đề: Cho các số nguyên a, b, c khác 0. Khi đó ta có

(a, bc) = (a,(a, b)c).

Ta có (a,(a, b)c) | ((a, b)c) | bc. Do đó (a,(a, b)c) là ước của a và bc, suy ra (a,(a, b)c) | (a, bc).

Mặt khác, (a, bc) là ước của a và bc nên nó là ước của ac và bc. Vì vậy (a, bc) | (ac, bc) = c(a, b). Ta có (a, bc) là ước của a và c(a, b) nên (a, bc) | (a,(a, b)c).

Vậy (a, bc) = (a,(a, b)c).

Giả sử m, n là hai số nguyên tố cùng nhau, tức là (m, n) = 1. Áp dụng bổ đề vừa chứng minh ta có

m², n²

= m², m², n n

= m²,(n,(m, n)m)n . Vì (m, n) = 1 nên m²,(n,(m, n)m)n

= m², n

. Lại áp dụng bổ đề ta có

m², n

= (n,(m, n)m) = 1.

Vì vậy (m, n) = 1 suy ra m², n²

= 1.

Ta có theo tính chất 1.2. (i) a

(a, b), b (a, b)

= 1

suy ra

a²

(a, b)², b² (a, b)²

= 1.

Từ đó theo tính chất 1.2. (ii) ta có a², b²

= (a, b)².

Ví dụ 1.5. Cho hai số nguyên a, b nguyên tố cùng nhau. Chứng minh rằng

a+ b, a² −ab+b²

= 1 hoặc 3.

Lời giải. Giả sử d = a+b, a² −ab+b²

. Ta có d | (a+b)² −a² +ab−b² = 3ab.

Do đó d | 3b(a+b)−3ab = 3b². Tương tự d | 3a². Do đó d | 3a²,3b²

= 3 a², b²

= 3 (a, b)² = 3.

Từ đó ta có điều phải chứng minh.

Ví dụ 1.6 (1997 Russian Mathematical Olympiad). Tìm tất cả các bộ ba số tự nhiên m, n, l thỏa mãn đồng thời các điều kiện sau

m+n = (m, n)², m+l = (m, l)², n+l = (n, l)².

Lời giải. Đặt d = gcd (m, n, l). Khi đó ta có m = dm₁, n = dn₁, l = dl₁ với gcd (m₁, n₁, l₁) = 1.

Đặt d_mn = gcd (m1, n₁). Theo giả thiết ta có d(m1 +n₁) = d²d²_mn. Suy ra m₁ +n₁ = dd²_mn. Tương tự như vậy với d_nl và d_lm ta có

2 (m1 +n₁ + l₁) = d d²_mn +d²_nl +d²_lm . Ta có d

gcd (d,2) là ước của m₁ +n₁+l₁ và cũng là ước của m₁ +n₁ nên d

gcd (d,2) là ước của l₁. Tương tự ta có nó cũng là ước của m₁ và n₁. Vì gcd (m1, n₁, l₁) = 1 nên d

gcd (d,2) = 1, và do đó d ≤2.

Mặt khác d_mn, d_nl, d_lm đôi một nguyên tố cùng nhau, suy ra l₁ = l₂d_lmd_ln, m₁ = m₂d_lmd_mn, n₁ = n₂d_nmd_nl

và ta có

m₂d_lm +n₂d_ln = dd_mn.

Không làm mất tổng quát ta giả sử d_mn = min{d_mn, d_lm, d_ln} ta có 2dmn ≥ dd_mn = m₂d_lm+n₂d_ln ≥ d_lm+ d_ln ≥ 2dmn.

Từ bất đẳng thức trên suy ra d = 2, m₂ = n₂ = 1 và d_mn = d_lm = d_ln mà các số này nguyên tố cùng nhau nên chúng bằng 1. Từ đó suy ra m₁ = n₁ = 1 và từ l₁ +m₁ = dd²_lm có l₁ = 1.

Vậy m = n= l = 2.

Ví dụ 1.7. Cho dãy số Fibonacci F₁ = F₂ = 1, F_n+2 = F_n+1 +F_n, với n≥ 1. Chứng minh rằng

(i) gcd (F_n+1, F_n) = 1,

(ii) Nếu s, t là các số nguyên s ≥1, t ≥ 0 thì F_s+t = F_s−1F_t +F_sF_t+1, (iii) Nếu n| m thì F_n | F_m,

(iv) gcd (Fm, F_n) = F_gcd(m,n).

Lời giải. (i) Đặt d = (Fn, F_n+1). Ta có d | F_n và d | F_n+1 nên d | F_n+1−F_n = F_n−1. Do đó d | F_n −F_n−1 = F_n−2. Tiếp tục quá trình như vậy ta suy ra d | F₁ = 1. Vì vậy ta có d = 1.

(ii) Ta cố định t và chứng minh quy nạp theo s.

Với s = 1 ta có F_t+1 = F₀F_t +F₁F_t+1 là hiển nhiên.

Giả sử s > 1 và F_s−k+t = F_s−k−1F_t + F_s−kF_t+1 với mọi k thỏa mãn 1≤ k ≤s−1.

Khi đó ta có

F_s+t = F_s+t−1 + F_s+t−2

= F_s−1+t+ F_s−2+t

= F_s−2F_t +F_s−1F_t+1+ F_s−3F_t+ F_s−2F_t+1

= F_t(Fs−2 +F_s−3) + F_t+1(Fs−1 +F_s−2)

= F_tF_s−1 +F_t+1F_s

Đến đây ta kết thúc chứng minh.

(iii) Cố định n. Ta chứng minh quy nạp theo k.

Nếu k = 1 thì rõ ràng F_n | F_n.

Giả sử F_n | F_kn. Ta đi chứng minh F_n | F_(k+1)n. Thật vậy, đặt s = n, t= kn vào đẳng thức (ii) ta có

F_(k+1)n = F_n+kn = F_n−1F_kn +F_nF_kn+1. Từ đó suy ra F_n | F_(k+1)n.

(iv) Đặt d = (F_n, F_m) và a = (m, n). Ta đi chứng minh d| F_a và F_a | d.

Thật vậy, vì a | m và a | n nên F_a | F_m, F_a | F_n suy ra F_a | d.

Nếu d = 1 thì hiển nhiên d | F_a. Trong trường hợp d > 1. Theo định lí Bezout, tồn tại hai số nguyên x, y sao cho xm +yn = a. Hiển nhiên không thể xảy ra trường hợp cả x và y là nguyên âm. Vì a | m, a | n nên a ≤ m, a ≤ n. x, y cũng không thể cùng là các số nguyên dương vì nếu như vậy thì a = xm+ yn ≥ m +n, mâu thuẫn. Do đó, x và y trái dấu nhau, không mất tổng quát ta giả sử x ≤ 0, y > 0.

Ta có F_yn = F_a−xm = F_a−1F_−xm+F_aF_−xm+1.

Ta cón | ny, m | (−xm), do đóF_n |F_yn,F_m | F_−xm. Từ đó suy ra d | F_yn và d | F_−xm. Vì thế d | F_aF_−xm+1.

Dễ dàng thấy được d | F_m | F_−xm. Nếu (d, F₋xm+1) = k > 1 thì k | F_−xm+1 và k | F_−xm. Mà hai số Fibonacci liên tiếp nguyên tố cùng nhau.

Ta có mâu thuẫn.

Từ đó (d, F₋xm+1) = 1, suy ra d | F_a. Đến đây ta hoàn thành chứng minh.

Ví dụ 1.8. Chứng minh rằng không tồn tại số Fibonacci lẻ nào chia hết cho 17.

Lời giải. Đặt d = (17, Fn), hiển nhiên d là số nguyên dương lẻ. Ta có (17, Fn) = (34, Fn) = (F9, F_n) = F_(9,n) = F₁, F₃ hoặc F₉. Điều đó có nghĩa d = 1,2 hoặc 34. Vì d lẻ nên ta có d = 1. Từ đó ta có điều phải chứng minh.

Ví dụ 1.9. Xét các số Fermat f_n = 2²ⁿ + 1. Chứng minh rằng với các số nguyên dương m, n, m > n ta có (fm, f_n) = 1.

Lời giải. Ta có với mọi số nguyên dương m f_m −2 = 2^2m−1

= 2^2n−1.2 −1

= (f_m−1 −1)² −1

= f_m²₋₁ −2fm−1

= f_m−1(fm−1 −2)

= f_m−1f_m−2(f_m−2 −2)

= · · ·

= f_m−1f_m−2· · ·f₁f₀.

Giả sử d = (fm, f_n) thì d | f_n | f_m−2. Do đó d| [fm−(fm −2)] = 2.

Rõ ràng d là số nguyên dương lẻ. Vì vậy f_m và f_n nguyên tố cùng nhau.

Ví dụ 1.10. Chof (x) = x³−x+1. Kí hiệua_n(x) =f (f (...(f (x))...)), nlần f. Chứng minh rằng các số trong dãy m, a₁(m), a₂(m), ... đôi một nguyên tố cùng nhau với mọi số tự nhiên m > 1.

Lời giải. Ta có f (x)−1 = x³ −x = (x−1)x(x+ 1). Đặt a_i = a_i(m).

Khi đó ta có

a_n+k −1 = (a_n+k−1 −1)a_n+k−1(a_n+k−1 + 1)

= (an+k−2 −1)a_n+k−2(an+k−2 + 1)a_n+k−1(an+k−1+ 1)

= · · ·

= (an −1)a_na_n+1· · ·a_n−k+1(an + 1) (an+1 + 1)· · ·(an+k−1 + 1). Do đó với các số tự nhiên i, j và i > j > 1 ta có a_j | (ai−1). Giả sử d = (ai, a_j) thì d | [ai −(ai −1)] = 1. Do đó d = 1. Vậy các số trong dãy m, a₁(m), a₂(m), ... đôi một nguyên tố cùng nhau với mọi số tự nhiên m > 1.

Ví dụ 1.11. Cho f (x) là một đa thức với các hệ số nguyên. Kí hiệu a₀ = 0,a_n = f (an−1)với mọin≥ 1. Chứng minh rằng(am, a_n) =|a_(m,n)|. Khi f (x) = P⁹

i=2

xⁱ+ 2, hãy tìm (a2016, a₂₀₁₄).

Lời giải. Đẳng thức

(am, a_n) = |a_(m,n)| (1.1)

hiển nhiên đúng khi m = 0 hoặc n= 0. Bây giờ ta xét m, n > 0.

Để chứng minh đẳng thức (1.1) trước hết ta chứng minh tính chất

a_nq...a_n (1.2)

đúng với mọi n, q ∈ N^∗.

Chứng minh tính chất (1.2) bằng quy nạp theo q.

Hiển nhiên (1.2) đúng khi q = 1.

Giả sử (1.2) đúng với q −1 tức là ta có a_n(q−1)...an. Ta cần chứng minh a_nq...an.

Với mỗi số nguyên dương k ta đặt f_k(x) =f (f (...(f (x))...)), k lần f. Ta có

a_nq −a_n = f_n a_n(q−1)

−f_n(0)...a_n(q−1). Kết hợp với giả thiết quy nạp, ta có (1.2) đúng với q.

Bây giờ để chứng minh (1.1), tương tự như thuật toán Euclid, ta chỉ ra rằng, nếu m = nq +r thì

(am, a_n) = (an, a_r) (1.3) Thật vậy ta có

a_m−a_r = f_r(anq)−f_r(0)...anq. Kết hợp với tính chất (1.2) ta có

a_m −a_r...an

Từ đó ta có đẳng thức (1.3) đúng.

Khi f (x) = P⁹

i=2

xⁱ+ 2 ta có

(a2016, a₂₀₁₄) =a₂ = 1024.

Ví dụ 1.12. Cho n là một số tự nhiên. Tìm ước chung lớn nhất của 2n

1

, 2n

3

, ...,

2n 2n−1

.

Lời giải. Ta có

n

X

k=1

2n 2k−1

= 2²ⁿ⁻¹,

suy ra ước chung lớn nhất cần tìm phải có dạng 2^a. Ta giả sử n = 2^lm với m là số tự nhiên lẻ. Mặt khác, ước chung lớn nhất của các số trên là ước của

2n 1

= 2n nên nó nhỏ hơn hoặc bằng 2^l+1. Ta đi chứng minh 2^l+1 là ước số chung lớn nhất cần tìm. Ta có

2^l+1m 2k −1

= 2^l+1m 2k −1

2^l+1m−1 2k −2

.

Nhưng 2k −1∤ 2^l+1 với k > 1 nên 2^l+1 |

2^l+1m 2k −1

. Từ đó ước chung lớn nhất của các số đã cho bằng 2^l+1.

2 Bội chung nhỏ nhất

Định nghĩa 2.1. Cho hai số nguyên a và b khác 0. Số nguyên dương k được gọi là bội số chung nhỏ nhất của a và b nếu:

(i) a | k, b | k (k là bội số chung của a và b), (ii) Nếu a | t và b | t thì k | t.

Kí hiệu bội số chung nhỏ nhất của a và b là lcm (a, b) hoặc [a, b].

Tính chất 2.2. Sau đây là một số tính chất của bội số chung nhỏ nhất (i) Nếu lcm (a, b) = k thì gcd

k a,k

b

= 1.

(ii) t.lcm (a, b) = lcm (ta, tb).

(iii) Nếu d| a, d | b và d > 0 thì lcm a

d, b d

= lcm (a, b)

d .

(iv) Nếu a = p^α₁¹.p^α₂²...p^α_k^k và b = p^β₁¹.p^β₂²...p^β_k^k với α_i, β_i ∈ N, αi +β_i ≥1, i = 1,2, ..., k, thì lcm (a, b) = p^max₁ ^{α1,β1}.p^max₂ ^{α2,β2}...p^max_k ^{αk,βk}.

Khái niệm bội số chung nhỏ nhất được mở rộng tự nhiên cho trường hợp có hơn hai số theo cách như sau

lcm (a₁, a₂, ..., a_n−1, a_n) = lcm (lcm (a₁, a₂, ..., a_n−1), a_n). Ví dụ 2.3. Chứng minh rằng

lcm (1,2, ...,200) = lcm (101,102, ...,200).

Lời giải. Ta đi chứng minh bài toán tổng quát: Với mọi số nguyên dương n ta có

lcm (1,2, ...,2n) = lcm (n+ 1, n+ 2, ...,2n).

Đặt A = lcm (1,2, ...,2n), B = lcm (n+ 1, n+ 2, ...,2n). Hiển nhiên ta có A...B.

Bây giờ ta sẽ chứng minh B...A. Ta đi chứng minh B...k với mọi k = 1,2, ...,2n.

Nếu k ∈ {n+ 1, n+ 2, ...,2n} thì hiển nhiên B...k.

Nếu k ∈ {1,2, ..., n} thì trong k số nguyên dương liên tiếp n + 1, n+ 2, ..., n+k có một số chia hết cho k. Giả sử đó là a. Ta có

n+ 1 ≤a ≤ n+k ≤ 2n, do đó B...k.

Tóm lại, với mọi k ∈ {1,2, ...,2n} ta có B...k. Vì vậy B...A.

Vậy A = B.

Ví dụ 2.4. Hỏi có bao nhiêu bộ ba số nguyên dương (a, b, c) thỏa mãn lcm (a, b) = 1000, lcm (b, c) = 2000, lcm (c, a) = 2000.

Lời giải. Ta thấy cả hai số 1000 và 2000 đều có dạng 2^m5ⁿ nên các số a, b, c đều phải có dạng này. Đặt a = 2^m15ⁿ¹, b = 2^m25ⁿ², c = 2^m35ⁿ³, trong đó m_i, n_i là các số nguyên không âm với i = 1,2,3.

Từ giả thiết ta có

max{m₁, m₂} = 3, max{m₂, m₃}= 4, max{m₃, m₁} = 4 (2.1) và

max{n₁, n₂}= 3, max{n₂, n₃} = 3, max{n₃, n₁} = 3. (2.2)

Từ (2.1) ta có m₃ = 4, hai số m₁, m₂ có một số bằng 3 và một số nhận một trong các giá trị 0,1,2,3. Có 7 bộ (m₁, m₂, m₃) thỏa mãn đó là (0,3,4), (1,3,4), (2,3,4), (3,0,4), (3,1,4), (3,2,4) và (3,3,4).

Từ (2.2) ta có hai trong ba số n₁, n₂, n₃ bằng 3 và số còn lại nhận một trong các giá trị 0,1,2,3. Ta có10 bộ(n1, n₂, n₃) thỏa mãn đó là(3,3,0), (3,3,1), (3,3,2), (3,0,3), (3,1,3), (3,2,3), (0,3,3), (1,3,3), (2,3,3) và (3,3,3).

Như vậy ta có tất cả 7.10 = 70 bộ số thỏa mãn đề bài.

Ví dụ 2.5 (Putnam 1980). Hỏi có bao nhiêu bộ 4số (a, b, c, d)thỏa mãn 3^r7^s = [a, b, c] = [b, c, d] = [c, d, a] = [d, a, b].

Lời giải.Vì sự phân tích thành các nhân tử nguyên tố của một số nguyên là duy nhất nên mỗi số a, b, c, d đều phải có dạng 3^mi7ⁿⁱ với 0≤ m_i ≤ r, 0≤ n_i ≤s, i = 1,2,3,4.

Hơn nữa, m_i bằng r đối với ít nhất hai số trong 4 số m_i. Tương tự n_i bằngs đối với ít nhất hai trong4 số n_i. Ta có

4 2

r² = 6r² cách chọn hai trong bốn số m_i bằng r và hai số mũ m_i còn lại nhận các giá trị trong tập {0,1, ..., r−1}, có

4 3

r = 4r cách chọn ba trong bốn số m_i bằng r và một số m_i còn lại nhận giá trị trong tập {0,1, ..., r−1}, có 4

4

= 1 cách chọn cả bốn số m_i bằng r. Như vậy ta có 1 + 4r + 6r² cách chọn ít nhất hai trong bốn số a, b, c, d có lũy thừa của 3 bằng r.

Tương tự như vậy ta có 1 + 4s+ 6s² cách chọn ít nhất hai trong bốn số a, b, c, d có lũy thừa của 7 bằng s. Như vậy ta có

1 + 4r + 6r²

1 + 4s+ 6s² bộ bốn số thỏa mãn đề bài.

Ví dụ 2.6 (AMM E2686). Cho số nguyên dương n. Chứng minh rằng (n+ 1) lcm

n 0

,

n 1

, ..., n

n

= lcm (1,2, ..., n+ 1). (2.3)

Lời giải. Trước hết ta nhắc lại định lí: Giả sử n là số nguyên dương.

Khi đó lũy thừa của số nguyên tố p xuất hiện trong phân tích ra thừa số nguyên tố của n! là

n p

+

n p²

+

n p³

+· · ·

Giả sử p là một số nguyên tố, p ≤ n+ 1 và α (tương ứng β) là số mũ lớn nhất của p ở vế trái (tương ứng vế phải) của (2.3). Chọn số r thỏa mãn p^r ≤ n+ 1 < p^r+1. Rõ ràng β = r.

Ta cần chứng minh rằng, nếu p^r ≤ m < p^r+1 thì p^r+1 ∤ m

k

với 0≤ k ≤m (*).

Thật vậy, lũy thừa của p xuất hiện trong sự phân tích ra thừa số nguyên tố của

m k

là

γ =

r

X

s=1

m p^s

− k

p^s

−

m−k p^s

.

Mỗi hạng tử trong tổng trên bằng 0hoặc 1, ta có γ ≤ r, do đó (*) đúng.

Với 0 ≤ k ≤ n, đặt a_k = (n+ 1)

n k

= (n−k+ 1)

n+ 1 k

= (k+ 1)

n+ 1 k + 1

.

Từ (*) ta có p^r+1 không là ước của các số nguyên n k

,

n+ 1 k

, n+ 1

k + 1

. Vì vậy p^r+1 là ước của a_k khi và chỉ khi p là ước của cả ba số n+ 1, n−k + 1, k + 1. Từ đó suy ra

p | [(n+ 1)−(n−k+ 1)−(k + 1)] = −1, mâu thuẫn. Vì vậy p^r+1 ∤ a_k.

Mặt khác với k = p^r −1 ta có k ≤ n nên a_k = (k+ 1)

n+ 1 k+ 1

chia hết cho p^r.

Vậy β = r = α. Từ đó suy ra điều phải chứng minh.

Ví dụ 2.7 (APMO 1998). Tìm số nguyên n lớn nhất thỏa mãn n chia hết cho tất cả các số nguyên nhỏ hơn √³ n.

Lời giải. Ta thấy 7 < √³

420 < 8 và 420 = lcm{1,2,3,4,5,6,7}. Ta đi chứng minh 420 là số cần tìm.

Giả sử n > 420 là số nguyên thỏa mãn chia hết cho tất cả các số nguyên nhỏ hơn√³ n. Ta có√³

n > 7nênnchia hết cho420 = lcm{1,2,3,4,5,6,7}, do đón≥ 840và√³

n > 9. Do đónchia hết2520 = lcm{1,2,3,4,5,6,7,8,9} và ta lại có √³

n > 13. Giả sử m là số nguyên dương lớn nhất nhỏ hơn

√3 n. Khi đó ta có m < √³

n ≤ m + 1. Ta có m ≥ 13 và n chia hết cho lcm{1,2,3,4,5,6,7}. Mặt khác, ta lại có

lcm (m−3, m−2, m−1, m) ≥ m(m−1) (m−2) (m−3) 6

vì chỉ có 2 và 3 là ước chung của bốn số trên.

Từ đó ta có

m(m−1) (m −2) (m−3)

6 ≤ n≤ (m+ 1)³. Suy ra

m ≤ 6

1 + 2

m −1 1 + 3

m−2 1 + 4

m−3

.

Vế trái của bất đẳng thức trên là hàm đơn điệu tăng của biến m, còn vế phải là hàm đơn điệu giảm của biến m. Với m = 13 ta có

13.12.11.10 = 17160 > 6.14³

do vậy bất đẳng thức trên không đúng với mọi m ≥ 13.

Vậy không có số m > 420 nào thỏa mãn điều kiện đề bài.

Ví dụ 2.8 (1951 Russian Mathematics Olympiad). Cho các số nguyên dươnga₁, a₂, ..., a_n nhỏ hơn 1000và lcm (a_i, a_j) > 1000với mọi i, j, i 6= j.

Chứng minh rằng

n

X

i=1

1 a_i < 2.

Lời giải. Nếu 1000

m + 1 < a ≤ 1000

m thì có m bội số của a là a,2a, ..., ma không vượt quá1000. Giả sửk₁ là số cáca_inằm trong khoảng

1000

2 ,1000

, k₂ là số các a_i nằm trong khoảng

1000

3 ,1000 2

,...Như vậy ta có k₁ + 2k2 + 3k3 + · · · các số nguyên, không lớn hơn 1000, là bội của ít nhất một số a_i nào đó. Vì các bội này là phân biệt (vì lcm (ai, a_j) > 1000) nên ta có

k₁ + 2k₂ + 3k₃ +· · · < 1000

⇒ 2k₁ + 3k₂ + 4k₃ +· · · < (k₁ + 2k₂ + 3k₃ +· · ·) + (k₁ +k₂ + k₃ +· · ·)

< 1000 +n < 2000.

Do đó,

n

X

i=1

1

a_i ≤ k₁ 2

1000 +k₂ 3

1000 +k₃ 4

1000 +· · · = 2k₁ + 3k₂ + 4k₃ +· · · 1000 < 2.

Ví dụ 2.9. Cho 0< a₁ < a₂ < ... < a_n ≤2n là các số nguyên thỏa mãn bội số chung nhỏ nhất của hai số bất kì trong chúng đều lớn hơn 2n.

Chứng minh rằng

a₁ >

2n 3

. ( ⌊α⌋ là kí hiệu phần nguyên của số thực α)

Lời giải. Rõ ràng, trong các số trên không tồn tại cặp số nào mà số này chia hết cho số kia (vì nếu trái lại thì bội chung nhỏ nhất của chúng nhỏ hơn hoặc bằng 2n). Ta viết a_k = 2^tkA_k với A_k là số lẻ. Ta thấy các giá trị A_k là phân biệt. Mặt khác từ 1 đến 2n ta có n số lẻ phân biệt.

Do đó các giá trị A_k là các số lẻ từ 1 đến 2n theo một thứ tự nào đó.

Ta xét a₁ = 2^t1A₁. Nếu a₁ ≤

2n 3

thì 3a1 = 2^t13A1 ≤ 2n tức là 3A1 < 2n. Do đó 3A1 là một số lẻ nhỏ hơn 2n, tức là 3A1 = A_j nào đó. Như vậy a_j = 2^tj3A1. Khi đó [a1, a_j] = 2^t13A1 = 3a1 ≤ 2n hoặc [a1, a_j] = 2^tj3A1 = a_j ≤ 2n, mâu thuẫn với giả thiết. Vậy điều giả sử là sai, tức là ta có a₁ >

2n 3

.

Ví dụ 2.10. Cho a₀ < a₁ < a₂ < · · · < a_n là các số nguyên dương.

Chứng minh rằng 1

lcm (a0, a₁) + 1

lcm (a1, a₂) + · · ·+ 1

lcm (an−1, a_n) ≤ 1− 1

2ⁿ. (2.4) Lời giải. Ta chứng minh quy nạp theo n.

Vớin = 1, ta có lcm (a₀,a₁) ≥ lcm (1,2) = 2. Do đó 1

lcm (a0,a1) ≤ 1−1 2. Giả sử (2.4) đúng với n = k, tức là nếu a₀ < a₁ < a₂ < · · · < a_k thì ta

có 1

lcm (a₀, a₁) + 1

lcm (a₁, a₂) +· · ·+ 1

lcm (ak−1, a_k) ≤ 1− 1 2^k.

Ta đi chứng minh (2.4) cũng đúng với n = k+ 1. Giả sử a₀ < a₁ < a₂ <

· · · < a_k < a_k+1 là các số nguyên dương. Ta xét hai trường hợp.

Trường hợp 1. a_k+1 ≥ 2^k+1. Ta có lcm (ak,ak+1) ≥ ak+1 ≥ 2^k+1. Theo giả thiết quy nạp ta có

1

lcm (a0, a₁) + 1

lcm (a1, a₂) +· · ·+ 1

lcm (ak−1, a_k) + 1

lcm (ak, a_k+1)

≤1− 1

2^k + 1

2^k+1 = 1− 1 2^k+1,

Trường hợp 2. a_k+1 < 2^k+1. Khi đó ta có 1

lcm (ai−1, a_i) = gcd (ai−1, a_i)

a_i−1a_i ≤ a_i −a_i−1

a_i−1a_i = 1

a_i−1 − 1 a_i. Cộng vế các bất đẳng thức như trên với i từ 1 đến k+ 1 ta được

1

lcm (a₀, a₁) + 1

lcm (a₁, a₂) +· · ·+ 1

lcm (ak−1, a_k) + 1

lcm (ak, a_k+1)

≤ 1

a₀ − 1

a_k+1 ≤ 1− 1 2^k+1.

Theo phương pháp quy nạp ta được điều phải chứng minh.

Ví dụ 2.11. Cho các số nguyên dương không vượt quá số nguyên dương m không đổi cho trước. Chứng minh rằng nếu mọi số nguyên dương nhỏ hơn hoặc bằng m không chia hết cho cặp hai số nào trong các số được cho ở trên, thì tổng nghịch đảo của các số đã cho nhỏ hơn 3

2.

Lời giải. Theo giả thiết mọi số nguyên dương nhỏ hơn hoặc bằng m không chia hết cho cặp hai số nào trong các số được cho ở trên nên bội chung nhỏ nhất của hai số bất kì trong các số được cho lớn hơn m. Giả sử cho n số, kí hiệu x₁, x₂, ..., x_n. Với mỗi i, ta có

m x_i

bội của x_i trong các số 1,2, ..., m, ( ⌊α⌋ là kí hiệu phần nguyên của số thực α). Không có số nào trong chúng là bội của x_j với j 6= i vì bội chung nhỏ nhất của x_i và x_j lớn hơn m. Như vậy ta có

m x₁

+

m x₂

+· · ·+ m

x_n

phần tử đôi một khác nhau của tập hợp {1,2, ..., m} chia hết cho một trong các số x₁, x₂, ..., x_n. Trong các phần tử này không có phần tử nào bằng 1 (trừ trường hợp n = 1, khi đó điều phải chứng minh là hiển nhiên). Do đó

m x₁

+

m x₂

+ · · ·+ m

x_n

≤ m−1.

Với mọi i ta lại có m x_i <

m x_i

+ 1, suy ra

m 1

x₁ + 1

x₂ +· · ·+ 1 x_n

< m+n−1.

Ta còn phải chứng minh n≤ m+ 1

2 , khi đó ta suy ra được 1

x₁ + 1

x₂ +...+ 1 xn

< 1 + n−1 m < 3

2.

Thật vậy, ta có các ước số lẻ lớn nhất của các số x₁, x₂, ..., x_n là phân biệt vì nếu trái lại có hai số có cùng ước số lẻ lớn nhất thì một số trong chúng là bội của số còn lại, trái với giả thiết. Suy ra n không vượt quá số các số lẻ trong các số 1,2, ..., m. Do đó n≤ m+ 1

2 .

3 Liên hệ giữa ước chung lớn nhất và bội chung nhỏ nhất

Định lí 3.1. Cho m, n là hai số nguyên dương. Khi đó ta có

mn = gcd (m, n).lcm (m, n).

Chứng minh. Giả sử m = p^α₁¹.p^α₂²...p^α_k^k và n = p^β₁¹.p^β₂²...p^β_k^k với α_i, β_i ∈ N, αi +β_i ≥ 1, i = 1,2, ..., k. Khi đó ta có

gcd (m, n) =p^min₁ ^{α1,β1}.p^min₂ ^{α2,β2}...p^min_k ^{αk,βk}. lcm (m, n) =p^max₁ ^{α1,β1}.p^max₂ ^{α2,β2}...p^max_k ^{αk,βk}. Ta có

gcd (m, n).lcm (m, n) = p^min₁ ^{{α1,β1}+max{α1,β1}}...p^min_k ^{{αk,βk}+max{αk,βk}}

= p^α₁^1+β1...p^α_k^k+βk

= mn.

Nhận xét 3.2. Cho các số nguyên dương a₁, a₂, ..., a_n, n ≥ 3 thì đẳng thức

a₁a₂...a_n = gcd (a1, a₂, ..., a_n).lcm (a1, a₂, ..., a_n) nói chung là không đúng. Chẳng hạn

gcd (3,3,3).lcm (3,3,3) = 3.3 = 9 < 3.3.3 = 27. Ví dụ 3.3. Cho m, n là các số nguyên dương thỏa mãn

lcm (m, n) + gcd (m, n) = m+n.

Chứng minh rằng một trong hai số đó chia hết cho số còn lại.

Lời giải. Cách 1. Đặt d = gcd (m, n). Khi đó ta có m = ad, n = bd với gcd (a, b) = 1 và

lcm (m, n) = mn

gcd (m, n) = abd.

Theo bài ra ta có phương trình abd+d = ad+bd hay ab−a−b+ 1 = 0.

Từ đó ta có (a−1) (b−1) = 0, suy ra a = 1 hoặc b = 1. Như vậy ta có m = d, n = bd = bm hoặc n = d, m = an.

Cách 2.Ta cólcm (m, n).gcd (m, n) =m.n, suy ralcm (m, n)vàgcd (m, n) là các nghiệm của phương trình

x² −(m+n)x+mn = 0.

Dễ thấy hai nghiệm của phương trình là m và n. Do đó {lcm (m, n),gcd (m, n)}= {m, n}. Từ đó ta có điều phải chứng minh.

Ví dụ 3.4 (St. Petersburg 2001). Cho m, n là các số nguyên dương, m > n. Chứng minh rằng

lcm (m, n) + lcm (m+ 1, n+ 1)> 2mn

√m−n. Lời giải. Đặt m = n+k. Khi đó ta có

lcm (m, n) + lcm (m+ 1, n+ 1) = mn

gcd (m, n) + (m+ 1) (n+ 1) gcd (m+ 1, n+ 1)

> mn

gcd (n+k, n) + mn

gcd (m + 1, n+ 1)

= mn

gcd (k, n) + mn

gcd (n+k + 1, n+ 1)

= mn

gcd (k, n) + mn

gcd (k, n+ 1).

Dễ thấygcd (k, n) và gcd (k+ 1, n) không thể có chung ước số nguyên tố nào vì nếu p là một ước số nguyên tố chung của chúng thì p | n và p | n+ 1, điều này là vô lí. Mặt khác gcd (k, n) | k và gcd (k, n+ 1) | k nên ta có gcd (k, n).gcd (k+ 1, n) ≤ k.

Theo bất đẳng thức giữa trung bình cộng và trung bình nhân (AM - GM) ta có

lcm (m, n) + lcm (m+ 1, n+ 1) > mn

gcd (k, n) + mn gcd (k, n+ 1)

≥ 2mn

r 1

gcd (k, n).gcd (k, n+ 1) ≥ 2mn r1

k = 2mn

√m−n.

Ví dụ 3.5. Cho a, b, c là các số nguyên khác không. Chứng minh rằng (i) [a,(b, c)] = ([a, b],[a, c]),

(ii) (a,[b, c]) = [(a, b),(a, c)]. Lời giải. (i) Ta có

(a, b, c) b

(a, b), c (a, c)

=

b

(a, b) (a, b, c), c

(a, c)(a, b, c)

=

b

(a, b) ((a, b),(b, c)), c

(a, c) ((a, c),(b, c))

=

b, b(b, c) (a, b)

,

c,c(b, c) (a, c)

=

b, b(b, c) (a, b)

, c, c(b, c) (a, c)

=

b, b(b, c) (a, b) , c

,c(b, c) (a, c)

=

(b, c),b(b, c) (a, b)

,c(b, c) (a, c)

=

(b, c),b(b, c)

(a, b) , c(b, c) (a, c)

= (b, c)

1, b

(a, b), c (a, c)

= (b, c). Từ đó suy ra

(b, c) (a, b, c) =

b

(a, b), c (a, c)

. Ta có

(a, b, c) = (a,(b, c)) = a.(b, c) [a,(b, c)]

và b

(a, b) = [a, b]

a ; c

(a, c) = [a, c]

a nên ta được

[a,(b, c)]

a =

[a, b]

a ,[a, c]

a

= 1

a([a, b],[a, c]).

Vậy [a,(b, c)] = ([a, b],[a, c]). (ii) Từ (i) ta suy ra

a.(b, c)

(a, b, c) = [a, b].[a, c]

[a, b, c]

⇔ abc

(a, b, c) [b, c] = a²bc

(a, b) (a, c) [a, b, c]

⇔ 1

(a, b, c) [b, c] = a

(a, b) (a, c) [a, b, c]

⇔ a[b, c] (a, b, c) = (a, b) (a, c) [a, b, c]

⇔ a[b, c]

[a, b, c] = (a, b) (a, c) (a, b, c)

⇔ (a,[b, c]) = [(a, b),(a, c)]

Ví dụ 3.6. Cho ba số nguyên dương m, n và p. Chứng minh rằng (i) [m, n, p] = mnp(m, n, p)

(m, n) (n, p) (p, m).

(ii) [m, n, p] = (m, n, p) [m, n] [n, p] [p, m]

mnp .

Lời giải.

(i) Cách 1. Suy ra từ ví dụ 3.5 và định lí 3.1.

Cách 2. Đặtd = (m, n, p). Khi đó m = dx, n= dy,p = dz với(x, y, z) = 1.

Ta có

[m, n, p] = [dx, dy, dz] = d[x, y, z], mnp(m, n, p)

(m, n) (n, p) (p, m) = dx.dy.dz.d

d(x, y).d(y, z).d(z, x) = dxyz

(x, y).(y, z).(z, x). Do vậy. điều phải chứng minh tương đương với

[x, y, z] = xyz

(x, y).(y, z).(z, x) trong đó (x, y, z) = 1.

[x, y, z] = [[x, y], z] = [x, y].z ([x, y], z) =

xy (x, y).z

([x, y], z) = xyz

(x, y).([x, y], z). (3.1)

Từ đó đẳng thức (3.1) tương đương với

([x, y], z) = (x, z).(y, z), (3.2) với điều kiện (x, y, z) = 1.

Đặt q = (x, y). Ta có x = qx₁, y = qy₁, trong đó (x1, y₁) = 1. Hơn nữa do (x, y, z) = 1 nên ta có (q, z) = 1. Do vậy đẳng thức (3.2) tương đương (x1y₁, z) = (x1, z).(y1, z). (3.3) Thật vậy, giả sử k = (x₁y₁, z). Khi đó k |(x₁y₁) và k | z mà (x₁, y₁) = 1 nên k | x₁ hoặc k | y₁. Suy ra k | (x₁, z) hoặc k | (y₁, z). Do đó k | (x₁, z).(y₁, z).

Ngược lại nếu l = (x₁, z) thì l | x₁ và l |z, suy ral | x₁y₁ nên l | (x₁y₁, z).

Tương tự (x₁, z) | (x₁y₁, z). Do đó (3.3) được chứng minh. Từ đó ta có (i) được chứng minh hoàn toàn.

(ii) Suy ra từ (i) bằng cách sử dụng định lí 3.1.

Ví dụ 3.7 (USAMO 1972). Cho các số nguyên a, b và c. Chứng minh rằng

[a, b, c]²

[a, b] [b, c] [c, a] = (a, b, c)² (a, b) (b, c) (c, a). Lời giải.

Cách 1. Áp dụng Ví dụ 3.6 ta có [a, b, c] = abc(a, b, c)

(a, b) (b, c) (c, a) = (a, b, c) [a, b] [b, c] [c, a]

abc .

Do đó

[a, b, c]² = abc(a, b, c)

(a, b) (b, c) (c, a).(a, b, c) [a, b] [b, c] [c, a]

abc = (a, b, c)²[a, b] [b, c] [c, a]

(a, b) (b, c) (c, a) . Từ đó ta có điều phải chứng minh.

Cách 2. Giả sử a = p^α₁¹· · ·p^α_nⁿ, b = p^β₁¹· · ·p^β_nⁿ, c = p^γ₁¹· · ·p^γ_nⁿ, ở đó p₁, p₂, ..., p_nlà các số nguyên tố phân biệt, vàα₁, ..., α_n,β₁, ..., β_n,γ₁, ..., γ_n

là các số nguyên không âm. Khi đó ta có

[a, b, c]²

[a, b] [b, c] [c, a] =

n

Q

i=1

p^{2 max}_i ^{{αi,βi,γi}}

n

Q

i=1

p^max_i ^{αi,βi}

n

Q

i=1

p^max_i ^{βi,γi}

n

Q

i=1

p^max_i ^{γi,αi}

=

n

Y

i=1

p^{2 max}_i ^{{αi,βi,γi}−max{αi,βi}−max{βi,γi}−max{γi,αi}}

và

(a, b, c)²

(a, b) (b, c) (c, a) =

n

Q

i=1

p^{2 min}_i ^{{αi,βi,γi}}

n

Q

i=1

p^min_i ^{αi,βi}

n

Q

i=1

p^min_i ^{βi,γi}

n

Q

i=1

p^min_i ^{γi,αi}

=

n

Y

i=1

p^{2 min}_i ^{{αi,βi,γi}−min{αi,βi}−min{βi,γi}−min{γi,αi}}

Ta cần chứng minh với các số nguyên không âm α, β, γ bất kì 2 max{α, β, γ} −max{α, β} −max{β, γ} −max{γ, α}

= 2 min{α, β, γ} −min{α, β} −min{β, γ} −min{γ, α}. (3.4) Thật vậy, do tính đối xứng, không mất tổng quát ta giả sử α ≤ β ≤ γ.

Khi đó ta có (3.4) tương đương với

2γ −β −γ −γ = 2α−α−β−α. (3.5) Đẳng thức (3.5) hiển nhiên đúng. Từ đó ta có điều phải chứng minh.

Chú ý: Ta thấy phương pháp này có thể dùng để chứng minh được các ví dụ 3.5, ví dụ 3.6 theo cách tương tự.

Nhận xét 3.8. Từ ví dụ trên ta có [a, b] [b, c] [c, a]

[a, b, c]² và (a, b) (b, c) (c, a) (a, b, c)² là các số nguyên bằng nhau.

Ví dụ 3.9. Cho n ≥ 2 số nguyên dương a₁, a₂, ..., a_n. Chứng minh rằng a₁a₂...a_n ≥[a1, a₂, ..., a_n] (a1, a₂, ..., a_n).

Lời giải. Đặt

A = a₁a₂...a_n (a1, a₂, ..., a_n). Với mỗi i = 1, n ta có

A = a_i.a₁...a_i−1.a_i+1...a_n (a1, a₂, ..., a_n) ...ai

Từ đó suy ra

A...[a₁, a₂, ..., a_n]. Do đó

A ≥[a1, a₂, ..., a_n].

4 Bài tập đề nghị

Bài toán 4.1. Tìm các số tự nhiêna, b thỏa mãn(a, b) = 12,[a, b] = 532.

Bài toán 4.2. Tìm hai số a, b nguyên dương thỏa mãn a²+b² = 85113, [a, b] = 1764.

Bài toán 4.3. Chứng minh rằng (a, b)ⁿ = (aⁿ, bⁿ) với mọi số tự nhiên n.

Bài toán 4.4. Cho các số nguyên a, b, c khác không. Chứng minh rằng ([a, b],[b, c],[c, a]) = [(a, b),(b, c),(c, a)].

Bài toán 4.5. Chứng minh rằng gcd

n−1 k −1

,

n k + 1

,

n+ 1 k

= gcd

n−1 k

,

n+ 1 k+ 1

,

n k−1

Bài toán 4.6 (USAMO 1993). Cho a, b là các số nguyên dương lẻ. Dãy số (fn) được xác định như sau f₁ = a, f₂ = b, với n ≥3 thì f_n là ước số lẻ lớn nhất của f_n−1+f_n−2. Chứng minh rằng f_n không đổi với n đủ lớn và xác định giá trị đó theo a và b.

Bài toán 4.7 (1997 Canadian Mathematical Olympiad). Có bao nhiêu cặp số nguyên dương (x, y) với x ≤ y thỏa mãn gcd (x, y) = 5! và lcm (x, y) = 50!.

Bài toán 4.8 (1995 Russian Mathematical Olympiad). Dãy các số tự nhiên a₁, a₂, ... thỏa mãn điều kiện gcd (ai, a_j) = gcd (i, j) với mọi i 6= j.

Chứng minh rằng a_i = i với mọi i.

Bài toán 4.9 (AIME 1985). Cho dãy số (a_n) được xác định bởi a_n = 100 +n², n = 1,2, ... Với mỗi n, đặt d_n = (a_n, a_n+1). Tìm max

n≥1 d_n. Tài liệu tham khảo

[1 ] Hà Huy Khoái, Chuyên đề bồi dưỡng học sinh giỏi toán trung học phổ thông Số học, NXB Giáo dục, 2006.

[2 ] Đặng Hùng Thắng - Nguyễn Văn Ngọc - Vũ Kim Thủy, Bài giảng số học, NXB Giáo dục Việt Nam, 2010.

[3 ] Dương Quốc Việt (chủ biên) - Đàm Văn Nhỉ, Cơ sở lí thuyết số và đa thức, NXB Đại học Sư phạm, 2012.

[4 ] Dương Quốc Việt (chủ biên), Nguyễn Đạt Đăng, Lê Văn Đính, Lê Thị Hà, Đặng Đình Hanh, Đào Ngọc Minh, Trương Thị Hồng Thanh, Phan Thị Thủy, Bài tập cơ sở lí thuyết số và đa thức, NXB Đại học Đại học Sư phạm, 2014.

[5 ] Titu Andreescu, Dorin Andrica, Zuming Feng, 104 number theory problems, Birkhauser Boston - Basel - Berlin, 2006.

[6 ] David A. Santos, Elementary Number Theory Notes C, 2004.

[7 ] Titu Andreescu, Dorin Andrica, Number Theory Structures, Ex- ample, and Problems, Birkhauser.