[THCS 6 Elite] Number Theory Lab · UCLN tuyến tính & bài toán số abcde
Số học nâng cao THCS: dùng tổ hợp nguyên để khử tham số trong ƯCLN, tách số thành khối theo giá trị hàng và chuyển điều kiện nguyên thành chia hết; có chứng…
TOÁN 6 NÂNG CAO · CHIA HẾT VÀ LẬP LUẬN
Tạo một số nhỏ để khóa một bài toán lớn
Muốn tìm ước chung của hai biểu thức có tham số, không nhất thiết phải biết từng giá trị. Muốn tìm một số năm chữ số, cũng không nhất thiết phải thử từng số. Ta sẽ học cách giữ lại điều kiện chia hết quan trọng và loại phần biến thiên.
Mục tiêu: giải thích vì sao ước chung chia mọi tổ hợp nguyên; chọn hệ số để khử tham số; tách số theo giá trị hàng; biến điều kiện nguyên thành điều kiện ước số và chứng minh đã tìm đủ nghiệm.
Cần biết trước: ước, bội, ƯCLN, phân tích thừa số nguyên tố, tính phân phối và cách viết số trong hệ thập phân. Nội dung giữ mức nâng cao nhưng chỉ dùng các lập luận chia hết cơ bản.
01 · ƯỚC CHUNG ĐƯỢC GIỮ LẠI NHƯ THẾ NÀO?
Ước chung cũng chia được hiệu của hai bội
Giả sử số nguyên dương d chia cả hai số nguyên A,B. Khi đó tồn tại các số nguyên r,s sao cho A=dr, B=ds. Với mọi số nguyên p,q, ta có:
pA+qB=d(pr+qs).
Vì pr+qs là số nguyên, d chia pA+qB. Hệ số âm hoàn toàn được phép: lấy hiệu của hai bội vẫn được một bội.
Điểm mấu chốt: nếu tìm được pA+qB=1, mọi ước chung dương phải chia 1, nên ƯCLN(A,B)=1. Không cần liệt kê ước của từng biểu thức.
Trong bài này, với các số nguyên có thể âm, ƯCLN được hiểu là ƯCLN của các giá trị tuyệt đối, luôn không âm; các cặp sử dụng ở đây không đồng thời bằng 0. Khi nói “ước chung” trong chứng minh, ta xét ước dương.
Vì sao thuật toán Euclid cũng dùng ý tưởng này?
Nếu A=qB+r, mọi ước chung của A,B chia r=A-qB. Ngược lại, mọi ước chung của B,r chia A=qB+r. Hai chiều cho thấy hai cặp có đúng cùng tập ước chung, nên ƯCLN(A,B)= ƯCLN(B,r).
Phân biệt hai kết luận: “ước chung phải chia một số C” chỉ cho biết ƯCLN là một ước của C. Nó chưa cho biết ƯCLN bằng C. Trường hợp C=1 đặc biệt vì 1 chỉ có một ước dương.
02 · KHỬ THAM SỐ BẰNG HỆ SỐ ĐƯỢC CHỌN
Tại sao lại nghĩ đến 3A − 5B?
Xét A=25n+7, B=15n+4 với n\in\mathbb Z. Ta muốn xóa phần chứa n để mọi ước chung bị ràng buộc bởi một số cố định.
Hai hệ số 25 và 15 có bội chung nhỏ nhất là 75. Nhân A với 3 và B với 5 sẽ tạo cùng phần 75n. Lấy hiệu:
\begin{aligned}3A-5B&=3(25n+7)-5(15n+4)\\&=(75n+21)-(75n+20)=1.\end{aligned}
Nếu d là ước chung dương của A,B, thì d\mid1, do đó d=1. Vì 1 luôn chia mọi số nguyên, suy ra ƯCLN(25n+7,15n+4)=1 với mọi n\in\mathbb Z.
Sơ đồ thể hiện một phép khử đại số, không biểu diễn kích thước hay số lượng theo tỉ lệ.
Kĩ năng nhận diện: khi hai biểu thức đều bậc nhất theo cùng tham số, nhìn hệ số của tham số trước. Tạo hai hệ số bằng nhau rồi trừ; các hằng số còn lại quyết định bước tiếp theo.
Nếu hiệu không bằng 1 thì làm gì?
Với A=2n+1, B=2n+3, ta có B-A=2. Vì vậy ƯCLN chỉ có thể là 1 hoặc 2. Nhưng cả hai biểu thức đều lẻ, nên 2 không chia được chúng; ƯCLN vẫn là 1.
Ví dụ này cho thấy cần lọc các ước của số cố định , không được dừng ở kết luận sai “hiệu bằng 2 nên ƯCLN bằng 2”. Nếu phép khử cho 0, điều kiện “ước chung chia 0” không tạo giới hạn hữu ích, vì mọi số nguyên dương đều chia 0.
Tự kiểm tra: vì sao thử nhiều giá trị n chưa thay thế chứng minh?
Thử n=0,1,2 chỉ xác nhận ba trường hợp. Đẳng thức 3A-5B=1 đúng với mọi số nguyên n, nên cùng một lập luận bao quát tất cả. Thử số hữu ích để phát hiện sai hoặc kiểm lại phép tính, nhưng không chứng minh được mệnh đề với vô hạn giá trị.
03 · CHỮ SỐ LÀ GIÁ TRỊ HÀNG, KHÔNG PHẢI PHÉP NHÂN
Tách một số thành hai khối
Kí hiệu \overline{abcde} là số năm chữ số có các chữ số a,b,c,d,e. Dấu gạch trên phân biệt số ghép chữ số với tích abcde. Đặt A=\overline{ab}, B=\overline{cde}. Vì ba vị trí cuối chiếm các hàng trăm, chục và đơn vị:
\overline{abcde}=1000A+B.
Ta có 10\le A\le99 và 0\le B\le999, cả hai đều nguyên. Khối cuối có ba vị trí chữ số , nhưng giá trị của nó có thể nhỏ hơn 100: chẳng hạn khối 007 có giá trị 7. Vì vậy không tự gọi B là “một số có ba chữ số” nếu đề không yêu cầu c\ne0.
Quy tắc tổng quát: nếu khối bên phải có r vị trí thì số ghép bằng 10^rA+B, với 0\le B\lt10^r. Hệ số phụ thuộc độ dài khối bên phải, không phụ thuộc độ lớn hiện tại của B.
Chẳng hạn A=13, B=7 trong một khối ba vị trí tạo số 13007=1000\cdot13+7, không phải 137. Giữ độ dài khối giúp tránh mất các chữ số 0 ở đầu khối sau.
04 · TỪ PHƯƠNG TRÌNH ĐẾN ĐIỀU KIỆN CHIA HẾT
Phần nguyên cộng một phân số tạo ra bộ lọc
Ta xét các số năm chữ số thỏa \overline{abcde}=2\,\overline{ab}\,\overline{cde}. Mục đích không chỉ tìm đáp số, mà học cách giảm một miền thử rất lớn xuống vài ước số.
Dùng hai khối ở trên, điều kiện trở thành 1000A+B=2AB. Chuyển các số hạng chứa B về cùng phía:
B(2A-1)=1000A.
Vì A\ge10 nên 2A-1\ge19>0, được phép chia. Để nhìn rõ khi nào B nguyên, viết 1000A=500(2A-1)+500:
B=\frac{1000A}{2A-1}=500+\frac{500}{2A-1}.
Số 500 đã nguyên, nên B nguyên khi và chỉ khi 2A-1 là một ước của 500. Đây là bước đổi câu hỏi: thay vì “thử từng số ghép”, hỏi “mẫu số nào chia hết tử số cố định?”.
Dấu hiệu nên tách thương: tử số và mẫu số đều bậc nhất theo cùng biến. Viết tử bằng một bội của mẫu cộng số dư hằng giúp điều kiện nguyên trở thành một điều kiện chia hết dễ kiểm soát.
Đừng bỏ điều kiện chữ số: tìm được một ước của 500 mới chỉ là ứng viên. Còn phải kiểm tra nó có dạng 2A-1, có đúng khoảng của A, và tạo được B trong miền 0\ldots999 hay không.
05 · LỌC NHANH NHƯNG KHÔNG BỎ SÓT
Khoảng, tính lẻ và thừa số nguyên tố cùng làm việc
Từ 10\le A\le99 suy ra 19\le2A-1\le197. Ngoài ra, 2A-1 luôn lẻ. Phân tích 500=2^2\cdot5^3, ta thấy một ước dương lẻ không chứa thừa số 2, nên chỉ có thể là:
1,\quad5,\quad25,\quad125.
Hai ước 1,5 nhỏ hơn 19, bị loại. Còn lại 25,125 đều nằm trong khoảng cho phép:
Mẫu số 25
2A-1=25 cho A=13; B=500+500/25=520. Số ghép là 13520.
Mẫu số 125
2A-1=125 cho A=63; B=500+500/125=504. Số ghép là 63504.
Cả hai khối B đều là số nguyên trong 0\ldots999. Kiểm tra trực tiếp: 2\cdot13\cdot520=13520 và 2\cdot63\cdot504=63504.
Vì sao đã đủ nghiệm?
- Mọi nghiệm ban đầu phải cho một số D=2A-1 là ước dương lẻ của 500 trong [19,197].
- Danh sách các ước lẻ được suy ra đầy đủ từ phân tích thừa số nguyên tố; trong khoảng chỉ có 25,125.
- Mỗi ứng viên xác định duy nhất A=(D+1)/2 và B=500+500/D; các giá trị này đã qua điều kiện chữ số và phép thử gốc.
Vì vậy có đúng hai số 13520 và 63504. Ta không chỉ chứng minh “chúng là nghiệm” mà còn chứng minh “không có nghiệm khác”.
Thử hữu hạn vẫn có vai trò: một chương trình duyệt A=10,\ldots,99 có thể kiểm tra độc lập danh sách nghiệm. Phép duyệt đầy đủ có thể xác nhận một miền hữu hạn; lập luận chia hết còn giải thích tại sao chỉ còn hai ứng viên và giúp giải những bài cùng cấu trúc.
06 · LIÊN KẾT HAI PHƯƠNG PHÁP
Đều tạo ra một ràng buộc nhỏ không còn tham số lớn
Ở bài ƯCLN, tổ hợp 3A-5B=1 xóa tham số n và khóa mọi ước chung vào các ước của 1. Ở bài chữ số, phép tách thương làm 2A-1 phải chia số cố định 500. Một bài dùng khử bằng tổ hợp nguyên , bài kia dùng điều kiện nguyên của thương ; cả hai đều tìm một giới hạn nhỏ trước khi tính chi tiết.
Khi gặp ƯCLN có tham số
Thử hiệu hoặc tổ hợp để khử tham số. Nếu còn hằng số khác 0, liệt kê các ước có thể rồi kiểm tra lại điều kiện.
Khi gặp số ghép chữ số
Tách khối với đúng lũy thừa của 10. Ghi miền của từng khối rồi đưa điều kiện về thương nguyên hoặc chia hết.
Tự kiểm tra bằng một biến đổi nhỏ
1. Nếu một tổ hợp cho 6, có được kết luận ƯCLN bằng 6 không?
Không. Chỉ biết ƯCLN thuộc \{1,2,3,6\}. Cần kiểm tra ước nào thực sự chia cả hai số. Ví dụ A=5, B=11 có B-A=6 nhưng ƯCLN bằng 1.
2. Trong bài chữ số, vì sao không xét ước 20 của 500?
Vì D=2A-1 phải lẻ. Dù 20 là ước của 500 và nằm trong khoảng [19,197], nó cho A=(20+1)/2=10{,}5, không phải số nguyên hai chữ số. Các bộ lọc phải được dùng đồng thời.
3. Nếu khối cuối có hai vị trí, hệ số 1000 còn đúng không?
Không. Khi khối bên phải có hai vị trí, số ghép là 100A+B, với 0\le B\le99. Đây là thay đổi cấu trúc giá trị hàng, nên phải lập lại phương trình; không thể giữ các hằng số của bài ba vị trí.
Thói quen quan trọng: sau một biến đổi thông minh, luôn hỏi “đây là điều kiện cần hay đã tương đương?”, “đã giữ miền của biến chưa?” và “lập luận nào loại hết các trường hợp còn lại?”. Chính ba câu hỏi ấy biến mẹo giải nhanh thành một chứng minh.
Ước chung trong lập luận là ước dương; các biến chữ số và khối số đều nguyên. Các mục tự kiểm tra mở được bằng bàn phím.