Chương 6: Phép ngược và khả nghịch

Câu hỏi mở đầu

Phép cộng và phép nhân đi từ hai số tới một số mới. Nhưng nhiều khi ta cần đi theo chiều ngược lại: biết đàn cừu sau khi nhập có 42 con và một đàn có 23 con, đàn kia có bao nhiêu con? Biết 35 con được chia đều vào 5 chuồng, mỗi chuồng bao nhiêu con? Nếu biết kết quả của một phép cộng hay phép nhân và một trong hai số, có tìm lại được số kia không? Phép toán nào có thể "tháo ngược"?

Đi ngược từ kết quả

Rất nhiều việc trong đời sống là đi ngược từ kết quả về nguyên nhân. Nhìn một dấu chân, ta đoán ai đã đi qua. Nhận một tin nhắn mã hóa, người nhận giải mã để đọc được lời gốc. Bị quên mật khẩu ổ khóa số, ta thử lần ngược các con số. Với hai câu hỏi của người chăn cừu cũng vậy: ta biết kết quả của một phép cộng (42) và một số hạng (23), cần tìm số hạng kia; ta biết kết quả của một phép nhân (35) và một thừa số (5), cần tìm thừa số kia.

Nhưng không phải việc gì cũng đi ngược được. Khuấy sữa vào cà phê rồi, không ai tách sữa ra lại được. Một tờ giấy đã cho vào máy hủy thì chữ trên đó coi như mất. Vậy điều gì làm một hành động tháo ngược được, và điều gì làm nó không tháo ngược được? Chương này trả lời câu hỏi ấy, và câu trả lời sẽ là một sợi chỉ chạy suốt cuốn sách.

Tháo ngược và mất thông tin

Hãy gọi một quy tắc biến mỗi đầu vào thành một đầu ra là một biến đổi (transformation). "Cộng thêm 3", "nhân với 5", "lấy số dư khi chia cho 3", "làm tròn đến hàng chục" đều là những biến đổi trên các số tự nhiên.

Tháo ngược một biến đổi nghĩa là: nhìn đầu ra, tìm lại đúng đầu vào đã sinh ra nó. Việc này làm được khi và chỉ khi hai đầu vào khác nhau không bao giờ cho cùng một đầu ra. Lý do đơn giản: nếu hai đầu vào khác nhau cho cùng một đầu ra, thì nhìn đầu ra ấy, không cách nào biết nó đến từ đầu vào nào. Thông tin phân biệt hai đầu vào đã bị mất trên đường đi.

Trái: "cộng 3" đưa các đầu vào khác nhau tới các đầu ra khác nhau, nên tháo ngược được. Giữa: "số dư khi chia 3" dồn nhiều đầu vào về một đầu ra, mất một phần thông tin. Phải: "nhân 0" dồn mọi thứ về 0, mất hết thông tin.

Ba ví dụ trong hình cho ba mức độ:

• "Cộng 3" không làm mất gì: 0 thành 3, 1 thành 4, 2 thành 5, và không có hai số nào thành cùng một số. Từ đầu ra 7, ta biết ngay đầu vào là 4. Tháo ngược "cộng 3" là "trừ 3".
• "Số dư khi chia 3", cách đồng nhất ở Chương 3, làm mất một phần: 1, 4, 7, 10 đều cho số dư 1. Từ đầu ra 1, ta chỉ biết đầu vào nằm trong một lớp, không biết là số nào.
• "Nhân 0" làm mất tất cả: mọi số đều thành 0. Đầu ra không nói gì về đầu vào.

"Làm tròn đến hàng chục" cũng làm mất thông tin: 35, 36, ..., 44 đều thành 40. Ngược lại, đổi một số sang hệ nhị phân ở Chương 4 không làm mất gì: dãy chữ số cho lại đúng con số.

Tháo ngược một chuỗi việc: làm ngược thứ tự. Sáng dậy, ta mang tất rồi đi giày. Tối về, ta tháo giày trước rồi mới tháo tất. Không ai tháo tất trước, vì giày đang trùm lên tất. Hành động làm sau cùng nằm "ở trên cùng", nên phải được tháo ra đầu tiên.

flowchart LR
    A["chân trần"] -->|"mang tất"| B["có tất"] -->|"đi giày"| C["có tất và giày"]
    C -.->|"tháo giày"| D["có tất"] -.->|"tháo tất"| E["chân trần"]

Cấu trúc này không riêng gì tất và giày. Muốn tháo ngược "làm việc thứ nhất rồi làm việc thứ hai", ta phải tháo việc thứ hai trước rồi mới tháo việc thứ nhất. Đây là một hệ quả của sợi chỉ về thứ tự ở Chương 5: khi các việc không giao hoán, thứ tự tháo ngược không thể tùy ý.

Ký hiệu

Ta viết một biến đổi bằng một mũi tên có gạch ở đuôi: \(x \mapsto x + 3\) đọc là "\(x\) biến thành \(x + 3\)". Chữ \(x\) là chỗ trống cho đầu vào.

Phép trừ. Phép trừ (subtraction) được định nghĩa như phép tháo ngược của phép cộng: \(a - b\) là số \(x\) sao cho \(b + x = a\). Ta gọi \(a\) là số bị trừ (minuend), \(b\) là số trừ (subtrahend), \(a - b\) là hiệu (difference). Câu hỏi "đàn kia có bao nhiêu con?" chính là tìm \(x\) với \(23 + x = 42\), tức \(x = 42 - 23\).

Phép chia. Phép chia (division) được định nghĩa như phép tháo ngược của phép nhân: \(a : b\) là số \(x\) sao cho \(b \cdot x = a\). Ta gọi \(a\) là số bị chia (dividend), \(b\) là số chia (divisor), \(a : b\) là thương (quotient). Theo thói quen ở trường, sách viết phép chia bằng dấu hai chấm ở những chương đầu; Chương 10 sẽ dùng thêm cách viết phân số.

Chia có dư. Khi \(b \cdot x = a\) không có nghiệm, ta vẫn có thể chia "được bao nhiêu thì chia": \(a = b \cdot q + r\), trong đó \(q\) là thương, \(r\) là số dư, và \(0 \leq r < b\). Việc này gọi là chia có dư (division with remainder). Ta nói "\(a\) chia cho \(b\) được \(q\), dư \(r\)".

Mỗi định nghĩa trên đặt ra hai câu hỏi riêng: số \(x\) cần tìm có tồn tại không, và nếu có thì có duy nhất không. Phép ngược chỉ có nghĩa khi câu trả lời cho cả hai là "có".

Làm bằng tay

Ví dụ 1 (hai câu hỏi của người chăn cừu). Tìm \(x\) với \(23 + x = 42\), và tìm \(x\) với \(5 \cdot x = 35\).

Với câu thứ nhất, \(x = 42 - 23 = 19\). Kiểm lại bằng cách làm xuôi: \(23 + 19 = 42\). Với câu thứ hai, \(x = 35 : 5 = 7\). Kiểm lại: \(5 \cdot 7 = 35\). Đây chính là công cụ "làm ngược lại" của Chương 2, giờ trở thành định nghĩa của phép trừ và phép chia.

Ví dụ 2 (tháo ngược một chuỗi). Một người nghĩ một số, nhân nó với 3, rồi cộng thêm 5, được 38. Số ban đầu là bao nhiêu?

Chuỗi việc là "nhân 3 rồi cộng 5". Tháo ngược theo thứ tự ngược: trước hết tháo "cộng 5" bằng cách trừ 5, được \(38 - 5 = 33\); rồi tháo "nhân 3" bằng cách chia 3, được \(33 : 3 = 11\). Kiểm lại theo chiều xuôi: \(11 \cdot 3 + 5 = 33 + 5 = 38\).

Nếu tháo sai thứ tự, chia 3 trước, ta gặp ngay \(38 : 3\), không chia hết: con đường bị chặn. Và nếu kết quả là 40 thay vì 38, thì \(40 - 5 = 35\) không chia hết cho 3: không có số tự nhiên nào sinh ra 40 qua chuỗi này. Tháo ngược chỉ làm được với những đầu ra thật sự đạt được.

Ví dụ 3 (chia có dư). Xếp 100 viên bi thành các nhóm 7 viên. Được bao nhiêu nhóm, còn thừa bao nhiêu viên?

Lấy ra từng nhóm 7 viên: sau 14 nhóm đã dùng \(7 \cdot 14 = 98\) viên, còn \(100 - 98 = 2\) viên, không đủ một nhóm nữa. Vậy \(100 = 7 \cdot 14 + 2\): thương 14, số dư 2.

100 viên bi: 14 nhóm đầy, mỗi nhóm 7 viên, và 2 viên thừa. Số dư luôn nhỏ hơn 7, vì nếu thừa từ 7 viên trở lên thì còn lập được một nhóm nữa.

Để ý: chỉ biết thương 14 thì chưa biết số bi ban đầu, vì 98, 99, ..., 104 viên đều cho thương 14. Nhưng biết cả thương lẫn số dư thì biết chính xác: \(7 \cdot 14 + 2 = 100\). Số dư là phần thông tin mà thương bỏ lại. Cặp (thương, số dư) không làm mất gì.

Ví dụ 4 (mật mã dịch chữ). Mã hóa từ TOAN bằng cách thay mỗi chữ cái bằng chữ cái đứng sau nó 3 vị trí trong bảng chữ cái 26 chữ A, B, C, ..., Z, và quay vòng về đầu khi hết (X thành A, Y thành B, Z thành C). Rồi giải mã.

T đứng thứ 20 trong bảng, dịch 3 thành chữ thứ 23 là W; O thành R; A thành D; N thành Q. Vậy TOAN thành WRDQ. Để giải mã, dịch lùi mỗi chữ 3 vị trí: W thành T, R thành O, D thành A, Q thành N. Kiểu mã này gọi là mật mã dịch chữ (shift cipher).

Mật mã dịch chữ như hai vòng chữ cái xoay lệch nhau 3 vị trí. Xoay đi rồi xoay lại: mã hóa khả nghịch.

Mã hóa này khả nghịch vì hai chữ khác nhau luôn thành hai chữ khác nhau: đó là một phép xoay trên vòng tròn 26 chữ, giống hệt số học đồng hồ ở Chương 3. Nhưng chính vì quá dễ tháo ngược, nó cũng quá dễ bị bẻ: chỉ có 25 cách dịch để thử.

Ranh giới

Phép trừ và phép chia không phải lúc nào cũng làm được trong các số tự nhiên. \(3 - 5\) là số \(x\) sao cho \(5 + x = 3\). Nhưng \(5 + x\) luôn lớn hơn hoặc bằng 5, không bao giờ bằng 3. Vậy trong \(\mathbb{N}\), \(3 - 5\) không tồn tại. Tương tự, \(7 : 2\) là số \(x\) sao cho \(2 \cdot x = 7\); nhưng \(2 \cdot 3 = 6\) còn \(2 \cdot 4 = 8\), nên không có số tự nhiên nào như vậy. Hai "lỗ hổng" này sẽ dẫn tới hai cuộc mở rộng: số âm ở Chương 7 và phân số ở Chương 10. Riêng phép chia cho 0 có một vấn đề sâu hơn, dành cho Chương 9.

Có biến đổi làm mất sạch thông tin. Thử trò chơi này: nghĩ một số, nhân đôi, cộng 10, chia đôi, rồi trừ đi số đã nghĩ. Kết quả luôn là 5, dù bạn nghĩ số nào. Với số 7: \(7 \cdot 2 = 14\), \(14 + 10 = 24\), \(24 : 2 = 12\), \(12 - 7 = 5\). Với số 13: \(26\), \(36\), \(18\), \(5\). Cả chuỗi biến đổi dồn mọi đầu vào về một đầu ra duy nhất, như "nhân 0". Người đọc kết quả không thể biết bạn đã nghĩ số nào; đó chính là lý do trò chơi "đoán trúng" được.

Có những biến đổi được thiết kế để không tháo ngược được. Nhiều hệ thống máy tính không lưu mật khẩu của người dùng, mà chỉ lưu kết quả của một biến đổi được thiết kế để rất khó đi ngược. Khi bạn đăng nhập, hệ thống biến đổi mật khẩu bạn gõ rồi so sánh hai kết quả. Ở đây, việc khó tháo ngược là một tính năng chứ không phải khuyết điểm.

Tháo sai thứ tự thì sai kết quả. Như Ví dụ 2 đã cho thấy, chia 3 trước khi trừ 5 thì kẹt ngay. Ở những chương sau, khi có đủ loại số để phép chia luôn làm được, tháo sai thứ tự sẽ không còn kẹt nữa mà lặng lẽ cho ra một đáp số sai. Lỗi lặng lẽ nguy hiểm hơn lỗi làm kẹt.

Bình phương sẽ làm mất một thông tin. Trong các số tự nhiên, hai số khác nhau có bình phương khác nhau, nên "bình phương" tháo ngược được bằng căn bậc hai. Nhưng khi có số âm ở Chương 7, cả 3 lẫn "âm 3" đều có bình phương là 9: bình phương sẽ làm mất thông tin về dấu.

Phát biểu chặt chẽ

Định nghĩa 1 (phép trừ). Với hai số tự nhiên \(a\), \(b\) mà \(a \geq b\), hiệu \(a - b\) là số tự nhiên \(x\) sao cho \(b + x = a\).

Mệnh đề 1. Với \(a \geq b\), số \(x\) trong Định nghĩa 1 tồn tại và duy nhất. Nếu \(a < b\) thì không có số tự nhiên \(x\) nào như vậy.

Chứng minh. Tồn tại: lấy một nhóm \(a\) vật. Vì \(b \leq a\), một nhóm \(b\) vật ghép được vào một phần của nhóm ấy (định nghĩa của thứ tự ở Chương 4). Phần còn lại có một số lượng \(x\) nào đó, và gộp phần đã ghép với phần còn lại cho cả nhóm, nên \(b + x = a\).

Duy nhất: giả sử \(b + x = a\) và \(b + y = a\) với \(x \neq y\), chẳng hạn \(x < y\). Khi đó một nhóm \(x\) vật ghép được vào một phần thực sự của một nhóm \(y\) vật; thêm cùng \(b\) vật vào cả hai, nhóm \(b + x\) vật ghép được vào một phần thực sự của nhóm \(b + y\) vật, nên \(b + x < b + y\) (Chương 4, bài C2: một nhóm hữu hạn không ghép một-một được với một phần thực sự của nó). Điều này trái với \(b + x = a = b + y\).

Không tồn tại khi \(a < b\): với mọi \(x\), nhóm \(b + x\) vật chứa một nhóm \(b\) vật, nên \(b + x \geq b > a\). \(\square\)

Định nghĩa 2 (khả nghịch). Một biến đổi là khả nghịch (invertible) nếu hai đầu vào khác nhau luôn cho hai đầu ra khác nhau. Khi đó, phép ngược (inverse) của nó là biến đổi gán cho mỗi đầu ra đạt được đúng đầu vào đã sinh ra nó.

Chương 20 sẽ tách định nghĩa này thành những khái niệm tinh hơn; ở đây, "khả nghịch" nghĩa là "không làm mất thông tin".

Mệnh đề 2. Trên các số tự nhiên: với mọi \(b\), biến đổi \(x \mapsto x + b\) khả nghịch, và phép ngược của nó là \(y \mapsto y - b\) trên các số \(y \geq b\). Với mọi \(b \geq 1\), biến đổi \(x \mapsto b \cdot x\) khả nghịch, và phép ngược của nó là \(y \mapsto y : b\) trên các bội của \(b\). Biến đổi \(x \mapsto 0 \cdot x\) không khả nghịch.

Chứng minh. Với "cộng \(b\)": nếu \(x + b = y + b\) thì theo phần duy nhất của Mệnh đề 1 (áp dụng cho \(a = x + b\)), \(x = y\). Với "nhân \(b\)", xem bài C2. Với "nhân 0": \(0 \cdot 1 = 0 = 0 \cdot 2\) trong khi \(1 \neq 2\). \(\square\)

Định lý 3 (chia có dư). Với mọi số tự nhiên \(a\) và mọi số tự nhiên \(b \geq 1\), tồn tại duy nhất một cặp số tự nhiên \(q\), \(r\) sao cho

\[ a = b \cdot q + r \quad \text{và} \quad 0 \leq r < b . \]

Chứng minh. Tồn tại: xét dãy \(a\), \(a - b\), \(a - 2b\), ..., trừ dần \(b\) chừng nào số còn lại vẫn lớn hơn hoặc bằng \(b\). Mỗi lần trừ, số còn lại giảm ít nhất 1 (vì \(b \geq 1\)), nên sau hữu hạn lần ta dừng ở một số \(r\) với \(0 \leq r < b\). Nếu đã trừ \(q\) lần thì \(a = b \cdot q + r\).

Duy nhất: giả sử \(a = bq + r = bq' + r'\) với \(0 \leq r < b\) và \(0 \leq r' < b\). Nếu \(q < q'\) thì \(q' \geq q + 1\), nên

\[ a = bq' + r' \geq bq' \geq b(q + 1) = bq + b > bq + r = a , \]

trong đó bất đẳng thức cuối dùng \(r < b\). Ta được \(a > a\), vô lý. Tương tự, \(q' < q\) cũng vô lý. Vậy \(q = q'\), và từ \(bq + r = bq + r'\), phần duy nhất của Mệnh đề 1 cho \(r = r'\). \(\square\)

Định lý 3 trả món nợ của Chương 4: ở đó, chứng minh rằng mỗi số có đúng một cách viết theo một cơ số đã dựa vào tính duy nhất của thương và số dư. Nó cũng cho thấy cặp (thương, số dư) mang đủ thông tin để dựng lại số bị chia: biến đổi \(a \mapsto (q; r)\) là khả nghịch, còn \(a \mapsto q\) hay \(a \mapsto r\) đứng riêng thì không.

Mệnh đề 4 (tháo ngược một chuỗi). Nếu hai biến đổi \(f\) và \(g\) đều khả nghịch, thì chuỗi "làm \(f\) rồi làm \(g\)" cũng khả nghịch, và phép ngược của nó là "tháo \(g\) rồi tháo \(f\)". Chứng minh: bài C3.

Sợi chỉ

• S2. Thông tin và khả nghịch. Đây là chương gốc của sợi chỉ này: một biến đổi tháo ngược được khi và chỉ khi nó không dồn hai đầu vào khác nhau về cùng một đầu ra. Lấy số dư (Chương 3) làm mất thông tin; đổi cơ số (Chương 4) thì không; cặp thương và số dư thì giữ đủ.
• S3. Thứ tự của biến đổi. Tháo ngược một chuỗi phải đi theo thứ tự ngược: tháo giày trước, tháo tất sau. Khi các việc không giao hoán (Chương 5), thứ tự tháo ngược không tùy ý được.

Tóm tắt

• Một biến đổi tháo ngược được khi và chỉ khi hai đầu vào khác nhau không bao giờ cho cùng một đầu ra; nếu không, thông tin đã bị mất.
• Phép trừ là phép tháo ngược của phép cộng (\(a - b\) là số \(x\) với \(b + x = a\)), phép chia là phép tháo ngược của phép nhân (\(a : b\) là số \(x\) với \(b \cdot x = a\)).
• Mỗi phép ngược đặt hai câu hỏi: đáp án có tồn tại không, và có duy nhất không; trong các số tự nhiên, \(3 - 5\) và \(7 : 2\) không tồn tại.
• Chia có dư luôn làm được khi số chia khác 0, và thương cùng số dư là duy nhất; số dư là phần thông tin mà thương bỏ lại.
• Tháo ngược một chuỗi việc phải làm theo thứ tự ngược.
• "Nhân 0", "làm tròn", "lấy số dư" làm mất thông tin; "cộng \(b\)", "nhân \(b\) với \(b \geq 1\)", "đổi cơ số" thì không.

Bài tập

A. Tư duy

A1. Vì sao "cộng 5" áp dụng được cho mọi số tự nhiên, còn phép tháo ngược của nó, "trừ 5", thì chỉ áp dụng được cho các số từ 5 trở lên? Điều này nói gì về "kích thước" của nhóm các đầu ra?

Lời giải

"Cộng 5" đưa mọi số tự nhiên tới các số từ 5 trở lên: đầu ra nhỏ nhất là \(0 + 5 = 5\). Các số 0, 1, 2, 3, 4 không bao giờ là đầu ra. Phép tháo ngược chỉ cần làm việc trên những đầu ra thật sự xuất hiện, nên "trừ 5" chỉ cần (và chỉ có thể) áp dụng cho các số từ 5 trở lên.

Nhóm các đầu ra là một phần thực sự của \(\mathbb{N}\), nhưng vẫn ghép một-một được với cả \(\mathbb{N}\) qua chính phép "cộng 5", giống như số chẵn ghép được với số tự nhiên ở Chương 4. Muốn "trừ 5" áp dụng được cho mọi số, ta phải thêm những số mới làm đầu ra cho \(0 - 5\), \(1 - 5\), ...: đó là số âm.

A2. Biến đổi nào sau đây làm mất thông tin, biến đổi nào không? (a) nhân 2; (b) lấy chữ số hàng đơn vị; (c) viết ngược thứ tự các chữ số (chẳng hạn 123 thành 321); (d) viết số trong hệ nhị phân. Với mỗi biến đổi làm mất thông tin, hãy chỉ ra hai đầu vào khác nhau cho cùng một đầu ra.

Lời giải

(a) Không mất: nếu \(2x = 2y\) thì \(x = y\); phép ngược là chia 2 (trên các số chẵn).

(b) Mất: 3, 13, 23 đều cho chữ số hàng đơn vị là 3.

(c) Mất, một cách bất ngờ: 12 viết ngược là 21, còn 120 viết ngược là 021, tức 21. Hai số khác nhau cho cùng đầu ra; thông tin về các chữ số 0 ở cuối bị mất.

(d) Không mất: theo Chương 4, mỗi số có đúng một cách viết trong hệ nhị phân, và dãy chữ số cho lại đúng con số.

A3. Vì sao khi tháo ngược "mang tất rồi đi giày", ta phải tháo giày trước? Hãy dùng cùng ý tưởng để giải thích vì sao tháo ngược "nhân 3 rồi cộng 5" phải trừ 5 trước rồi mới chia 3.

Lời giải

Việc làm sau (đi giày) trùm lên kết quả của việc làm trước (có tất). Muốn quay về trạng thái trước việc thứ nhất, ta phải đi qua trạng thái giữa, tức trạng thái "có tất", và chỉ tháo giày mới đưa ta về đó.

Với các con số cũng vậy. Đầu ra 38 là kết quả của "cộng 5" áp lên số 33, và 33 là kết quả của "nhân 3" áp lên số ban đầu. Muốn tìm lại 33, ta tháo việc sau cùng: trừ 5. Rồi mới tháo việc trước đó: chia 33 cho 3. Chia 38 cho 3 trước là tháo một việc không phải việc cuối cùng, nên không đưa ta về trạng thái giữa nào cả.

B. Tính toán

B1. Tìm số tự nhiên \(x\) trong mỗi trường hợp, và kiểm lại bằng cách làm xuôi: (a) \(17 + x = 43\); (b) \(x + 28 = 100\); (c) \(6 \cdot x = 54\); (d) \(7 \cdot x = 91\).

Lời giải

(a) \(x = 43 - 17 = 26\); kiểm lại \(17 + 26 = 43\). (b) \(x = 100 - 28 = 72\); kiểm lại \(72 + 28 = 100\). (c) \(x = 54 : 6 = 9\); kiểm lại \(6 \cdot 9 = 54\). (d) \(x = 91 : 7 = 13\); kiểm lại \(7 \cdot 13 = 91\).

B2. (a) Một số được nhân 4 rồi cộng 7, cho kết quả 63. Tìm số ban đầu. (b) Một số được cộng 7 rồi nhân 4, cho kết quả 63. Có số tự nhiên nào như vậy không?

Lời giải

(a) Tháo ngược theo thứ tự ngược: \(63 - 7 = 56\), rồi \(56 : 4 = 14\). Kiểm lại: \(14 \cdot 4 + 7 = 63\).

(b) Tháo ngược: trước hết tháo "nhân 4", tức tìm \(63 : 4\). Nhưng \(4 \cdot 15 = 60\) và \(4 \cdot 16 = 64\), nên 63 không chia hết cho 4. Không có số tự nhiên nào như vậy: 63 không phải là một đầu ra đạt được của chuỗi "cộng 7 rồi nhân 4" (mọi đầu ra của chuỗi này đều chia hết cho 4). Hai chuỗi chỉ khác nhau về thứ tự mà cho những kết quả rất khác nhau.

B3. Tìm thương và số dư: (a) 365 chia cho 7; (b) 1000 chia cho 13; (c) 58 chia cho 60; (d) 2025 chia cho 45.

Lời giải

(a) \(7 \cdot 52 = 364\), nên \(365 = 7 \cdot 52 + 1\): thương 52, dư 1.

(b) \(13 \cdot 76 = 988\) và \(13 \cdot 77 = 1001 > 1000\), nên \(1000 = 13 \cdot 76 + 12\): thương 76, dư 12.

(c) \(58 < 60\), nên \(58 = 60 \cdot 0 + 58\): thương 0, dư 58. (Số dư có thể lớn, miễn là nhỏ hơn số chia.)

(d) \(45 \cdot 45 = 2025\), nên thương 45, dư 0: 2025 chia hết cho 45.

B4. Dùng mật mã dịch chữ 3 vị trí như Ví dụ 4: (a) mã hóa từ HOC; (b) giải mã KRF; (c) nếu mã hóa bằng cách dịch 3 vị trí, thì dịch tới bao nhiêu vị trí cũng có tác dụng giải mã?

Lời giải

(a) H thành K, O thành R, C thành F: HOC thành KRF.

(b) Dịch lùi 3 vị trí: K thành H, R thành O, F thành C: KRF thành HOC.

(c) Dịch tới 23 vị trí: vì \(3 + 23 = 26\), dịch 3 rồi dịch thêm 23 là đi trọn một vòng 26 chữ và quay về chỗ cũ. Đây là số học đồng hồ của Chương 3, với "đồng hồ" có 26 vạch.

B5. Hôm nay là thứ Hai. Hỏi 1000 ngày nữa là thứ mấy?

Lời giải

Chia 1000 cho 7: \(7 \cdot 142 = 994\), nên \(1000 = 7 \cdot 142 + 6\). Sau 142 tuần trọn, thứ trong tuần quay về thứ Hai; thêm 6 ngày nữa là Chủ nhật. Vậy 1000 ngày nữa là Chủ nhật. Chỉ có số dư là quan trọng; thương 142 không ảnh hưởng tới câu trả lời.

B6. Làm tròn đến hàng chục gần nhất (số có chữ số hàng đơn vị là 5 thì làm tròn lên). Những số tự nhiên nào được làm tròn thành 40? Biết một số đã làm tròn thành 40, ta biết gì về số ban đầu?

Lời giải

Các số từ 35 đến 44 được làm tròn thành 40: có 10 số. Biết kết quả là 40, ta chỉ biết số ban đầu nằm trong khoảng từ 35 đến 44; không biết là số nào. Làm tròn dồn 10 đầu vào về một đầu ra, nên mất thông tin, và không có phép tháo ngược.

B7. Nghĩ một số, nhân đôi, cộng 10, chia đôi, rồi trừ đi số đã nghĩ. Thực hiện với các số 7, 13 và 100. Vì sao kết quả luôn là 5?

Lời giải

Với 7: \(14\), \(24\), \(12\), \(12 - 7 = 5\). Với 13: \(26\), \(36\), \(18\), \(18 - 13 = 5\). Với 100: \(200\), \(210\), \(105\), \(105 - 100 = 5\).

Giải thích: nhân đôi rồi cộng 10, rồi chia đôi, cho đúng số đã nghĩ cộng thêm 5 (vì một nửa của "hai lần số đã nghĩ cộng 10" là "số đã nghĩ cộng 5"). Trừ đi số đã nghĩ thì chỉ còn 5. Cả chuỗi làm mất sạch thông tin về số ban đầu.

B8. Chia 2025 lần lượt cho 2, 5, 10 và 100. Ghi thương và số dư. Em thấy số dư khi chia cho 10 và cho 100 liên hệ thế nào với cách viết của 2025?

Lời giải

\(2025 = 2 \cdot 1012 + 1\); \(2025 = 5 \cdot 405 + 0\); \(2025 = 10 \cdot 202 + 5\); \(2025 = 100 \cdot 20 + 25\).

Số dư khi chia cho 10 là chữ số hàng đơn vị (5); số dư khi chia cho 100 là hai chữ số cuối (25); còn thương là phần chữ số còn lại (202 và 20). Đây là lý do việc chia liên tiếp cho cơ số, ở Chương 4, lần ra từng chữ số một.

B9. Có bao nhiêu số tự nhiên nhỏ hơn 100 chia cho 7 dư 3? Liệt kê vài số đầu và số cuối.

Lời giải

Các số ấy có dạng \(7q + 3\): 3, 10, 17, 24, ..., và số lớn nhất nhỏ hơn 100 là \(7 \cdot 13 + 3 = 94\) (vì \(7 \cdot 14 + 3 = 101 > 99\)). Thương \(q\) chạy từ 0 đến 13, nên có 14 số. Cả 14 số này cùng cho một đầu ra "số dư 3": đó là mức độ mất thông tin của việc lấy số dư.

C. Phản ví dụ và chứng minh

C1. Chứng minh luật giản ước (cancellation law) của phép cộng: với mọi số tự nhiên \(a\), \(x\), \(y\), nếu \(a + x = a + y\) thì \(x = y\). Giải thích vì sao luật này chính là tính khả nghịch của biến đổi \(x \mapsto a + x\).

Lời giải

Đặt \(c = a + x = a + y\). Khi đó \(x\) và \(y\) đều là số \(z\) thỏa \(a + z = c\). Theo Mệnh đề 1, số ấy là duy nhất, tức \(x = c - a = y\). \(\square\)

Luật giản ước nói rằng hai đầu vào \(x\) và \(y\) của biến đổi "cộng \(a\)" mà cho cùng một đầu ra thì phải là một. Đó đúng là định nghĩa của khả nghịch: không có hai đầu vào khác nhau nào cho cùng một đầu ra.

C2. Chứng minh rằng với mọi số tự nhiên \(b \geq 1\), biến đổi \(x \mapsto b \cdot x\) khả nghịch: nếu \(b \cdot x = b \cdot y\) thì \(x = y\). Vì sao điều kiện \(b \geq 1\) là cần thiết?

Lời giải

Giả sử \(x \neq y\), chẳng hạn \(x < y\). Khi đó \(y = x + d\) với \(d = y - x \geq 1\). Theo tính phân phối, \(b \cdot y = b \cdot x + b \cdot d\). Vì \(b \geq 1\) và \(d \geq 1\), lưới \(b \times d\) có ít nhất một ô, nên \(b \cdot d \geq 1\) và \(b \cdot y > b \cdot x\). Điều này trái với \(b \cdot x = b \cdot y\). Vậy \(x = y\). \(\square\)

Điều kiện \(b \geq 1\) cần thiết vì với \(b = 0\), \(0 \cdot 1 = 0 \cdot 2\) trong khi \(1 \neq 2\): bước "\(b \cdot d \geq 1\)" hỏng ngay khi \(b = 0\).

C3. Chứng minh Mệnh đề 4: nếu \(f\) và \(g\) khả nghịch thì chuỗi "làm \(f\) rồi làm \(g\)" khả nghịch, và phép ngược của nó là "tháo \(g\) rồi tháo \(f\)". Tìm thêm một ví dụ cho thấy nếu \(f\) không khả nghịch thì chuỗi cũng không khả nghịch, dù \(g\) khả nghịch.

Lời giải

Giả sử hai đầu vào \(x\) và \(x'\) cho cùng một đầu ra của chuỗi, tức \(g\) áp lên \(f(x)\) và \(g\) áp lên \(f(x')\) cho cùng kết quả (ở đây \(f(x)\) là đầu ra của \(f\) khi đầu vào là \(x\)). Vì \(g\) khả nghịch, hai đầu vào của \(g\) phải bằng nhau: \(f(x) = f(x')\). Vì \(f\) khả nghịch, \(x = x'\). Vậy chuỗi khả nghịch.

Để tháo ngược từ một đầu ra \(z\) của chuỗi: tháo \(g\) trước, được đầu vào duy nhất \(y\) của \(g\) sinh ra \(z\); rồi tháo \(f\), được đầu vào duy nhất \(x\) của \(f\) sinh ra \(y\). Làm xuôi lại từ \(x\): \(f\) cho \(y\), rồi \(g\) cho \(z\). Vậy "tháo \(g\) rồi tháo \(f\)" đúng là phép ngược. \(\square\)

Ví dụ: \(f\) là "lấy số dư khi chia cho 2", \(g\) là "cộng 10". Chuỗi đưa 1 và 3 cùng về \(1 + 10 = 11\), nên không khả nghịch, dù \(g\) khả nghịch: thông tin đã mất ở bước \(f\) thì bước sau không lấy lại được.

Câu hỏi để ngỏ

\(3 - 5\) bằng bao nhiêu? Trong thế giới số đếm, câu hỏi này không có đáp án: không số tự nhiên nào cộng với 5 mà được 3. Có nên "mở rộng thế giới" để mọi phép trừ đều có đáp án không? Và nếu có, thì những số mới ấy phải tuân theo luật nào, để các luật cộng và nhân mà ta đã chứng minh không bị phá vỡ?