Kiến thức

Phép chia lấy dư và giải thuật Euclid (Phần 1)

Phép chia lấy dư và giải thuật Euclid (Phần 1)

7 phút đọc

Tags:

algorithm

,

euclid

,

math

,

modulo

1. Chút kiến thức căn bản cần chuẩn bị

1.1) Một vài định nghĩa cơ bản về số học

  1. Khi ta nói rằng chia hết cho (, là các số nguyên) thì ta viết một cách ngắn gọn như sau: . Nghĩa là . = ( là số nguyên).
  2. Một số nguyên là số nguyên tố nếu nó chỉ chia hết cho 1 và chính nó.
  3. Một số nguyên nếu không phải là số nguyên tố thì được gọi là hợp số.

1.2) Định lý

Với a, b, c, x, y là các số nguyên, thì:

  1. Nếu và thì .
  2. Nếu và thì .
  3. Nếu và thì .

Việc chứng minh các định lý trên không quá phức tạp, mình sẽ nhường công việc thú vị này cho bạn đọc. Nếu bạn có thắc mắc gì hãy thoải mái comment xuống bên dưới bài viết nhé! :smile:

Mình bonus 2 vấn đề nho nhỏ sau với bạn đọc hiếu kỳ :smiley:

1) Hãy chứng minh nếu một số nguyên là một số lẻ thì luôn chia hết cho 8.

2) Liệu rằng là số nguyên tố với mọi số nguyên ?

1.3) Một vài tính chất của phép chia lấy dư

Phép chia lấy dư có lẽ đã rất quen thuộc với nhiều người, chúng ta đã được học nó từ cấp 1, ví dụ như 9 chia 8 dư 1. Người ta ký hiệu phép chia lấy dư là mod, trong nhiều ngôn ngữ lập trình chúng ta có ký hiệu % với ý nghĩa tương đương. Ví dụ: 9 mod 8 = 1 hay 9%8 = 1

Xem thêm: Hỏi đáp: Quy định chụp ảnh hộ chiếu mặc áo gì?

1.3.1) Định nghĩa

Với và là các số nguyên, ta định nghĩa phép chia lấy dư như sau:

Trong đó là phép chia lấy phần nguyên. Ví dụ, nên . Bạn có thể thử vài số bất kỳ để kiểm chứng định nghĩa trên. :smiley: Có nhiều ứng dụng khá hay của phép chia lấy dư nhưng mình sẽ không đề cập ở bài viết này để tránh lan man.

1.4) Ước chung lớn nhất (greatest common divisor)

1.4.1) Định nghĩa

  1. Một số nguyên được gọi là ước chung của và nếu và cùng chia hết cho , hay nói cách khác, khi và .
  2. Ước chung lớn nhất của và , hai số nguyên khác 0, được định nghĩa là số nguyên lớn nhất trong các ước chung của và . Ta ký hiệu là như sau:

Xem thêm: Appel Reaction

1.4.2) Định lý

  1. Nếu và là các số nguyên thì .
  2. Nếu và là các số nguyên thì .
  3. Nếu , và là các số nguyên thì

Định lý 1 và 2 mình sẽ để cho bạn đọc tự chứng minh, mình chỉ chứng minh định lý 3, đây cũng chính là định lý nền tảng cho giải thuật Euclid. :wink:

Chứng minh Định lý 3:

Ta cần chứng minh rằng ước chung của và giống với ước chung của và . Giả sử rằng và thì và (, là các số nguyên). Khi đó ta có:

Từ đó suy ra là ước của . Vậy là ước chung của và . Ngược lại, ta giả sử là ước chung của và thì và với , là các số nguyên. Khi đó ta có:

Từ đó suy ra là ước chung của và .

Từ hai chứng minh trên ta suy ra tập ước chung của giống với tập ước chung của . Do vậy .

Từ định lý 3 ta rút ra 1 hệ quả quan trọng là nền tảng cho giải thuật Euclid.

1.4.3) Hệ quả Định lý 3

Hệ quả:

Với và là các số nguyên, thì

Chứng minh:

Nhớ lại chút về định nghĩa của phép chia lấy dư: , suy ra với . Do đó hệ quả là đúng.

Áp dụng hệ quả:

Bây giờ chúng ta sẽ sử dụng hệ quả trên kết hợp với Định lý 2 mục 1.4.2) để tính ước chung lớn nhất của 2 số nguyên bất kỳ. Ví dụ, ta muốn tính , quy trình như sau:

gcd(64, 24) = gcd(64 mod 24, 24) = gcd(16, 24) = gcd(24 mod 16, 16) = gcd(8, 16) = gcd(16 mod 8, 8) = gcd(0, 8) = 8 

Như vậy . Bạn có thể thử với các số khác nếu muốn. :smile:

2. Giải thuật Euclid

Thực ra khi thực hiện ví dụ trên là bạn đang chạy giải thuật Euclid rồi đấy. :))

Giải thuật Euclid thực chất là giải thuật giúp bạn tính được ước chung lớn nhất của 2 số nguyên bất kỳ, dựa trên cơ sở toán học mà chúng ta đã đề cập và chứng minh ở trên. Có thể bạn đang cảm thấy giải thuật này cũng chẳng giúp ích được gì lắm đúng không ? Điểm thú vị của giải thuật Euclid ở chỗ nó giúp chúng thực hiện việc tính với các số lớn khá nhanh. Bài viết sau mình sẽ demo việc này cũng như thử xem xét độ phức tạp của giải thuật này.

Bây giờ chúng ta sẽ implement giải thuật Euclid bằng code C++ nhé. Ta làm đúng theo các bước như khi ta thực hiện ví dụ trước thôi.

1 2 3 4 5 6 7 8 9 10 11 
int gcd(int a, int b) { int c = b; a = abs(a); b = abs(b); while(b > 0) { c = b; b = a%b; a = c; } return a; }

Kiến thức có vẻ nhiều mà khi code có mấy dòng nhỉ. :))

Ta nhận thấy ở đây có sự lặp lại của chính hàm , do vậy ta có thể đệ quy đến khi nào một trong hai số hoặc bằng 0. Sau đây là implement giải thuật Euclid theo kiểu đệ quy.

1 2 3 4 5 6 7 8 9 10 
int gcdRecursion(int a, int b) { int c; a = abs(a); b = abs(b); if(b > 0) { c = gcdRecursion(b,a%b); } else c = a; return c; }

Mình tạm kết phần 1 tại đây, trong bài viết sau mình sẽ phân tích độ phức tạp của giải thuật Euclid và đề cập giải thuật Euclid mở rộng. Bạn đọc nếu có gì muốn góp ý gì về bài viết thoải mái comment và nếu cảm thấy bài viết bổ ích thì hãy share để bạn bè cùng đọc nhé!

Chúc bạn một ngày tốt lành ! 🙂

Ngày đăng: July 27, 2018

Chủ đề:

theory

Bình luận

tungluu18

tungluu18

August 01, 2018 at 03:33 PM

bổ ích quá

Trả lời tungluu18

AMC's Blog

AMC’s Blog

August 01, 2018 at 06:07 PM

Cảm ơn bạn, hãy chia sẻ bài viết cho bạn bè mình cùng đọc nữa nhé ! :wink:


Để lại bình luận của bạn     

Cancel

Email của bạn sẽ được giữ bí mật. Các phần bắt buộc được đánh dấu. *

Đang gửi…

Hỗ trợ Markdown.

<!– –>

Chuyên mục: Kiến thức

Related Articles

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Check Also
Close
Back to top button