Phép Chia Trong Toán Học Như Thế Nào Trong Lập Trình

Phép Chia Trong Toán Học Như Thế Nào Trong Lập Trình

Chắc hẳn các bạn còn nhớ bài giới thiệu về những ứng dụng thiết thực của toán học trong lập trình từ A đến Z của mình? (Toán học - Khẩu Bazooka Trong Chiến Trường Lập Trình).

Mình xin giới thiệu series "Toán học", nơi thảo luận những kiến thức "thuần toán" ta có thể ứng dụng trực tiếp trong những bài tập lập trình cơ bản cho đến những phần mềm "đao to búa lớn", đi kèm với đó là những chứng minh "hợp lí hợp tình". Đây chính là bài đầu tiên trong series!

Phép chia là phép toán thứ 4 chúng ta được học, đồng thời là phép tính “khó ở” nhất trong đám anh chị em các phép tính khác. Vì không như phép cộng trừ…, đôi khi phép chia có dư! Nhiều vấn đề lập trình cơ bản lại đòi hỏi chúng ta phải xử lí những phần dư ấy! Tuy nhiên, muốn "thông" phép chia dư, phải "thạo" phép chia hết trước đã!

(Nếu không đề cập thêm gì, những số được nhắc đến trong bài viết này đều là những số không âm)

1. Phép chia hết

Từ khi được học phép chia (lớp 2, 3 hay 4 gì đó, mình không nhớ rõ :) ), chúng ta đều được học điều có vẻ hiển nhiên sau:

Nếu a chia hết cho b, và a : b = c, thì b x c = a (*)

Mệnh đề trên tưởng chừng như đơn giản, nhưng hãy chú ý tới nó, vì sau này nó sẽ rất hữu dụng cho nhiều hệ quả về phép chia mình sắp giới thiệu!

Tiếp theo là những tính chất cơ bản của phép chia mà sau này chúng ta sẽ phải dùng rất nhiều.

  • Nếu a chia hết cho b thì a ≥ b
  • Bắc cầuNếu a chia hết cho b, và b chia hết cho c, thì a cũng chia hết cho c

Chứng minh: Bạn có thể sử dụng trực tiếp mệnh đề (*)

  • Nếu a chia hết cho c, và b chia hết cho c, thì các số a + b, a - b, a * b cũng chia hết cho c

Chứng minh: Mình sẽ chỉ chứng minh cho số a + b. Các số còn lại các bạn có thể dựa vào đó mà tự chứng minh ;)

Giả sử a : c = qa, b : c = qb. Khi đó a = c x qa, b = c x qb

Suy ra a + b = c x qa + c x qb = c x (qa + qb)

Vậy a + b chia hết cho c (vì a + b bằng c nhân với một số nguyên). Đây là điều phải chứng minh.

  • Lưu ý:
    • Điều trên không đúng với số a : b, kể cả khi a chia hết cho b. Một ví dụ dễ thấy là a = 8, b = 4, c = 4
    • Điều ngược lại là không đúng. Tức là, nếu a + b chia hết cho c, thì chưa chắc cả ab đều chia hết cho c

2. Phép chia dư - Đồng dư thức

Phép chia dư

Cho trước 2 số ab. Khi đó, nếu a chia b bằng q và dư r (0 ≤ r < b) thì ta sẽ viết như sau: a = q x b + r

Có lẽ các bạn đã quen với mệnh đề trên từ khi mới bập bẹ phép chia có dư. Tuy nhiên, toán học có một cách phát biểu chính xác hơn, chặt chẽ hơn:

Định lí về phép chia có dư: Cho trước 2 số ab. Khi đó, tồn tại duy nhất 2 số q, r (0 ≤ r < b) để a = q x b + r

Có thể các bạn đang bối rối về cụm từ "tồn tại duy nhất" kia. Hiểu đơn giản thì nó có nghĩa là "có-1-không-2"

Chứng minh: Chúng ta sẽ phản chứng, tức là giả sử điều ngược lại với điều cần phải chứng minh, rồi chứng minh điều đó sai. Đây là một phương pháp chứng minh toán học phổ biến mà mình sẽ sử dụng xuyên suốt series này.

Giả sử tồn tại 2 cặp số là (q1, r1)(q2, r2) sao cho a = q1 x b + r1 và a = q2 x b + r2

Ta nhận thấy rằng chỉ cần một trong 2 cặp: (q1, q2) hoặc (r1, r2) bằng nhau thì sẽ kéo theo cặp còn lại bằng nhau luôn. Vậy q1 != q2 và r1 != r2

a = a ⇔ q1 x b + r1 = q2 x b + r2 ⇔ q1 x b - q2 x b = r2 - r1 ⇔ (q1 - q2) x b = r2 - r1

Trong đẳng thức trên, vế trái chia hết cho b, còn vế phải thì không. Vô lí. Vậy ta đã hoàn tất chứng minh.

Có thể các bạn đang thắc mắc rằng mệnh đề trên đây có ý nghĩa gì đối với lập trình. Thực ra, nó là một tiền đề cơ bản nhưng quan trọng để chứng minh thuật toán Euclid, một giải thuật rất hữu dụng và nhanh chóng để tìm ước chung lớn nhất của 2 số mà chúng ta sẽ bàn tới nhiều hơn trong những bài tiếp theo của series.

Phép đồng dư

Đây chính là phần rất quan trọng trong chứng minh những mệnh đề, định lí toán học cũng như trong những vấn đề lập trình dạng "trả về kết quả modulo 109 + 7"

Định nghĩa: a đồng dư với b theo modulo m khi và chỉ khi a chia mb chia m đều cho ra cùng một số dư. Kí hiệu: a ≡ b (mod m) (yep, là 3 dấu gạch chứ không phải là 2)

Xử lí đồng dư trong các vấn đề cơ bản

Đây có lẽ là phần nhiều bạn đang chờ đợi!

Khi các bạn đã quen với việc xử lí "modulo một số m", có lẽ các bạn cũng đã quen với "3 dòng thần thánh" sau:

(a + b) % m = ((a % m) + (b % m)) % m
(a - b) % m = ((a % m) - (b % m)) % m
(a x b) % m = ((a % m) x (b % m)) % m

Thực ra, chúng ta sẽ không đi sâu vào những việc như "xử lí tràn số" ở đây mà sẽ chỉ là chứng minh 3 đẳng thức trên. Một lần nữa mình sẽ chỉ chứng minh dòng phép cộng. Các bạn hãy thử sức với 2 phép còn lại nhé!

Giả sử a = qa x m + ra và b = qb x m + rb (0 ≤ ra, rb < m) (áp dụng định lí trên), tức là a % m = ra và b % m = rb 

Ta thấy ở cả 2 vế, chúng ta đều chia cho m lấy số dư. Vậy theo định nghĩa của phép đồng dư, chúng ta sẽ phải chứng minh: 

(a + b) ≡ (a % m) + (b % m) (mod m)

// Vế trái
(a + b) ≡ (qa x m + ra + qb x m + rb) (mod m)
        ≡ [(qa + qb) x m + (ra + rb)] (mod m) 
// (qa + qb) x m chia hết cho m, tức là nó chia m dư 0
        ≡ ra + rb (mod m)
// Vế phải
(a % m) + (b % m) ≡ (ra + rb) (mod m)
=> (a + b) ≡ (a % m) + (b % m) (mod m) // Chứng minh xong

Bonus: Chứng minh các dấu hiệu chia hết cơ bản

Chắc hẳn hồi tiểu học, cấp 2, các bạn đã ít nhiều học làm sao để biết một số có chia hết cho 2, cho 3, cho 5 ... hay không. Giờ chúng ta sẽ tập trung chứng minh những dấu hiệu đó bằng cách sử dụng những mệnh đề chúng ta có sẵn ở trên nhé!

Dĩ nhiên, bản thân một vài dấu hiệu như chia hết cho 2, cho 5, cho 10 khá là hiển nhiên (chỉ xét chữ số cuối). Nhưng đối với những số "xấu" như chia cho 3, cho 7, cho 9, mọi chuyện không đơn giản như vậy.

Dấu hiệu chia hết cho 3/ cho 9: Nếu tổng các chữ số của n chia hết cho 3/ cho 9 thì n chia hết cho 3/ cho 9

Chứng minh: Mình sẽ chỉ chứng minh trường hợp chia hết cho 3. Chia hết cho 9 thì cũng tương tự như vậy.

Chúng ta sẽ chứng minh điều chặt chẽ hơn sau: n ≡ S(n) (mod 3) với S(n) là tổng các chữ số của n

Đặt n = akak-1...a1. (ak, ak-1, ..., a0 là các chữ số của n)

n - S(n) = akak-1...a0 - (a+ ak-1 + ... + a0)

              = (ak x 10k - ak) + (ak-1 x 10k-1 - ak-1) + ... + (a0 x 100 - a0)

              = ak x 99...9 (k chữ số 9) + ak-1 x 99...9 (k - 1 chữ số 9) + ... (Số này chia hết cho 3, vì mỗi số hạng đều chia hết cho 3)

Suy ra n - S(n) ≡ 0 (mod 3) => n ≡ S(n) (mod 3)

Dấu hiệu chia hết cho 7

Đây là một dấu hiệu khá phức tạp nên mình sẽ trình bày bằng đoạn pseudocode (code giả) như sau:

sum = 0
// Chạy qua từng chữ số của n từ trái sang phải
for d in n
    sum = sum * 3 + d
if (sum % 7 == 0) (n % 7 == 0) = true

Chứng minh: Ta sẽ tiếp tục chứng minh mệnh đề mạnh như sau: n ≡ sum (mod 7) (sum là giống ở pseudocode trên)

Đặt n = akak-1...a0.

Ta nhận thấy 1 cách tính khác của sum là: sum = ak x 3k + ak-1 x 3k-1 + ... + a0

n - sum = (ak x 10k - ak x 3k) + (ak-1 x 10k-1 - ak-1 x 3k-1) + ... + (a0 x 100 - a0)

             = ak x (10k - 3k) + ak-1 x (10k-1 - 3k-1) + ... + 0

Mà theo hằng đẳng thức: 10a - 3a = (10 - 3)(10a - 1 + ... + 3a - 1) chia hết cho 7.

Suy ra n - sum chia hết cho 7 => n - sum ≡ 0 (mod 7) => n ≡ sum (mod 7)

Tạm kết

Trên đây là "tất tần tật" về phép chia, kể cả kiến thức xử lí đồng dư trong những bài lập trình cơ bản!

Có lẽ bài này không phải là những gì các bạn đang kì vọng. Nhưng hãy yên tâm! Dù sao đây cũng là bài viết đầu tiên của series. Mình khẳng định rằng những bài viết sau sẽ hữu ích hơn. Hãy đón xem nhé!