tailieunhanh - Số dư của Ax + Bx

Nội dung bài viết trình bày một định lí cơ bản về sự tồn tại thặng dư bậc hai. Mặc dù trong bài toán này không cần đến nó, nhưng ý tưởng chứng minh định lí đó có thể áp dụng trong nhiều vấn đề và sẽ sử dụng nó trong suốt bài viết này. Mời các bạn tham khảo! | SỐ DƯ CỦA A ax C Bx Yimin Ge Vienna Áo Người dịch Nguyễn Tất Thu Đồng Nai 1. Mở đầu Trong thời gian gần đây một số vấn đề của lý thuyết số đã trở nên phổ biến trong các kì thi. Cụ thể là vấn đề tìm số dư của ax C bx theo modulo của số nguyên dương m. Trong bài viết này chúng tôi đưa ra bài toán tổng quát cho các bài toán trên. Chúng ta sẽ bắt đầu với một định lí cơ bản về sự tồn tại thặng dư bậc hai. Mặc dù trong bài toán này ta không cần đến nó nhưng ý tưởng chứng minh định lí đó có thể áp dụng trong nhiều vấn đề và chúng tôi sẽ sử dụng nó trong suốt bài viết này. Định lý 1. Cho p là số nguyên tố lẻ k là số nguyên dương và a là một số nguyên không chia hết cho p. Khi đó a là thặng dư bậc hai theo modulo p k khi và chỉ khi a là thặng dư bậc hai theo modulo p. Chứng minh. Ta thấy nếu a là thặng dư bậc hai theo modulo p k thì hiển nhiên a là thặng dư bậc hai theo modulo p. Do đó ta chỉ cần chứng minh a là thặng dư bậc hai theo modulo p k với a là thặng dư bậc hai theo modulo p. Ta chứng minh vấn đề này bằng cách quy nạp theo k. Giả sử a là thặng dư bậc hai theo modulo p k ta chứng minh a là thặng dư bậc hai theo modulo p kC1 . Thật vậy Vì a là thặng dư bậc hai theo modulo p k nên tồn tại số tự nhiên x sao cho x2 a .mod p k hay là tồn tại số nguyên l sao cho x 2 D a C l p k với x không chia hết cho p. Đặt x 0 D x C y p k với y là một số nguyên. Ta chứng minh tồn tại số nguyên y sao cho x 02 a .mod p kC1 Ta có 2 x 02 D x C y p k D x 2 C2xyp k Cy 2 p 2k D p k Cy 2 p 2k p k .mod p kC1 Ta chứng minh tồn tại y sao cho l C 2xy 0 .mod p Rõ ràng đây là phương trình đồng dư tuyến tính và .2x p D 1 nên phương trình luôn có nghiệm nguyên y. Vây định lí được chứng minh. 149 Tạp chí Epsilon Số 06 12 2015 Ý tưởng quan trọng trong chứng minh trên là một kĩ thuật rất hữu ích Sử dụng giả thiết quy nạp theo modulo m ta xây dựng một nghiệm mới x 0 theo modulo m0 dựa vào nghiệm x theo modulo m bằng cách thêm vào biến mới y. Chú ý rằng x 0 vẫn bất biến theo modulo m khi