Xem mẫu
- 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 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ệ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 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 ZC
sao 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ọn
n 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/
150
- Tạp chí Epsilon, Số 06, 12/2015
Đặt x D y n C B 0 C , ta chứng minh tồn tại số nguyên dương y đủ lớn thỏa mãn
A:ax C Bx C .mod m/: .2/
Điều này tương đương với
0
A:anyCB C C B.ny C B 0 C / C .mod m/
0
, A:aB C :any C .Bn/y C .BB 0 C C/ 0 .mod m/
y
c:e C by C t 0 .mod m/ .3/
B0C n 0
với c D A:a ; e D a ; b D Bn; t D BB C C . Rõ ràng gcd.e; m/ D gcd.b; m/ D 1:
Đặt f .y/ D ce y C by C t . Bây giờ ta chứng minh bài toán bằng phương pháp quy nạp theo m.
Với m D 1 thì .3/ hiển nhiên đúng. Giả sử m > 1 và bài toán đúng với mọi m0 < m. Gọi p là ước
nguyên tố lớn nhất của m và giả sử m D p k :p1k1 :p2k2 : : : : prkr : Đặt m0 D p k 1 :p1k1 :p2k2 : : : : prkr .
Khi đó, tồn tại số nguyên dương y để
f .y/ 0 .mod m0 /
hay tồn tại số nguyên l sao cho f .y/ D lm0 : Ta chọn
r
Y
0
y D y C z:.p 1/p k 1
.pi 1/piki
i D1
với z là một số nguyên dương. Ta chứng minh tồn tại z sao cho f .y 0 / 0 .mod m/: Ta có
r k r
!
yCz.p 1/p k 1 .pi 1/pi i
Q
Y k
0 k 1
f y D ce i D1 C b y C z.p 1/p .pi 1/pi i C t
i D1
r k r
z.p 1/p k 1 .pi 1/pi i
Q
Y
y
D ce :e iD1 C by C t C zb.p 1/p k 1
.pi 1/piki
i D1
r
Y
.ce y C by C t/ C zb.p 1/p k 1
.pi 1/piki
i D1
r
Y
lm0 C z:nm0 .p 1/ .pi 1/ .mod m/
i D1
r k
z.p 1/p k 1 .pi 1/pi i
Q
(ở trên ta đã sử dụng e iD1 1 .mod m/ theo định lí Euler’s).
Do đó, ta chứng minh
r
Y
lm0 C zbm0 .p 1/ .pi 1/ 0 .mod m/
i D1
có nghiệm nguyên dương z, tức là phương trình
r
Y
l C zb.p 1/ .pi 1/ 0 .mod p/
i D1
151
- Tạp chí Epsilon, Số 06, 12/2015
có nghiệm nguyên dương z.
r
Y
Điều này luôn đúng do đây là phương trình đồng dư tuyến tính và gcd.b.p 1/ .pi 1/; p/ D
i D1
1. Do vậy bước quy nạp được hoàn tất.
Ở trên ta đã chứng minh được tồn tại số nguyên dương y sao cho f .y/ 0 .mod m/ hay tồn tại
x thỏa mãn (2). Chúng ta cần chứng minh có thể chọn y lớn tùy ý thỏa mãn (3). Điều này luôn
thực hiện được vì nếu y thỏa f .y/ 0 .mod m/ thì y C :m: .m/ với 2 ZC cũng thỏa mãn.
Vậy định lí được chứng minh.
Cách 2. Giả sử gcd.B; M / D 1 và C là một số nguyên bất kì. Ta có dãy Aa1 ; Aa2 ; : : : là dãy
tuần hoàn xét theo modulo M . Gọi T là chu kì của dãy, tức là T là số nguyên dương nhỏ nhất
sao cho
A:axCkT A:ax .mod M /
với mọi x đủ lớn.
Đặt d D gcd.T; M /. Trước hết ta chứng minh d < M với M > 1.
Vì d jM nên d M . Giả sử d D M , khi đó M jT nên M T . Tuy nhiên, T là chu kì của dãy
Aai khi xét theo modulo M nên T M , do đó T D M . Suy ra tồn tại số nguyên dương X sao
cho A:aX 0 .mod M / và như vậy A:ax 0 .mod M / với mọi x X. Dẫn đến T D 1, nên
M D 1.
Tiếp theo ta chứng minh bài toán bằng phương pháp quy nạp theo M .
Với M D 1 là trường hợp tầm thường. Ta xét M > 1 và giả sử bài toán đúng với mọi m < M ,
dẫn đến bài toán cũng đúng với d . Tức là, tồn tại số nguyên dương x sao cho
A:ax C Bx C .mod d /
hay A:ax C Bx D C C ld với l là số nguyên. Đặt x 0 D x C kT với k là số nguyên dương. Ta có
0
A:ax C Bx 0 D A:axCkT C B.x C kT /
.A:ax C Bx/ C kBT
D C C ld C kBT .mod M /:
Tiếp theo ta chứng minh phương trình đồng dư
ld C kBT 0 .mod M /
có nghiệm nguyên dương k. Chia hai vế của phương trình đồng dư trên cho d ta được phương
trình
T M
l C kB 0 .mod /
d d
T M
Phương trình này luôn có nghiệm nguyên dương k vì gcd B ; D 1:
d d
Vậy bài toán được chứng minh.
152
nguon tai.lieu . vn
