gcd, lcm là gì? bài toán liên quan đến gcd,lcm

GCD và LCM là hai khái niệm cơ bản và quan trọng trong lý thuyết số, có nhiều ứng dụng trong toán học và tin học.

1. GCD là gì? (Ước chung lớn nhất)

GCD (Greatest Common Divisor), hay còn gọi là ƯCLN (Ước chung lớn nhất), của hai hay nhiều số nguyên dương là số nguyên dương lớn nhất mà tất cả các số đó đều chia hết.

Ký hiệu: GCD($a,b$) hoặc ƯCLN($a,b$).

Ví dụ:

• Tìm GCD(12, 18):
  • Các ước của 12 là: 1, 2, 3, 4, 6, 12.
  • Các ước của 18 là: 1, 2, 3, 6, 9, 18.
  • Các ước chung của 12 và 18 là: 1, 2, 3, 6.
  • Ước chung lớn nhất là 6. Vậy GCD(12, 18) = 6.

Cách tìm GCD:

• Liệt kê ước: Liệt kê tất cả các ước của từng số, sau đó tìm ước chung lớn nhất. Cách này hiệu quả với số nhỏ.
• Phân tích ra thừa số nguyên tố:
  1. Phân tích mỗi số ra thừa số nguyên tố.
  2. Chọn các thừa số nguyên tố chung với số mũ nhỏ nhất.
  3. Nhân các thừa số đó lại với nhau. Ví dụ GCD(12, 18):
  • 12=22×31
  • 18=21×32
  • Thừa số nguyên tố chung là 2 và 3.
  • Chọn số mũ nhỏ nhất: 21 và 31.
  • GCD(12, 18) = 21×31=6.
• Thuật toán Euclid: Đây là thuật toán hiệu quả nhất để tìm GCD, đặc biệt với các số lớn. Thuật toán này dựa trên tính chất: GCD($a,b$) = GCD($b,a(\mathrm{mod}b)$). Lặp lại quá trình này cho đến khi số dư bằng 0, khi đó số chia chính là GCD. Ví dụ GCD(18, 12):
  • $18=1\times 12+6$
  • $12=2\times 6+0$
  • Số chia cuối cùng khác 0 là 6. Vậy GCD(18, 12) = 6.

2. LCM là gì? (Bội chung nhỏ nhất)

LCM (Least Common Multiple), hay còn gọi là BCNN (Bội chung nhỏ nhất), của hai hay nhiều số nguyên dương là số nguyên dương nhỏ nhất mà tất cả các số đó đều là ước của nó.

Ký hiệu: LCM($a,b$) hoặc BCNN($a,b$).

Ví dụ:

• Tìm LCM(12, 18):
  • Các bội của 12 là: 12, 24, 36, 48, 60, 72,...
  • Các bội của 18 là: 18, 36, 54, 72, 90,...
  • Các bội chung của 12 và 18 là: 36, 72,...
  • Bội chung nhỏ nhất là 36. Vậy LCM(12, 18) = 36.

Cách tìm LCM:

• Liệt kê bội: Liệt kê các bội của từng số cho đến khi tìm được bội chung nhỏ nhất.
• Phân tích ra thừa số nguyên tố:
  1. Phân tích mỗi số ra thừa số nguyên tố.
  2. Chọn tất cả các thừa số nguyên tố (chung và riêng) với số mũ lớn nhất.
  3. Nhân các thừa số đó lại với nhau. Ví dụ LCM(12, 18):
  • 12=2^2×3^1
  • 18=2^1×3^2
  • Thừa số nguyên tố là 2 và 3.
  • Chọn số mũ lớn nhất: 2^2 và 3^2.
  • LCM(12, 18) = 2^2×3^2=4×9=36.

Mối quan hệ giữa GCD và LCM: Đối với hai số nguyên dương $a$ và $b$, ta có công thức quan trọng sau: $GCD(a,b)\times LCM(a,b)=a\times b$

Từ công thức này, ta có thể tính LCM nếu đã biết GCD, hoặc ngược lại: LCM(a,b)=axb/GCD(a,b)​

3. Các bài toán liên quan đến GCD và LCM

GCD và LCM có rất nhiều ứng dụng trong toán học và thực tế:

a. Bài toán về phân số:

• Rút gọn phân số: Để rút gọn một phân số ba​ về dạng tối giản, ta chia cả tử và mẫu cho GCD($a,b$). Ví dụ: Rút gọn 1812​. GCD(12, 18) = 6. do 18÷6=12÷6​=3​.
• Quy đồng mẫu số: Để cộng hoặc trừ các phân số có mẫu số khác nhau, ta cần quy đồng mẫu số. Mẫu số chung nhỏ nhất chính là LCM của các mẫu số. Ví dụ: Cộng 121​+181​. LCM(12, 18) = 36. 12×3 =18×2​=36

b. Bài toán chia nhóm, chia đều:

• Chia đều vật phẩm: Có $a$ quả táo và $b$ quả cam. Muốn chia đều số táo và cam vào các rổ sao cho mỗi rổ có số táo bằng nhau và số cam bằng nhau, và số rổ là nhiều nhất. Số rổ chính là GCD($a,b$). Ví dụ: Có 24 viên bi đỏ và 30 viên bi xanh. Muốn chia đều vào các túi sao cho mỗi túi có số bi đỏ bằng nhau và số bi xanh bằng nhau. Hỏi có thể chia được nhiều nhất bao nhiêu túi? Đây là bài toán tìm GCD(24, 30). 24=2^3×3 $30=2\times 3\times 5$ GCD(24, 30) = $2\times 3=6$. Vậy có thể chia nhiều nhất 6 túi.

c. Bài toán về chu kỳ, thời gian lặp lại:

• Tìm thời điểm gặp nhau: Hai xe buýt khởi hành cùng lúc từ một bến. Xe A cứ 15 phút lại có một chuyến, xe B cứ 20 phút lại có một chuyến. Hỏi sau bao lâu thì cả hai xe lại cùng khởi hành một lần nữa? Đây là bài toán tìm LCM(15, 20). $15=3\times 5$ 20=2^2×5 LCM(15, 20) = 2^2×3×5=4×3×5=60. Vậy sau 60 phút (1 giờ) thì cả hai xe lại cùng khởi hành.
• Đèn nhấp nháy: Có ba đèn nhấp nháy: đèn thứ nhất nhấp nháy sau mỗi 3 giây, đèn thứ hai sau mỗi 4 giây, đèn thứ ba sau mỗi 5 giây. Nếu cả ba đèn cùng nhấp nháy lúc 10 giờ, thì thời điểm tiếp theo chúng cùng nhấp nháy là khi nào? Bài toán này yêu cầu tìm LCM(3, 4, 5). Vì 3, 4, 5 là các số nguyên tố cùng nhau từng đôi một, nên LCM(3, 4, 5) = $3\times 4\times 5=60$. Vậy sau 60 giây (1 phút), cả ba đèn lại cùng nhấp nháy. Thời điểm đó là 10 giờ 1 phút.

d. Trong lập trình và khoa học máy tính:

• Mã hóa và giải mã: Trong một số thuật toán mã hóa, các khái niệm liên quan đến lý thuyết số như GCD được sử dụng.
• Tối ưu hóa thuật toán: Thuật toán Euclid để tìm GCD là một trong những thuật toán cổ điển và hiệu quả nhất, được sử dụng rộng rãi trong các thư viện lập trình.

Những bài toán này cho thấy tầm quan trọng và tính ứng dụng thực tế của GCD và LCM trong nhiều lĩnh vực khác nhau.