Chương 8: Chia hết và số nguyên tố

Câu hỏi mở đầu

Phép cộng giờ đã luôn tháo ngược được: mọi phép trừ đều có đáp án. Còn phép nhân thì chưa: 12 chia hết cho 3 nhưng không chia hết cho 5, và \(7 : 2\) vẫn chưa có nghĩa. Trước khi mở rộng thêm, hãy nhìn kỹ bản thân phép nhân: số nào chia hết cho số nào? Có những số "không thể tách nhỏ" thành tích của những số nhỏ hơn không, như những nguyên tử của phép nhân?

Nhìn vào bên trong phép nhân

Lấy 12 viên sỏi. Ta xếp được chúng thành hình chữ nhật theo nhiều cách: một hàng 12 viên, hai hàng 6 viên, ba hàng 4 viên. Giờ lấy 13 viên sỏi: thử mãi cũng chỉ xếp được một hàng dài. Hai hàng thì thừa một viên, ba hàng thì thừa một viên, và cứ thế.

12 xếp được thành hình chữ nhật 1 hàng, 2 hàng, 3 hàng. 13 chỉ xếp được một hàng.

Vậy có hai loại số. Có những số "vỡ" được thành tích của những số nhỏ hơn: \(12 = 3 \cdot 4 = 2 \cdot 2 \cdot 3\). Và có những số không vỡ được, như 13. Giống như các phân tử được ghép từ nguyên tử, các số tự nhiên được ghép bằng phép nhân từ những số không vỡ được. Chương này hỏi ba câu: nguyên tử của phép nhân là những số nào; mỗi số có ghép được từ chúng không; và cách ghép có duy nhất không.

Những câu hỏi này không chỉ để ngắm. Chúng quyết định cách rút gọn phân số ở Chương 10, giải thích các mẹo nhận biết số chia hết cho 3 hay cho 9, và nằm ở nền của nhiều hệ mã hóa dùng hằng ngày trên mạng.

Hình chữ nhật, nguyên tử và phân tử

Nói "12 chia hết (divisible) cho 3" nghĩa là 12 viên sỏi xếp được thành 3 hàng đầy, không thừa viên nào. Khi đó 3 là một ước (divisor) của 12, và 12 là một bội (multiple) của 3. Các ước của 12 chính là những số có thể làm số hàng: 1, 2, 3, 4, 6, 12.

Số 13 chỉ có hai ước là 1 và 13: chỉ xếp được thành một hàng 13 viên, hoặc 13 hàng mỗi hàng một viên, mà hai cách này thật ra là một. Như đã nhắc ở Chương 1, một số tự nhiên lớn hơn 1 chỉ có hai ước là 1 và chính nó gọi là số nguyên tố. Số lớn hơn 1 mà không nguyên tố gọi là hợp số (composite number). Số 1 không được xếp vào loại nào; phần ranh giới sẽ giải thích vì sao.

Tách mãi phải dừng. Một hợp số luôn tách được thành tích của hai số nhỏ hơn nó. Nếu một trong hai số ấy lại là hợp số, ta tách tiếp. Chẳng hạn \(360 = 36 \cdot 10 = (6 \cdot 6) \cdot (2 \cdot 5) = (2 \cdot 3) \cdot (2 \cdot 3) \cdot 2 \cdot 5\). Quá trình này phải dừng, vì mỗi lần tách, các thừa số nhỏ đi, mà các số tự nhiên không thể nhỏ đi mãi. Khi dừng, mọi thừa số đều là số nguyên tố.

Hai cách tách 360 khác nhau, nhưng kết thúc ở cùng các lá nguyên tố: ba số 2, hai số 3 và một số 5.

Hình cho thấy một điều đáng ngạc nhiên. Tách 360 theo hai con đường khác nhau, ta vẫn kết thúc ở cùng một bộ nguyên tử. Liệu có phải luôn như vậy không? Hóa ra là có, và đó là một định lý sâu, không phải một điều hiển nhiên. Phần ranh giới sẽ cho thấy một "thế giới số" khác, nơi điều này sai.

Tìm các nguyên tử: cái sàng. Để tìm mọi số nguyên tố đến 100, viết các số từ 2 đến 100, rồi gạch đi mọi bội thực sự của 2 (4, 6, 8, ...), mọi bội thực sự của 3, của 5, của 7. Những số còn lại không bị gạch là số nguyên tố. Cách làm này gọi là sàng Eratosthenes (sieve of Eratosthenes).

Sau khi gạch các bội của 2, 3, 5, 7, còn lại đúng 25 số nguyên tố nhỏ hơn 100.

Vì sao chỉ cần gạch tới bội của 7? Nếu một hợp số không quá 100 tách được thành \(a \cdot b\) với cả hai thừa số đều lớn hơn 10, thì tích lớn hơn \(10 \cdot 10 = 100\), vô lý. Vậy nó có một thừa số không quá 10, và do đó có một ước nguyên tố không quá 10, tức là 2, 3, 5 hoặc 7.

Ký hiệu

Ta viết \(a \mid b\) (đọc là "\(a\) là ước của \(b\)", hay "\(b\) chia hết cho \(a\)") khi có một số nguyên \(k\) với \(b = k \cdot a\); viết \(a \nmid b\) khi không có. Chẳng hạn \(3 \mid 12\) và \(5 \nmid 12\). Cần phân biệt rõ: \(a \mid b\) là một khẳng định, đúng hoặc sai, còn \(a : b\) là một số. Viết nhầm hai ký hiệu này là lỗi rất hay gặp.

Khi một số nguyên tố xuất hiện nhiều lần trong phân tích, ta dùng số mũ để viết gọn: \(360 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5 = 2^3 \cdot 3^2 \cdot 5\). Cách viết này gọi là phân tích ra thừa số nguyên tố (prime factorization).

Số lớn nhất là ước của cả \(a\) lẫn \(b\) gọi là ước chung lớn nhất (greatest common divisor) của chúng, viết \(\text{ƯCLN}(a; b)\). Số dương nhỏ nhất là bội của cả hai gọi là bội chung nhỏ nhất (least common multiple), viết \(\text{BCNN}(a; b)\).

Cuối cùng, để viết chặt chẽ số học đồng hồ của Chương 3: với số nguyên dương \(n\), ta viết

\[ a \equiv b \pmod{n} \]

(đọc là "\(a\) đồng dư với \(b\) theo môđun \(n\)") khi \(n \mid a - b\), tức khi \(a\) và \(b\) có cùng số dư khi chia cho \(n\). Quan hệ này gọi là đồng dư (congruence), và \(n\) gọi là môđun (modulus). Trên mặt đồng hồ, \(13 \equiv 1 \pmod{12}\).

Làm bằng tay

Ví dụ 1 (phân tích và đếm ước). Phân tích 360 ra thừa số nguyên tố, rồi đếm xem 360 có bao nhiêu ước.

Như ở trên, \(360 = 2^3 \cdot 3^2 \cdot 5\). Mỗi ước của 360 được ghép từ một phần các nguyên tử ấy: lấy từ 0 đến 3 thừa số 2, từ 0 đến 2 thừa số 3, và 0 hoặc 1 thừa số 5. Có 4 cách chọn số thừa số 2, 3 cách chọn số thừa số 3, 2 cách chọn số thừa số 5. Các lựa chọn xếp thành một hình hộp \(4 \times 3 \times 2\) như ở Chương 5, nên 360 có \(4 \cdot 3 \cdot 2 = 24\) ước.

Ví dụ 2 (thuật toán Euclid). Tìm \(\text{ƯCLN}(360; 84)\) và \(\text{BCNN}(360; 84)\).

Chia có dư liên tiếp, mỗi lần lấy số chia cũ chia cho số dư mới:

\[ \begin{aligned} 360 &= 84 \cdot 4 + 24, \\ 84 &= 24 \cdot 3 + 12, \\ 24 &= 12 \cdot 2 + 0 . \end{aligned} \]

Số dư khác 0 cuối cùng là 12, nên \(\text{ƯCLN}(360; 84) = 12\). Cách làm này gọi là thuật toán Euclid (Euclidean algorithm). Kiểm lại bằng phân tích: \(84 = 2^2 \cdot 3 \cdot 7\) và \(360 = 2^3 \cdot 3^2 \cdot 5\); phần chung là \(2^2 \cdot 3 = 12\). Bội chung nhỏ nhất lấy mỗi nguyên tử với số lần nhiều nhất: \(2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520\). Cũng có thể tính \(360 \cdot 84 : 12 = 2520\).

Thuật toán Euclid có một hình ảnh đẹp. Lấy một tờ giấy \(360 \times 84\), cắt ra những hình vuông lớn nhất có thể: được 4 hình vuông cạnh 84, còn thừa một dải \(24 \times 84\). Từ dải ấy cắt được 3 hình vuông cạnh 24, còn thừa \(24 \times 12\), cắt vừa khít 2 hình vuông cạnh 12. Hình vuông nhỏ nhất, cạnh 12, lát kín được mọi mảnh trước nó, và do đó lát kín cả tờ giấy: nó chính là ước chung lớn nhất.

Thuật toán Euclid như việc cắt hình vuông: 4 hình vuông cạnh 84, 3 hình vuông cạnh 24, 2 hình vuông cạnh 12. Cạnh của hình vuông cuối cùng là ước chung lớn nhất.

Ví dụ 3 (vì sao dấu hiệu chia hết cho 9 đúng). Kiểm tra 2025 có chia hết cho 9 không, và giải thích mẹo "cộng các chữ số".

Tổng các chữ số của 2025 là \(2 + 0 + 2 + 5 = 9\), chia hết cho 9, nên 2025 chia hết cho 9; thật vậy \(2025 = 9 \cdot 225\). Lý do: \(10 = 9 + 1\), nên \(10 \equiv 1 \pmod 9\); tương tự \(100 = 99 + 1 \equiv 1\) và \(1000 = 999 + 1 \equiv 1\). Do đó

\[ 2025 = 2 \cdot 1000 + 0 \cdot 100 + 2 \cdot 10 + 5 \equiv 2 + 0 + 2 + 5 \pmod 9 . \]

Mỗi số đồng dư với tổng các chữ số của nó theo môđun 9. Bước "thay 1000 bằng 1 ở giữa một phép tính" được phép nhờ Định lý 5 ở dưới.

Ví dụ 4 (số học đồng hồ, chặt chẽ). Ở Chương 3, ta thấy \(7 + 8\) và \(19 + 32\) cho cùng một vị trí kim giờ. Giờ viết lại: \(7 \equiv 19\) và \(8 \equiv 32 \pmod{12}\), và quả thật \(7 + 8 = 15 \equiv 3\), \(19 + 32 = 51 \equiv 3 \pmod{12}\). Với phép nhân cũng vậy: \(7 \cdot 8 = 56 = 12 \cdot 4 + 8\) và \(19 \cdot 32 = 608 = 12 \cdot 50 + 8\), cùng đồng dư với 8. Định lý 5 chứng minh rằng điều này luôn đúng.

Ranh giới

Vì sao 1 không phải số nguyên tố. Số 1 cũng "không vỡ được", vậy sao không gọi nó là số nguyên tố? Vì nếu gọi, thì \(6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3\) sẽ có vô số cách phân tích thành "số nguyên tố", và định lý về tính duy nhất phải kèm thêm một câu "không kể các thừa số 1" vướng víu. Người ta chọn định nghĩa sao cho định lý phát biểu gọn nhất. Đây là một quy ước, nhưng một quy ước phục vụ cấu trúc: nó không làm thay đổi sự thật nào, chỉ làm cho sự thật dễ nói hơn.

Tính duy nhất không hiển nhiên: thế giới số chẵn. Hãy tưởng tượng một thế giới chỉ có các số chẵn \(2, 4, 6, 8, \dots\). Trong thế giới ấy, gọi một số là "nguyên tố" nếu nó không là tích của hai số chẵn. Số 2 "nguyên tố". Số 6 cũng "nguyên tố", vì \(6 = 2 \cdot 3\) mà 3 không có trong thế giới này. Số 18 cũng vậy. Nhưng

\[ 36 = 2 \cdot 18 = 6 \cdot 6 , \]

hai cách phân tích 36 thành tích các "số nguyên tố" của thế giới số chẵn, hoàn toàn khác nhau. Vậy tính duy nhất của phân tích trong \(\mathbb{N}\) không phải là một điều hiển nhiên về logic. Nó là một tính chất đặc biệt của các số tự nhiên, và cần một chứng minh thật sự. Bài C3 chỉ ra chỗ mà chứng minh ấy hỏng trong thế giới số chẵn.

Dễ nhân, khó tách. Máy tính nhân hai số nguyên tố có hàng trăm chữ số trong chớp mắt. Nhưng cho trước tích của chúng, với những phương pháp đã biết, việc tìm lại hai thừa số có thể tốn một khối lượng tính toán khổng lồ. Theo Định lý 4 dưới đây, phép nhân các số nguyên tố "không làm mất thông tin" (tích xác định duy nhất các thừa số), nhưng tháo ngược nó trong thực tế lại cực khó. Nhiều hệ mã hóa hiện đại dựa vào chính khoảng cách giữa "tháo ngược được về nguyên tắc" và "tháo ngược được trong thực tế" ấy.

Mẫu hình trong số nguyên tố rất khó đoán. Chương 1 đã cho thấy \(n^2 + n + 41\) tưởng sinh ra toàn số nguyên tố rồi hỏng. Người ta chưa biết một công thức đơn giản nào sinh ra mọi số nguyên tố. Còn có vô số số nguyên tố hay không? Có, và Chương 17 sẽ chứng minh điều đó.

Phép thử bằng số dư chỉ bác bỏ được. Mẹo cộng chữ số kiểm tra được phép tính (bài B7, B8), nhưng như mọi phép thử ở Chương 2, nó chỉ bác bỏ, không xác nhận: đổi chỗ hai chữ số của một đáp số sai không làm đổi tổng chữ số, nên lỗi ấy lọt qua.

Phát biểu chặt chẽ

Định nghĩa 1. Với các số nguyên \(a\), \(b\), ta nói \(a \mid b\) nếu tồn tại số nguyên \(k\) với \(b = k \cdot a\). Một số tự nhiên \(p > 1\) là số nguyên tố nếu các ước dương của nó chỉ là 1 và \(p\).

Bổ đề 1. Nếu \(d \mid a\) và \(d \mid b\) thì với mọi số nguyên \(x\), \(y\), ta có \(d \mid ax + by\). Đặc biệt \(d \mid a - q b\) với mọi số nguyên \(q\).

Chứng minh. Viết \(a = d m\) và \(b = d n\). Khi đó \(ax + by = d m x + d n y = d(mx + ny)\), là một bội của \(d\). \(\square\)

Định lý 2 (thuật toán Euclid đúng). Nếu \(a = b q + r\) thì các ước chung của \(a\) và \(b\) chính là các ước chung của \(b\) và \(r\). Do đó \(\text{ƯCLN}(a; b) = \text{ƯCLN}(b; r)\), và số dư khác 0 cuối cùng của thuật toán Euclid là \(\text{ƯCLN}(a; b)\).

Chứng minh. Nếu \(d\) là ước chung của \(a\) và \(b\), thì theo Bổ đề 1, \(d \mid a - qb = r\), nên \(d\) là ước chung của \(b\) và \(r\). Ngược lại, nếu \(d\) là ước chung của \(b\) và \(r\), thì \(d \mid bq + r = a\). Hai nhóm ước chung trùng nhau, nên số lớn nhất của chúng cũng trùng nhau. Dọc thuật toán, số dư giảm dần nên thuật toán dừng khi số dư bằng 0; lúc ấy \(a\) chia hết cho \(b\) và \(\text{ƯCLN}(a; b) = b\). \(\square\)

Nhóm các ước chung là một bất biến của mỗi bước thuật toán: số thay đổi, nhưng các ước chung thì không.

Mệnh đề 3 (đẳng thức Bézout). Với các số nguyên dương \(a\), \(b\), tồn tại các số nguyên \(x\), \(y\) sao cho \(ax + by = \text{ƯCLN}(a; b)\).

Chứng minh. Dọc thuật toán Euclid, mỗi số dư bằng số bị chia trừ đi bội của số chia. Số dư đầu tiên \(a - bq\) có dạng \(ax + by\). Nếu hai số liên tiếp trong thuật toán đều có dạng \(ax + by\), thì số dư tiếp theo, bằng số trước trừ bội của số sau, cũng có dạng ấy. Vậy mọi số dư, kể cả số dư khác 0 cuối cùng, đều có dạng \(ax + by\). \(\square\)

Kết quả này thường được gọi là đẳng thức Bézout (Bézout's identity). Với 360 và 84, đi ngược thuật toán: \(12 = 84 - 24 \cdot 3 = 84 - (360 - 84 \cdot 4) \cdot 3 = 84 \cdot 13 - 360 \cdot 3\). Kiểm lại: \(1092 - 1080 = 12\).

Bổ đề 4 (bổ đề Euclid). Nếu \(p\) là số nguyên tố và \(p \mid ab\) thì \(p \mid a\) hoặc \(p \mid b\).

Chứng minh. Giả sử \(p \nmid a\). Các ước dương của \(p\) chỉ là 1 và \(p\), mà \(p\) không chia hết \(a\), nên \(\text{ƯCLN}(p; a) = 1\). Theo Mệnh đề 3, có các số nguyên \(x\), \(y\) với \(px + ay = 1\). Nhân hai vế với \(b\): \(b = pbx + aby\). Số hạng thứ nhất là bội của \(p\); số hạng thứ hai là bội của \(ab\), mà \(p \mid ab\). Theo Bổ đề 1, \(p \mid b\). \(\square\)

Bổ đề 4 thường được gọi là bổ đề Euclid (Euclid's lemma). Nó là chìa khóa cho định lý quan trọng nhất của chương.

Định lý 5 (định lý cơ bản của số học). Mọi số tự nhiên \(n \geq 2\) viết được thành tích các số nguyên tố, và cách viết ấy là duy nhất nếu không kể thứ tự các thừa số.

Chứng minh. Sự tồn tại là lập luận "tách mãi phải dừng" ở đầu chương. Sự duy nhất: giả sử \(p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_m\) với mọi \(p_i\), \(q_j\) là số nguyên tố. Số \(p_1\) chia hết vế trái nên chia hết vế phải. Áp dụng Bổ đề 4 nhiều lần (tách vế phải thành \(q_1\) nhân phần còn lại, rồi lặp lại), \(p_1\) chia hết một \(q_j\) nào đó. Vì \(q_j\) là số nguyên tố, ước dương \(p_1 > 1\) của nó phải bằng chính nó: \(p_1 = q_j\). Giản ước thừa số chung này ở hai vế (theo luật giản ước của Chương 6) và lặp lại. Mỗi lần hai vế mất cùng một số nguyên tố, cho tới khi một vế hết thừa số; khi đó vế kia cũng phải hết, vì tích của các số nguyên tố không thể bằng 1. Vậy hai cách viết có đúng cùng những thừa số. \(\square\)

Tên gọi "định lý cơ bản của số học" (fundamental theorem of arithmetic) nói lên vai trò của nó: nhờ nó, mỗi số tự nhiên được mô tả trọn vẹn bằng danh sách số mũ của các nguyên tử, không mất chút thông tin nào.

Định lý 6 (đồng dư tương thích với cộng và nhân). Nếu \(a \equiv a' \pmod n\) và \(b \equiv b' \pmod n\) thì

\[ a + b \equiv a' + b' \pmod n \qquad \text{và} \qquad a \cdot b \equiv a' \cdot b' \pmod n . \]

Chứng minh. Theo giả thiết, \(a' = a + ns\) và \(b' = b + nt\) với các số nguyên \(s\), \(t\). Khi đó \(a' + b' = (a + b) + n(s + t)\), và

\[ a' b' = (a + ns)(b + nt) = ab + n(at + bs + nst) . \]

Cả hai hiệu \((a' + b') - (a + b)\) và \(a'b' - ab\) đều là bội của \(n\). \(\square\)

Định lý 6 trả món nợ của Chương 3: cộng hay nhân các lớp trên mặt đồng hồ không phụ thuộc vào đại diện được chọn. Và nó biện minh cho Ví dụ 3: trong một phép tính theo môđun 9, ta được thay 1000 bằng 1.

Sợi chỉ

• S1. Bất biến qua biến đổi. Mỗi bước của thuật toán Euclid thay cặp số nhưng giữ nguyên nhóm các ước chung. Lớp đồng dư của một tổng hay một tích không đổi khi thay các số bằng những đại diện khác của lớp, như trên mặt đồng hồ ở Chương 3.
• S2. Thông tin và khả nghịch. Phân tích ra thừa số nguyên tố mô tả một số không mất thông tin (Định lý 5), khác với số dư ở Chương 6 chỉ giữ một phần. Nhưng "không mất thông tin" không có nghĩa là "dễ tháo ngược": tách một tích lớn ra thừa số rất khó.
• S6. Biểu diễn khác nhau của cùng một cấu trúc. Chia hết là xếp được hình chữ nhật; thuật toán Euclid là cắt hình vuông; các ước của 360 là các ô của một hình hộp \(4 \times 3 \times 2\) như ở Chương 5.

Tóm tắt

• \(a \mid b\) nghĩa là \(b = k \cdot a\) với một số nguyên \(k\): \(b\) vật xếp được thành \(a\) hàng đầy.
• Số nguyên tố là số lớn hơn 1 chỉ có hai ước là 1 và chính nó; chúng là nguyên tử của phép nhân, và sàng Eratosthenes tìm ra chúng.
• Thuật toán Euclid tìm ước chung lớn nhất bằng chia có dư liên tiếp; nó đúng vì mỗi bước giữ nguyên nhóm các ước chung.
• Ước chung lớn nhất luôn viết được thành \(ax + by\) (Bézout), và từ đó suy ra: số nguyên tố chia hết một tích thì chia hết một thừa số (bổ đề Euclid).
• Mọi số tự nhiên từ 2 trở lên phân tích được thành tích các số nguyên tố theo đúng một cách; tính duy nhất này không hiển nhiên, như thế giới số chẵn cho thấy.
• Đồng dư theo môđun \(n\) tương thích với cộng và nhân; đó là lý do số học đồng hồ và các dấu hiệu chia hết cho 3, cho 9 đúng.
• Số 1 không được gọi là số nguyên tố, một quy ước chọn ra để định lý phát biểu gọn.

Bài tập

A. Tư duy

A1. Vì sao người ta quy ước 1 không phải số nguyên tố? Nếu gọi 1 là số nguyên tố thì định lý cơ bản của số học phải phát biểu lại thế nào?

Lời giải

Nếu 1 là số nguyên tố, mọi số sẽ có vô số cách phân tích thành "số nguyên tố": \(6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3\), và cứ thế. Định lý sẽ phải nói: "phân tích là duy nhất nếu không kể thứ tự và không kể các thừa số 1". Quy ước loại số 1 ra không làm thay đổi sự thật nào; nó chỉ đặt ranh giới của khái niệm sao cho định lý quan trọng nhất về khái niệm ấy phát biểu gọn gàng.

A2. Dùng hình ảnh xếp sỏi thành hình chữ nhật, giải thích vì sao các ước của một số thường đi thành từng cặp, và vì sao chỉ số chính phương mới có một số lẻ ước. Kiểm tra với 36 và 48.

Lời giải

Nếu \(n\) viên sỏi xếp được thành \(d\) hàng thì mỗi hàng có \(n : d\) viên, và xoay hình chữ nhật đi ta được \(n : d\) hàng. Vậy các ước đi thành cặp \(d\) và \(n : d\). Hai ước trong một cặp chỉ trùng nhau khi \(d = n : d\), tức \(d \cdot d = n\): hình chữ nhật là hình vuông. Chỉ số chính phương mới có một hình vuông như vậy, nên chỉ nó có một ước "không có bạn", và tổng số ước là số lẻ.

Với 36: các cặp là \((1; 36)\), \((2; 18)\), \((3; 12)\), \((4; 9)\), và riêng \(6\) tự ghép với chính nó vì \(6 \cdot 6 = 36\). Có \(4 \cdot 2 + 1 = 9\) ước, số lẻ. Với 48: các cặp \((1; 48)\), \((2; 24)\), \((3; 16)\), \((4; 12)\), \((6; 8)\), có 10 ước, số chẵn.

A3. Phép nhân hai số nguyên tố lớn rất nhanh, còn việc tách tích của chúng ra thừa số thì cực khó. Điều này có mâu thuẫn với việc phép nhân "không làm mất thông tin" theo định lý cơ bản của số học không?

Lời giải

Không mâu thuẫn. "Không làm mất thông tin" là một khẳng định về sự tồn tại: từ tích, có đúng một cặp thừa số nguyên tố, nên về nguyên tắc có thể tìm lại chúng (chẳng hạn thử chia cho mọi số nhỏ hơn). "Khó tháo ngược" là một khẳng định về chi phí: với những phương pháp đã biết, việc tìm lại tốn quá nhiều bước khi các số rất lớn.

Chương 6 định nghĩa khả nghịch theo nghĩa thứ nhất. Thực tế còn cần nghĩa thứ hai: một biến đổi có thể khả nghịch về nguyên tắc mà vẫn không tháo ngược được trong khoảng thời gian có thể chờ. Mã hóa hiện đại dựa vào chính khoảng cách giữa hai nghĩa này.

B. Tính toán

B1. Liệt kê các ước của 36, 48 và 97. Số nào là số nguyên tố?

Lời giải

36: 1, 2, 3, 4, 6, 9, 12, 18, 36 (9 ước). 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48 (10 ước). 97: chỉ có 1 và 97, vì 97 không chia hết cho 2, 3, 5, 7, mà \(10 \cdot 10 = 100 > 97\) nên không cần thử thêm. Vậy 97 là số nguyên tố.

B2. Phân tích ra thừa số nguyên tố: 84, 126, 1001, 2025.

Lời giải

\(84 = 2^2 \cdot 3 \cdot 7\). \(126 = 2 \cdot 3^2 \cdot 7\). \(1001 = 7 \cdot 11 \cdot 13\). \(2025 = 3^4 \cdot 5^2\) (vì \(2025 = 45 \cdot 45\) và \(45 = 3^2 \cdot 5\)).

B3. Dùng thuật toán Euclid tìm ước chung lớn nhất, rồi tìm bội chung nhỏ nhất: (a) 126 và 84; (b) 1071 và 462.

Lời giải

(a) \(126 = 84 \cdot 1 + 42\), \(84 = 42 \cdot 2 + 0\). Vậy \(\text{ƯCLN}(126; 84) = 42\) và \(\text{BCNN} = 126 \cdot 84 : 42 = 252\).

(b) \(1071 = 462 \cdot 2 + 147\), \(462 = 147 \cdot 3 + 21\), \(147 = 21 \cdot 7 + 0\). Vậy \(\text{ƯCLN}(1071; 462) = 21\) và \(\text{BCNN} = 1071 \cdot 462 : 21 = 23562\).

B4. Mỗi số sau có bao nhiêu ước: 2025, 1000, 97?

Lời giải

\(2025 = 3^4 \cdot 5^2\): số mũ của 3 chọn từ 0 đến 4 (5 cách), của 5 từ 0 đến 2 (3 cách), nên có \(5 \cdot 3 = 15\) ước. Đây là số lẻ, đúng với việc 2025 là số chính phương.

\(1000 = 2^3 \cdot 5^3\): có \(4 \cdot 4 = 16\) ước. 97 là số nguyên tố: có 2 ước.

B5. Không làm phép chia, cho biết 123456789 có chia hết cho 3 không, cho 9 không. Số 987654 thì sao? Tìm số dư khi chia 987654 cho 9.

Lời giải

Tổng các chữ số của 123456789 là \(1 + 2 + \dots + 9 = 45\), chia hết cho 9 (và do đó cho 3). Vậy 123456789 chia hết cho cả 3 và 9.

Tổng các chữ số của 987654 là \(9 + 8 + 7 + 6 + 5 + 4 = 39\). Vì \(39 = 3 \cdot 13\), số này chia hết cho 3; nhưng \(39 = 9 \cdot 4 + 3\), nên nó không chia hết cho 9, và số dư khi chia 987654 cho 9 là 3.

B6. Tìm các số nguyên tố từ 100 đến 130. Cần thử chia cho những số nguyên tố nào, và vì sao?

Lời giải

Vì \(11 \cdot 11 = 121\) và \(13 \cdot 13 = 169 > 130\), mọi hợp số không quá 130 có một ước nguyên tố không quá 11. Chỉ cần thử 2, 3, 5, 7, 11. Loại các số chẵn, các bội của 3 (tổng chữ số chia hết cho 3), các số tận cùng bằng 5, rồi thử 7 và 11: \(105 = 7 \cdot 15\), \(119 = 7 \cdot 17\), \(121 = 11 \cdot 11\) là hợp số. Còn lại các số nguyên tố: 101, 103, 107, 109, 113, 127.

B7. Không nhân hai số, tìm số dư khi chia \(1234 \cdot 5678\) cho 9. Rồi kiểm tra: \(1234 \cdot 5678 = 7006652\).

Lời giải

\(1234 \equiv 1 + 2 + 3 + 4 = 10 \equiv 1 \pmod 9\) và \(5678 \equiv 5 + 6 + 7 + 8 = 26 \equiv 8 \pmod 9\). Theo Định lý 6, tích đồng dư với \(1 \cdot 8 = 8\).

Kiểm tra: tổng các chữ số của 7006652 là \(7 + 0 + 0 + 6 + 6 + 5 + 2 = 26 \equiv 8 \pmod 9\). Khớp. Cách kiểm tra phép nhân này thường được gọi là phép thử chín (casting out nines).

B8. Dùng phép thử chín cho hai khẳng định sai: (a) \(1234 \cdot 5678 = 7006752\); (b) \(1234 \cdot 5678 = 7006625\). Phép thử bắt được lỗi nào? Vì sao lỗi kia lọt qua?

Lời giải

(a) Tổng các chữ số của 7006752 là 27, đồng dư với 0 theo môđun 9, trong khi tích phải đồng dư với 8. Phép thử bác bỏ được khẳng định này.

(b) 7006625 có tổng các chữ số là 26, đồng dư với 8: phép thử không phát hiện gì, dù khẳng định sai (đáp số đúng là 7006652). Lỗi ở đây là đổi chỗ hai chữ số cuối, mà đổi chỗ không làm thay đổi tổng các chữ số. Đúng như Chương 2: một phép thử khớp không chứng minh được đáp số đúng; nó chỉ không tìm ra lỗi.

B9. Hai bánh răng ăn khớp với nhau, một bánh có 12 răng, bánh kia có 18 răng. Đánh dấu một cặp răng đang chạm nhau. Sau khi quay qua bao nhiêu răng thì cặp răng đánh dấu gặp lại nhau lần đầu? Mỗi bánh đã quay bao nhiêu vòng?

Lời giải

Cặp răng gặp lại khi số răng đã đi qua là bội của cả 12 và 18. Lần đầu là \(\text{BCNN}(12; 18) = 36\) răng. Khi đó bánh 12 răng quay \(36 : 12 = 3\) vòng, bánh 18 răng quay \(36 : 18 = 2\) vòng. (Có thể tính \(\text{ƯCLN}(12; 18) = 6\) và \(\text{BCNN} = 12 \cdot 18 : 6 = 36\).)

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

C1. Chứng minh rằng với mọi số nguyên \(a\), \(b\), \(c\): (a) nếu \(a \mid b\) và \(b \mid c\) thì \(a \mid c\); (b) nếu \(a \mid b\) và \(a \mid c\) thì \(a \mid b + c\) và \(a \mid b - c\).

Lời giải

(a) Viết \(b = ka\) và \(c = mb\). Khi đó \(c = m(ka) = (mk)a\), nên \(a \mid c\). \(\square\)

(b) Đây là trường hợp riêng của Bổ đề 1: viết \(b = ka\), \(c = ma\); khi đó \(b + c = (k + m)a\) và \(b - c = (k - m)a\). \(\square\)

C2. Chứng minh rằng một số tự nhiên chia hết cho 3 khi và chỉ khi tổng các chữ số (trong hệ thập phân) của nó chia hết cho 3.

Lời giải

Vì \(10 = 3 \cdot 3 + 1\), ta có \(10 \equiv 1 \pmod 3\). Theo Định lý 6 áp dụng nhiều lần cho phép nhân, \(10^k \equiv 1^k = 1 \pmod 3\) với mọi \(k\). Một số viết là \(d_k \dots d_1 d_0\) trong hệ thập phân bằng \(d_k \cdot 10^k + \dots + d_1 \cdot 10 + d_0\). Theo Định lý 6 cho cả phép nhân và phép cộng, số ấy đồng dư với \(d_k + \dots + d_1 + d_0\) theo môđun 3. Hai số đồng dư theo môđun 3 có cùng số dư khi chia cho 3, nên số này chia hết cho 3 khi và chỉ khi tổng các chữ số chia hết cho 3. \(\square\)

C3. Trong thế giới số chẵn \(2, 4, 6, 8, \dots\), gọi \(a\) là "ước chẵn" của \(b\) nếu \(b = a \cdot k\) với \(k\) cũng là số chẵn, và gọi một số là "nguyên tố chẵn" nếu không có ước chẵn nào. (a) Chứng minh 2, 6, 18 là nguyên tố chẵn. (b) Chỉ ra rằng bổ đề Euclid hỏng trong thế giới này, và giải thích vì sao điều đó làm tính duy nhất của phân tích hỏng theo.

Lời giải

(a) Một tích của hai số chẵn luôn chia hết cho 4. Các số 2, 6, 18 không chia hết cho 4, nên không số nào trong chúng là tích của hai số chẵn: chúng là nguyên tố chẵn.

(b) Số 6 là nguyên tố chẵn và 6 là "ước chẵn" của \(36 = 2 \cdot 18\), vì \(36 = 6 \cdot 6\) với 6 là số chẵn. Nhưng 6 không là ước chẵn của 2 (vì \(2 = 6 \cdot k\) không có \(k\) chẵn nào), cũng không là ước chẵn của 18 (vì \(18 = 6 \cdot 3\) mà 3 không chẵn, và không \(k\) chẵn nào cho \(6 \cdot k = 18\)). Vậy nguyên tố chẵn 6 chia hết một tích mà không chia hết thừa số nào: bổ đề Euclid hỏng.

Trong chứng minh Định lý 5, bước then chốt là "\(p_1\) chia hết vế phải nên chia hết một \(q_j\)", tức bổ đề Euclid. Khi bổ đề hỏng, ta có \(2 \cdot 18 = 6 \cdot 6\) với 6 không trùng thừa số nào ở vế trái. Còn chứng minh bổ đề Euclid trong \(\mathbb{N}\) lại dựa vào một đẳng thức Bézout dạng \(px + ay = 1\). Thế giới số chẵn không có số 1, và mọi tổng các bội chẵn đều chẵn, nên không có đẳng thức nào như vậy: lập luận không bắt đầu được. \(\square\)

Câu hỏi để ngỏ

Phép chia có dư luôn làm được khi số chia khác 0, và ta đã hiểu khá rõ số nào chia hết cho số nào. Nhưng còn một trường hợp mà mọi định lý trong chương đều né tránh: số chia bằng 0. Vì sao ai cũng nói "không được chia cho 0"? Đó chỉ là một lệnh cấm do người ta đặt ra, hay nếu cố tình cho phép, thì sẽ có điều gì sụp đổ?