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!
Nội dung trích xuất từ tài liệu:
Số dư của Ax + Bx 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ở đầuTrong 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ánnà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ếtcho 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 theomodulo 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ậchai 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 modulop 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 kvớ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ó 2x 02 D x C y:p k D x 2 C2xyp k Cy 2 p 2k D aC.lC2xy/p k Cy 2 p 2k aC.lC2xy/: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ệmnguyê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ạptheo 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 modulom 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 y thay đổi. Nócòn được dùng để chứng minh các vấn đề khác khi chọn những giá trị y thích hợp.Bài toán sau xuất hiện trong kí thi Olympic Brazil năm 2005.Bài toán 1. (Brazil 2005) Cho các số nguyên dương a, b và c. Chứng minh rằng tồn tại một sốnguyên dương x sao cho ax C x b .mod c/:Một trường hợp đặc biệt của bài toán trên xuất hiện trong đề IMO Shortlist năm 2006.Bài toán 2. (IMO Shortlist 2006) Chứng minh rằng với mọi số nguyên dương n luôn tồn tại sốnguyên dương m sao cho n là ước của 2m C m.Một bài toán tương tự đã được đưa ra trong kì thi USA TST năm 2007.Bài toán 3. (USA TST 2007) Tồn tại hay không các số nguyên dương a, b sao cho a không làước của b n n với mọi số nguyên dương n.Tất cả các bài toán được được tổng quát thành bài toán sauĐịnh lý 2. Cho A; a; B là các số nguyên và M là số nguyên dương. Khi đó, điều kiện cần và đủđể với mọi số nguyên C , luôn tồn tại số nguyên dương x sao cho A:ax C Bx C .mod M /là gcd.B; M / D 1:Lưu ý: Ta có thể phát biểu định li trên theo một cách khác là fA:ax C Bx mod mjx 2 ZC g D f0; 1; : : : ; M 1g khi và chỉ khi gcd.M; B/ D 1.Chứng minh. Ta chứng minh điều kiện cần: Giả sử .M; B/ > 1, gọi p là một ước nguyên tốchung của M và B. Khi đó, nếu pjAa thì ta chọn C D 1, ngược lại ta chọn C D 0. Khi đó,phương trình A:ax C Bx C .mod p/ không có nghiệm x.Chứng minh điều kiện đủ: Ta có thể chứng minh theo hai cách sau:Cách 1. Giả sử .B; M / D 1. Gọi C là một số nguyên bất kì và đặt M D mn với m; n 2 ZCsao cho mỗi ước nguyên tố của n là ước của a và gcd.a; m/ D gcd.n; m/ D 1 (điều này cónghĩa là nếu a D p1˛1 :p2˛2 : : : pk˛k :m0 và M D p1ˇ1 :p2ˇ2 : : : pkˇk :m với pi 6 j m0 ; m thì ta chọnn D p1ˇ1 :p2ˇ2 : : : pkˇk ). Khi đó njax với x đủ lớn. Ta có ( x A:ax C Bx C .mod m/ A:a C Bx C .mod M / , : A:ax C Bx C .mod m/Từ .B; n/ D 1, suy ra tồn tại số nguyên dương B 0 sao cho BB 0 1 .mod n/. Khi đó, với x đủlớn thỏa mãn x B 0 C .mod n/ thỏa mãn phương trình A:ax C Bx C .mod n/: .1/ 150Tạp chí Epsilon, Số 06, 12/2015Đặt x D y n C B 0 ...