Tính Chất ước Số Chung Lớn Nhất Và Một Vài Bài Tập ứng Dụng Số ...

Trang chủ » Tính Chất Của Ucln » Tính Chất ước Số Chung Lớn Nhất Và Một Vài Bài Tập ứng Dụng Số ...

Có thể bạn quan tâm

Nếu số nguyên chia hết cho số nguyên d thì số d được gọi là ước của số nguyên a, a được gọi là bội của d. Số nguyên dương d lớn nhất là ước của cả hai số nguyên a,b được gọi là ứơc chung lớn nhất (ƯCLN) của a và b

Ước số chung lớn nhất của 2 số nguyên a và b kí hiệu GCD(a,b) có các tính chất cần lưu ý và ghi nhớ, nhờ những tính chất thú vị này, ta có thể áp dụng để giải một số bài tập về số học và hình học.

  • Bội chung nhỏ nhất cuả và b kí hiệu là  LCM(a,b). GCD(a,b) * LCM(a,b)  = a*b.
  • GCD(a + m*b, b) = GCD(a, b) (m là số nguyên bất kì)
  • Hình học (đề các). GCD(a, b) biểu diễn số các điểm với tọa độ nguyên trên đoạn thẳng nối các điểm (0, 0) và (a, b), trừ chính điểm (0, 0).

Bổ đề 1: tham khảo tại http://acm.timus.ru/problem.aspx?space=1&num=1139

Cho hình chữ nhật có dài rộng lần lượt là a,b (a và b nguyên dương), hình chia thành nhiều ô nhỏ như hình vẽ. Tính số ô bị chiếm dụng khi vẽ một đường chéo nối hai đỉnh đối diện.

image

Q = a+b  – GCD(a,b).

Bổ đề 2. Tham khảo Đề thi Tin học Quốc gia Ireland, 1994. Tìm số chữ  số 0 ở cuối cùng của n! với n trong khoảng 1..100. Thí dụ: –  n = 7, kết quả = 1. –  n = 15, kết quả = 3.

Phân tích: n = 15

15! = 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15

Phân tích dãy này thành các số nguyên tố

= 1.2.3.(2.2).5.(2.3).7.(2.2.2).9.(2.5).11. (2.2.3).13.(2.7).(3.5)

Nhận thấy kết quả xuất hiện k số 0 ở cuối tương đương với số cặp thừa số 2 và 5 xuất hiện trong dãy số phân tích. Gọi số lượng thừa số 2 là d2 và số lượng thừa số 5 là d5 . Ta có d2 > d5  (vì cứ hai số liên tiếp trong dãy giai thừa lại có một số chẵn).

vậy số lượng số ở cuối sẽ là d2 – d5.

Share this:

  • Twitter
  • Facebook
Like Loading...

Related

Từ khóa » Tính Chất Của Ucln