www.laisac.page.tl

M M MỘ Ộ ỘT T T S S SỐ Ố Ố B B BÀ À ÀI I I T T TO O OÁ Á ÁN N N S S SỐ Ố Ố H H HỌ Ọ ỌC C C T T TR R RO O ON N NG G G C C CÁ Á ÁC C C K K KÌ Ì Ì T T TH H HI I I  O O OL L LY Y YM M MP P PI I IC C C T T TO O OÁ Á ÁN N N

Trần Xuân Đáng – Nam Định

Trong kỳ thi Olympic toán Quốc tế lần thứ 49 được tổ chức tại Tây Ban Nha có bài toán

sau (bài toán 1) mà tác giả của nó là Kestutis Cesnavicius (Lithuania) (Litva).

Bài toán 1: Chứng minh rằng tồn tại vô số số nguyên dương n sao cho

n +  có ước

2  1

nguyên tố lớn hơn  2

n

+

2

n

Bài toán này là bài toán khó nhất của ngày thi thứ nhất. Lời giải của bài toán 1 được phát

triển từ lời giải của các bài toán đơn giản hơn sau đây:

Bài toán 2: Chứng minh rằng tồn tại vô số số nguyên dương n sao cho n 2 + 1 không là ước

của n!.(Đề thi chọn đội tuyển của Inđônêxia dự thi Toán Quốc tế năm 2009) .

Lời giải của bài toán 2:  Bổ đề: Tồn tại vô số số nguyên tố dạng 4k + 1 (k ˛ N * )  Chứng minh: Gọi A là tập hợp gồm tất các số nguyên tố dạng 4k+1           (k ˛N * ) , Khi đó

A „ rỗng  vì 5 ˛ A. Giả sử A là tập hữu hạn. Gọi p0 là phân tử lớn nhất của A (cid:222) p0 ‡ 5 .

Giả sử p1, p2 … pn là tất cả các số nguyên tố nhỏ hơn p0.

đặt

a

=

4

...

+  khi đ? a ˛ N * , a > 1. Giả sử q là ước nguyên tố  của a

1

2 2 p p 0 1

2  p n

(cid:222) q „ pi , " i ˛ {0,1,2 …, n}. Mặt khác (2p0p1… pn) 2 + 1 ” 0 (modq)

(cid:222) ­ 1 là số chính phương (modq) và q lẻ.

q

”

1  (mod

) 4

(cid:222)

1

(  - (cid:222)

=

1

(cid:222)

1 -  q 2  ) 1

1  :

2

(cid:222)

q

- 2

(cid:230) - (cid:246) 1  (cid:231) (cid:231) (cid:247) (cid:247) = q  Ł ł

Suy ra q có dạng 4k + 1 (k ˛ N * ). Mặt khác

- p  1 2

=

- (

) 1

=

1

- (cid:222)

1

q> p0. Điều này mâu thuẫn với cách chọn p0. Vậy tồn tại vô số số nguyên tố dạng  4k + 1  (k˛ N * ).  Chúng ta chuyển sang việc giải bài toán 2. Giả sử p là số nguyên tố dạng 4k + 1 (k ˛ N * )

(cid:222)

(cid:230) - (cid:246) 1  (cid:231) (cid:231) (cid:247) (cid:247) p  Ł ł

2

- ”

1  (mod

p  )

(cid:222)

(cid:222) $ np ˛  { 0,1,2 …. ,p ­ 1} sao cho

2  p n

p n  +1: p và np! không chia hết cho p fi

2

2

1 - p

là số chính phương (modp)

p n  + 1. Ta có:

p n  + 1 ‡  p (cid:222) np ‡

. Vì tồn tại vô số số nguyên tố p np ! không chia hết cho

dạng 4k + 1 (k˛ N * ) nên tồn tại vô số số nguyên dương n sao cho n 2  + 1 không là ước của n!

Bài toán 3:  Chứng minh rằng tồn tại vô số số nguyên dương n sao cho ước nguyên tố lớn

nhất của n 2  + 1 lớn hơn 2n

- p  1 2

- (

) 1

=

1

- (cid:222)

1

(Tạp chí  Animath của Pháp năm 2006)  Lời giải của bài toán 3:  Giả sử p là số nguyên tố dạng 4k + 1 (k ˛ N * )

(cid:230) - (cid:246) 1  (cid:231) (cid:231) (cid:247) (cid:247) = p  Ł ł

(cid:222) $ x ˛  {0,1,2, … ,p ­ 1} sao cho x 2 ”  ­ 1(modp).  Ta có: q 2 ”  (p­ q) 2 (modp)  (q ˛ Z)

Suy ra là số chính phương (modp)

(cid:222) $ q ˛  {0,1,2, …,

1 - p  2

} sao cho q 2 ” ­1 (modp).

1 - p  2

1 + p  2

Thật vậy giả sử . Đặt q = p – x, ta có: < x < p (cid:222) x ‡

1 - p  2  p ‡ 2q +1 > 2q. Suy ra ước nguyên tố lớn nhất của q 2 +1 lớn hơn 2q.Vì có vô số số nguyên tố  dạng 4k + 1(k ˛ N * ) nên tồn tại vô số số nguyên dương n sao cho n 2 +1  có ước nguyên tố lớn

q 2 = ( p – x) 2 ”  x 2 ”  ­ 1 (modp) và 0 < q £ . Ta có:  q 2 +1 M  p và

hơn 2n.

- p  1 2

- (

) 1

=

1

- (cid:222)

1

Sau đây là các lời giải của bài toán 1  Lời giải thứ nhất của bài toán 1: Xét số nguyên tố p dạng 4k + 1 (k ˛ N * )

(cid:222)

(cid:230) - (cid:246) 1  (cid:231) (cid:231) (cid:247) (cid:247) = p  Ł ł

(cid:222) $ x ˛  {0,1,2, … p ­ 1} sao cho x 2 ”  ­ 1(modp).

là số chính phương (modp)

1 - p  2

p

-

a

} sao cho Vì x 2 ”  (p­ x) 2 (modp) (x ˛ Z) (cid:222) $ x ˛  {0,1,2 … ,

1 - p  2

1  - 2

(cid:230) (cid:231) Ł

(cid:246) 2 ” ­1 (modp)  (cid:247) ł

p

-

a

} sao cho x 2 ” ­1 (modp). (cid:222) $ a ˛  {0,1,2, … ,

(cid:222) m ˛  {0,1,2, …,

1 - p  2

1  - 2

(cid:230) (cid:231) Ł

(cid:246) (cid:247) ł

4 p

1

-

3

4 p

1

-

1

(cid:222)

(cid:222)

Đặt m = } và m 2 ” ­1 (modp)

+  4

+  2

Giả sử p > 20. N?u 0 £ a £ 0 < 2a +1 £

(2a +1) 2 

4 p

1

-

3

1 - p

(cid:222)

+  4

Vậy a  > p > 2m  +  m 2 . Vì . Vì m 2 +1 M  p nên m 2 ‡ p ­1 (cid:222) m ‡

tồn tại vô số số nguyên tố p dạng 4k + 1 (k ˛ N * ) nên tồn tại vô số số nguyên dương n sao cho

ước nguyên tố lớn nhất của n 2  + 1 lớn hơn  2

n

+

2

n .

Lời giải thứ 2 của bài toán 1: Giả sử n là số nguyên, n ‡ 24. Giả sử p là ước nguyên tố

p  2  Khi đ? 0 < x< p – x < p. Ta c? x 2 + 1 chia hết cho p. Thật vậy tồn tại m˛  Z sao cho n! = mp + x  hoặc – n! = mp + x. Trong cả hai trường hợp ta đều có (n!) 2 +1 = (mp+x) 2 +1 (cid:222)  x 2 +1 = (n!) 2 +  1 – m 2 p 2 – 2mpx (cid:222) x 2 +1Mp . Từ đó suy ra p là ước của p 2 ­ 2px + 4x 2 + 4 = (p – 2x) 2 + 4

4 - p

(cid:222) p £  (p – 2x) 2 + 4 (cid:222) p ‡  2x +

4 - p

của  (n!) 2 + 1. Hiển nhiên p > n. Giả sử  x ˛(0, ) là số dư trong phép chia n ! hoặc – n! cho p.

(cid:222) p ­ 4 ‡  2x +

4 - p

­ 4 ‡  2x +  20  – 4> 2x

x 2  Từ đây suy ra điều phải chứng minh

(cid:222)  p ‡  2x +

> 2x +

Bài toán sau là bài toán tổng quát của bài toán 1  Bài toán 4: Chứng minh rằng tồn tại vô số số nguyên dương n sao cho n 2 + 1 có ước

nguyên tố lớn hơn 2n + 2  n

7

+

=

n  2

Bài toán 5: Chứng minh rằng với mỗi số nguyên n ‡ 3, tồn tại cặp số nguyên dương lẻ (xn,

2 x  n

2  y  n

yn) sao cho

(Đề thi Olympic Toán của Bungari năm 1996)

7

+

=

n  2

Lời giải: Với n = 3 , chọn x3 = y3 = 1

2 x  n

2  y  n

. Ta chứng Giả sử với n ‡ 3 , tồn tại cặp số nguyên dương lẻ (xn,yn) sao cho

7

7

y  n

x n

y  n

+ 1

x n

y  n

y  n

7

2  X

+

2  Y

=

n  2

Y  ,

=

Y  ,

=

minh rằng mỗi cặp .

+  2

- x  n  2

-  2

+ x  n  2

7

y  n

y  n

+

(X= ) , (X= ) thoả măn

2 7  x +  n

2  y  n

m  x  n  2

x  (cid:230) –  n  7 (cid:231) 2  Ł

2  (cid:246) (cid:247) ł

(cid:230) (cid:231) Ł

2  (cid:246) = 2 (  (cid:247) ł

x  n

y  n

(cid:222)

=

k

l  +

+

1

Thật vậy ) = 2. 2 n = 2 n+1

+ 2

-

-

x  n

y  n

x  n

y  n

x n

y  n

=

k

- l

,

Vì xn , yn lẻ nên xn = 2k + 1, yn = 2l + 1 (k, l ˛  Z)

2

+  2

2

+1

7

+

=

n  2

và . Điều đó chứng tỏ rằng một trong các số là lẻ . Vì vậy

2  x  +  1 n

2  y  + 1  n

với n +1 tồn tại các số tự nhiên lẻ xn+1 và yn+1 thoả măn

Bài toán 6 : Chứng minh rằng với mỗi số nguyên dương n, phương trình x 2  + 15y 2 = 4 n có

ít nhất n nghiệm tự nhiên (x,y)

(Đề thi chọn học sinh giỏi Toán Quốc gia năm học 2009 – 2010)

+

=

n  4

Lời giải: Trước hết ta chứng minh rằng với mỗi số nguyên n ‡ 2 tồn tại cặp số nguyên

2 x  n

15  2  y  n

dương lẻ (xn , yn) sao cho sao cho

+

=

n  4

Thật vậy với n = 2 , chọn x2 = 1 , y2  = 1

2 x  n

15  2  y  n

. Giả sử  với n ‡ 2  tồn tại cặp số nguyên dương lẻ (xn , yn) sao cho sao cho

15

-

-

15

x  n

y  n

x  n

+ 1

x  n

y  n

x  n

2  X

+

2  Y  15

=

n  4

Y  ,

=

Y  ,

=

Ta chứng minh rằng mỗi cặp

y n  2

+ 2

+  y n  2

2

x  n

y  n

x  n

+

(X= ),  (X= ) thoả măn

2  2  15  n  x +  y  n

y  m  n  2

– 2

15 (cid:230)  (cid:231) Ł

2  (cid:246) (cid:247) ł

(cid:230) 15  (cid:231) Ł

2  (cid:246) (cid:247) ł

x  n

y  n

(cid:222)

=

k

l  +

+

1

Thật vậy = 4 ( ) = 4. 4 n = 4 n+1

+ 2

2 (  l

+

) 1

2 (  k

+

) 1

y  n

x  n

=

=

l

-

k

Và xn , yn lẻ nên xn = 2k + 1, yn = 2l + 1 (k, l ˛  Z)

-  2

- 2

y  n

x  n

y  n

x n

,

và . Điều đó chứng tỏ rằng một trong các số

+  2

- 2

+

1

+

15

=

n  4

2  x  n  +

1

2  y  n  +

1

là lẻ . Vì vậy với n +1 tồn tại các số tự nhiên lẻ xn+1 và yn+1 thoả măn

2 x

+

15  2  y

=

Trở lại bài toán 6:

n  có 1 nghiệm tự nhiên là (x,y)  = (2,0)  4

2 x

+

15  2  y

=

Với n = 1, phương tŕnh

n  có 2 nghiệm tự nhiên là (x,y)= (4,0); (1,1)  4

2 x

+

15  2  y

=

Với n = 2, phương tŕnh

n  có n nghiệm tự nhiên là (x1,y1), (x2,y2), …, (xn, yn)  4

2 x

+

15  2  y

=

n  4

+1 .

Giả sử với n ‡  2, phương tŕnh

2 x

+

15  2  y

=

n  4

khi đó (x,y) = ( 2xk, 2yk) (1 £  k £  n) là các nghiệm tự nhiên của phương trình

+1 lại có 1 nghiệm tự nhiên lẻ. Vậy phương

2 x

+

15  2  y

=

n  4

Theo chứng minh trên phương trình

+1 có ít nhất n+1 nghiệm tự nhiên. Bài toán 6 đă được giải quyết.

tŕnh

2  x x

+  -

2  y  y

Bài toán 7: Tìm tất cả các cặp số nguyên dương (x,y) sao cho là số nguyên và là

ước của 1995.(Đề thi Olympic toán Bungari năm 1995)

Lời giải : Trước hết ta chứng minh  Bổ đề: Cho số nguyên tố p = 4q + 3 (q ˛  N). Giả sử x, y là các số nguyên sao cho x 2 + y 2

chia hết cho p, Khi đó x và y chia hết cho p. Thật vậy nếu x Mp thì y Mp .

Giả sử x không chia hết p (cid:222) y không chia hết cho p

Theo định lý nhỏ Phecma ta có x p­1 ” 1 (modp) (cid:222) x 4q+2 ” 1 (modp). Tương tự  y 4q+2 ” 1

(cid:222) (x 2 ) 2q+1 ”  (­y 2 ) 2q+1 (modp) (cid:222)  x 4q+2 ”  ­ y 4q+2 (modp) (cid:222)  1 ”  ­ 1 ( modp) (cid:222)  p = 2 (vô

(modp) . Ta có x 2 + y 2 Mp (cid:222) x 2 ”  ­y 2 (modp)

lí). Bổ đề đã được chứng minh.

Áp dụng bổ đề vào bài toán 7: Giả sử tồn tại các số nguyên dương x,y sao cho x> y ,

2  x x

+  -

2  y  y

2  x x

+  -

2  y  y

2  x x

+  -

2  y  y

-

=

+

là số nguyên và là ước của 1995 . Đặt k = thì    x 2 +y 2 = k( x –y) và k là

k  x  (  1  1

2  y  1

2  x 1

. N?u k = 1 thì  )  y  1

ước của 1995  = 3.5.7.19.N?u k M3 th́ k= 3 k1 (k1 ˛N * ) (k1 không chia hết cho 3) (cid:222)  x 2 + y 2  M3 (cid:222) x M3 và y M3 (cid:222) x = 3x1 , y = 3y1 (x1 , y1 ˛N * , x1 > y1) (cid:222)  x 2 + y 2 = x – y  . Đó là điều vô lí vì x 2 + y 2 ‡  x + y  > x – y (vì x,y ‡ 1 )

Nếu k = 5 thì x 2 + y 2 = 5(x – y) (cid:222) (2x ­ 5) 2 + (2y +5) 2 = 50 (cid:222)  x = 3 , y = 1 hoặc x = 2 , y

= 1

+

=

-

Nếu k = 7 , tương tự như trên, tồn tại k2˛N * sao cho k = 7 k2  (k2  không chia hết cho 7)  x

2  x 2

2  y  2

k  x  (  2  2

y  )  2

= 7x2 , y = 7y2  (x2, y2 ˛N * , x2 > y2) và

+

=

-

Nếu k M19 thì tồn tại k3 ˛N * sao cho k = 19k3 (k3 không chia hết cho 19 ),    x = 19x3 , y =

2  x 3

2  y  3

k  x  (  3  3

y  )  3

19y3  (x3, y3 ˛N * , x3 > y3 ) và

Vậy tất cả các cặp số nguyên dương (x,y) cần tìm có dạng (3c, c), (2c, c), (c, 2c), (c, 3c)

trong đó c ˛  {1,3,7,19,21,57,133,399} .

2  x x

+  -

2  y  y

Bài toán 8: Tìm tất cả các cặp số nguyên dương (x,y) sao cho số  A = là số

nguyên và là ước của 2010.

(Đề thi Olympic Toán khu vực duyên hải đồng bằng Bắc Bộ năm học 2009 – 2010)

2  x

+

2  y

=

k  (  x

-

y  )

Lời giải: Trên cơ sở lời giải của bài toán 7 ta chỉ cần tìm các nghiệm nguyên dương của

các phương trình : với k ˛  { 2,5, 10}. Phương tŕnh  x 2 + y 2 = 2 (x­ y) không có

nghiệm  nguyên dương . Thật vậy giả sử x,y ˛N * , x > y  và x 2 + y 2 = 2 (x­ y) (cid:222)  x 2 + y 2 ‡  2x  +y 2 > 2(x – y). Đó là điều vô lý . Phương trình x 2 + y 2 = 5 (x­ y)   có các nghiệm nguyên dương  là (x,y) = (3,1), (2,1). Phương trình x 2 + y 2 = 10 (x­ y) (cid:219)  (x­5) 2 + (y+5) 2 = 50 có các nghiệm

nguyên dương là (x,y) = (6,2) ; (4,2) .

Vậy tất cả các cặp số nguyên dương (x, y) thoả măn đề bài là  (3c, c), (2c, c), (c, 2c) , (c,

3c) , (6c, 2c) , (4c, 2c) , ( 2c, 6c), (2c, 4c) trong đó

c ˛  {1,3,6,7,201}

Cuối cùng là một số bài toán dành để luyện tập

Bài toán 9: Chứng minh rằng với mỗi số nguyên dương n, phương tŕnh

7x 2 + y 2 = 2 n+2 luôn có nghiệm nguyên dương.

Bài toán 10: Chứng minh rằng với mỗi số nguyên dương n, phương trình x 2  + 15y 2 = 4 n

có đúng n nghiệm tự nhiên .

Bài toán 11: Cho số nguyên dương n. Gọi Sn là tổng các bình phương của các hệ số của đa

thức f(x) = (1+x) n .

Chứng minh rằng S2n+1 không chia hết cho 3

(Đề thi chọn đội tuyển Việt Nam dự thi Olympic Toán Quốc tế năm 2010)

Bài toán 12: Chứng minh rằng tồn tại vô số số nguyên dương n sao cho  2 n +2 chia hết cho n .

Bài toán 13: Chứng minh rằng tồn tại vô số số nguyên dương n sao cho tất cả các ước

nguyên tố của n 2 + n + 1 không lớn hơn  n .

(Đề thi chọn đội tuyển  Ukraina dự thi Olympic toán quốc tế năm 2007)

Bài toán 14: Với mỗi số nguyên dương n > 1, kí hiệu p(n) là ước nguyên tố lớn nhất của

n. Chứng minh rằng tồn tại vô số số nguyên n > 1 sao cho:

p(n) < p(n+1) < p(n+2) .

Bài toán 15: Cho các số nguyên a,b  thoả măn a>b > 0 . Chứng minh rằng tồn tại vô số số

nguyên dương n sao cho a n + b n chia hết cho n .

Bài toán 16: Chứng minh rằng tồn tại vô số số nguyên tố p có tính chất sau: Tồn tại vô số

nguyên dương n sao cho p – 1 không chia hết cho n và n! +1 chia hết cho p.

(Đề thi chọn đội tuyển của Mônđôva dự thi Olympic toán Quốc tế năm 2007).

Bài toán 17: Chứng minh rằng tồn tại vô số số nguyên dương n sao cho    5 n­2 – 1  chia hết

cho n.

(Đề thi Olympic toán của Braxin năm 2008)