Phương trình vô định nghiệm nguyên và ứng dụng

BỘ GIÁO DỤC VÀ ĐÀO TẠO

ĐẠI HỌC ĐÀ NẴNG

LÊ THỊ KIM ÁNH

PHƢƠNG TRÌNH VÔ ĐỊNH NGHIỆM

NGUYÊN VÀ ỨNG DỤNG

Chuyên ngành: Phƣơng pháp toán sơ cấp

Mã số: 60.46.01.13

TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC

Đà nẵng - Năm 2015

Công trình được hoàn thành tại

ĐẠI HỌC ĐÀ NẴNG

Ngƣời hƣớng dẫn khoa học: TS. Nguyễn Ngọc Châu

Phản biện 1: TS. Cao Văn Nuôi

Phản biện 2: GS.TS. Lê Văn Thuyết

Luận văn đã được bảo vệ trước Hội đồng chấm Luận văn

tốt nghiệp thạc sĩ khoa học họp tại Đại học Đà Nẵng vào ngày 12

tháng 12 năm 2015

Có thể tìm hiểu luận văn tại:

- Trung tâm Thông tin-Học liệu, Đại học Đà Nẵng

- Thư viện trường Đại học Sư phạm, Đại học Đà Nẵng

1

MỞ ĐẦU

1. Lý do chọn đề tài

Phương trình vô định (còn gọi là phương trình Diophantus) nói

chung và phương trình vô định nghiệm nguyên nói riêng có một vai

trò quan trọng không những trong đại số mà cả trong toán học và

thực tế, bởi vậy đã được các nhà toán học trên thế giới nghiên cứu từ

rất lâu. Phương trình vô định là phương trình đại số với hệ số nguyên

và số ẩn thường nhiều hơn số phương trình, nghiệm của nó được tìm

trong một tập hợp số nào đó như: số nguyên, số nguyên dương, số

hữu tỉ,… Nhiều phương trình vô định phát biểu rất đơn giản nhưng

đến nay cũng chưa có cách giải hữu hiệu.

Ngay từ thời thượng cổ, các nhà toán học đã quan tâm giải

những phương trình vô định. Chẳng hạn, từ thế kỷ thứ XVII trước

công nguyên, các nhà toán học Ba-bi-lon đã biết giải phương trình x

2

+ y

2

= z

2

(phương trình Pythagore) trong phạm vi số nguyên. Người

đầu tiên nghiên cứu có hệ thống phương trình vô định là nhà toán học

Hy Lạp Diophantus, sống ở thế kỷ thứ III trước công nguyên.

Diophantus đã biết cách giải một số dạng phương trình vô định trong

phạm vi các số hữu tỷ dương.

Nhằm tìm hiểu phương trình vô định và những ứng dụng của nó

trong chương trình toán bậc phổ thông, tôi chọn đề tài: “Phương trình

vô định nghiệm nguyên và ứng dụng” cho luận văn thạc sĩ của mình.

2. Mục đích và nhiệm vụ nghên cứu

- Khảo sát, nghiên cứu sự tồn tại nghiệm của phương trình vô

định.

- Tìm hiểu cách giải phương trình vô định.

- Ứng dụng phương trình vô định để giải một số lớp bài toán.

3. Đối tƣợng và phạm vi nghiên cứu

- Phương trình vô định nghiệm nguyên bậc nhất.

- Phương trình vô định nghiệm nguyên bậc hai, hai ẩn.

- Một số bài toán dân gian.

4. Phƣơng pháp nghiên cứu

2

- Thu thập, tổng hợp, hệ thống các tài liệu có nội dung liên quan

đến đề tài luận văn, đặt biệt là các bài toán dân gian giải được bằng

phương tình vô định.

- Phân tích, nghiên cứu các tài liệu để thực hiện đề tài luận văn.

- Trao đổi, thảo luận, tham khảo ý kiến của người hướng dẫn,

của chuyên gia và của các đồng nghiệp.

5. Bố cục của luận văn

Ngoài phần mở đầu và kết luận, nội dung của luận văn được

chia thành bốn chương:

Chương 1. Kiến thức chuẩn bị

Chương 2. Phương trình vô định bậc nhất

Chương 3. Phương trình vô định bậc hai hai ẩn

Chương 4. Phương trình Pell

CHƢƠNG 1. KIẾN THỨC CHUẨN BỊ

1.1. QUAN HỆ CHIA HẾT TRÊN TẬP CÁC SỐ NGUYÊN

Định nghĩa 1.1. Ta nói rằng số

a 

chia hết cho số

b  ,

b  0

, ký hiệu là

a b

hay

b a

, nếu tồn tại số nguyên q sao cho

a bq 

. Khi đó số b gọi là ước số của a hay a là bội của b, còn

số q gọi là thương của phép chia a cho b. Nếu a không chia hết

cho b ta ký hiệu là b

|

a.

Định lý 1.3. Nếu

a b d ,  

thì tồn tại hai số nguyên p và q

sao cho

ap bq d   .

Bổ đề. Giả sử a, b, q, r là những số thỏa mãn đẳng thức

a bq r   . Khi đó

a b b r , ,    .

Dựa vào bổ đề trên, để tìm ước số chung lớn nhất của hai số

nguyên a và b khác 0, ta chia a cho b (

a b 

). Khi đó

a bq r  

, với

0 .   r b

3

Nếu

r  0

thì dừng lại. Nếu

r  0

ta chia b cho r và nhận

được đẳng thức tương tự

1 1 b rq r   ,

với

0 . 1   r r

Tiếp tục quá

trình trên ta nhận được:

a bq r   ,

1 1 b rq r   ,

1 2 2 r rq r   ,

…,

2 1 ,

k k k k r r q r     1 1 1.

k k k k r r q r     

Vì những số

r,

1

r , …,

,

k

r k 1

r 

tạo thành dãy giảm ngặt những số không âm, nên tồn tại k

để

rk1

 0

. Khi đó đẳng thức sau cũng có thể viết

1 1.

k k k r r q  



Theo Bổ đề, ta có

r r r r r r b a b k k k k k       , , ... , , .

   1 1 2       

Quá trình nêu trên gọi là thuật toán Euclicde.

1.2. QUAN HỆ ĐỒNG DƢ TRÊN TẬP CÁC SỐ NGUYÊN

Định nghĩa 1.3. Cho m là số nguyên dương và a, b là những số

nguyên. Ta nói rằng a đồng dư với b theo modul m, nếu

a b m   ,

và ký hiệu là

a b m  mod .

Trường hợp ngược lại,

ta nói rằng a không đồng dư với b theo modul m và viết

a b 

(mod m).

Định nghĩa 1.4. Cho n là một số nguyên dương. Ký hiệu

 n

là số lượng tất cả các số tự nhiên không lớn hơn n và nguyên tố cùng

nhau với n. Hàm

 n

gọi là hàm Euler.

Định lý 1.7. Nếu

a n , 1  

thì

   1 mod .  

n

a n



1.3. LIÊN PHÂN SỐ

Định nghĩa 1.5. Liên phân số hữu hạn là một biểu thức có dạng

1

2

1

1

1

n

q

q

q







, trong đó

q1  ,

*

i q  ,   i n 2, .

Và được ký hiệu là

q q q 1 1 , , ...,

n .

Bằng thuật toán Euclicde, ta có thể biểu diễn số hữu tỷ

a

b

dưới

4

dạng liên phân số hữu hạn như sau:

1 1 a bq r   ,

1 2 2 b rq r   ,

1 2 3 3 r r q r   , …,

3 2 1 1,

n n n n r r q r       2 1 .

n n n r r q   

Từ đẳng thức đầu tiên ta nhận được

1

1 1

1

1

.

a r

q q

b b b

r

   

Từ đẳng thức thứ hai ta có

2

2 2

1 1 1

2

1

.

b r

q q

r r r

r

   

Suy ra

1

2

1

2

1

1

a

q

b

q

r

r

 



.

Tiếp tục quá trình trên, ta được

1

2

1

.

1

1

n

a

q

b

q

q

 





Định nghĩa 1.6. Cho dãy vô hạn những số nguyên

1 2 q q, , …,

qn, …, với

0, 1. q i i   

Khi đó ta gọi biểu thức

1

2

1

1

1

1

n

q

q

q









là liên phân số vô hạn và ký hiệu

q q q 1 2 , , ..., , ...

n 

; còn những số

1 2 q q , , ...

gọi là những phần tử của liên phân số vô hạn.

Ta có thể biểu diễn số vô tỷ



thành liên phân số như sau

1 1  

1

1

q ;

q

 



 



2 1 2  

1 2

1

q ;

q

 



 



5

…

1

1

1

;

n n n

n n

q

q

 







      

…

Khi đó

  q q q 1 2 , , ..., , ...

n .

Cho liên phân số

  q q q 1 2 , , ..., , ...

n 

. Ta xác định hai dãy

số

Pn

và

Q n n   1, 2, ...

theo công thức sau:

1 2 , P q P P n n n n     1 2 , Q q Q Q n n n n    

trong đó

P Q P q Q 0 0 1 1 1

    1, 0, , 1.

Định lý 1.10. Thương số

n

n

p

Q

biểu diễn giản phân thứ n liên

phân số



, nghĩa là

 1 2 , , ..., .

n

n

n

P

q q q

Q



Định lý 1.11. Với mọi số tự nhiên n, đẳng thức sau đúng

1 1  1 . 

n

P Q Q P n n n n     

1.4. DẠNG TOÀN PHƢƠNG

1.4.1. Các khái niệm liên quan

Định nghĩa 1.10. Dạng toàn phương của hai biến x, y là một

biểu thức có dạng

2 2 ax bxy cy   2 ,

với a, b, c là những số nguyên

không đồng thời bằng 0.

Số

2 D b ac  

được gọi là định thức của dạng toàn phương.

Cho dạng toàn phương

 

2 2 f x y ax bxy cy , 2   

. Ta đổi

biến số x và y bằng những biến



và



theo công thức

x

y

 

 

   

  

(1.1)

trong đó

    , , ,

là những số nguyên.

6

Khi đó

   

2 2

1 1 1 f x y a b c , 2 ,           ,

trong đó

2 2

1 a a b c       2 , 1 b a b b c        ,

2 2

1

c a b c       2 .

Đẳng thức (1.1) gọi là phép biến đổi dạng toàn phương. Số

   gọi là môđun của phép biến đổi (1.1).

Hai dạng toàn phương gọi là tương đương nhau khi từ dạng thứ

nhất chuyển đổi sang dạng thứ hai, cũng như ngược lại đều thông qua

một phép biến đổi với hệ số nguyên.

1.4.2. Biểu diễn số nguyên theo dạng toàn phƣơng

Cho dạng toàn phương

2 2 ax bxy cy   2

và m là một số

nguyên. Nếu tồn tại

0 0 x y , 

sao cho

2 2

0 0 0 0 m ax bx y cy    2 ,

ta nói rằng số nguyên m biểu diễn qua dạng toàn phương

2 2 ax bxy cy   2 .

Nếu

m  0

, giả sử rằng m biểu diễn được theo dạng toàn

phương, tức là

2 2

0 0 0 0 m ax bx y cy    2

, với

0

x ,

0

y

là những số

nguyên tố cùng nhau.

Ta biết rằng khi

0

x ,

0

y

là những số nguyên tố cùng nhau thì tồn

tại hai số nguyên p, q sao cho

px qy 0 0   1.

Dễ tính toán được đẳng thức sau:

 

2 2 mU V b ac    ,

với

 

2 2 U aq bqp cp    2 , V p x b y c q x a y b      0 0 0 0    .

Suy ra nếu số

m  0

biểu diễn qua dạng toàn phương

2 2 ax bxy cy   2

với

0

x x  ,

0

y y 

và

 x y 0 0 , 1  

, thì phải tồn

tại số nguyên V sao cho hiệu bình phương của số đó với định thức

của dạng toàn phương chia hết cho m.

Mệnh đề 1.2. Nếu một số nguyên biểu diễn thông qua một dạng

toàn phương đã cho thì nó cũng biểu diễn thông qua mọi dạng toàn

7

phương khác, mà nó bao hàm bởi dạng toàn phương đã cho.

Định lý 1.12. Nếu m là số nguyên khác 0, mà nó biểu diễn

thông qua dạng toàn phương

2 2 ax bxy cy   2

với

0

x x  ,

0

y y  ,  x y 0 0 , 1  

và định thức D của nó là số dư bình phương

của số V đối với m thì những dạng toàn phương sau tương đương

riêng

2 2 ax bxy cy   2 và

2

2 2 2

V D m V

m

  



  .

CHƢƠNG 2

PHƢƠNG TRÌNH VÔ ĐỊNH BẬC NHẤT

2.1. PHƢƠNG TRÌNH VÔ ĐỊNH

Định nghĩa 2.1. Phương trình vô định (hay còn gọi là phương

trình Diophante) là phương trình có dạng:

F x x x  1 2 , , ..., 0,

n  

n  1, trong đó

F x x x  1 2 , , ...,

n 

là một đa thức của các biến

1 2 , , ..., ; n

x x x

với hệ số nguyên.

Để thuận tiện, từ đây về sau nếu không nói gì khác, thì phương

trình vô định nghiệm nguyên được gọi là phương trình vô định.

2.2. PHƢƠNG TRÌNH VÔ ĐỊNH BẬC NHẤT HAI ẨN

2.2.1. Các định nghĩa và định lý tồn tại nghiệm

Định nghĩa 2.3. Phương trình vô định bậc nhất hai ẩn x, y là

phương trình có dạng

ax by c   (2.1)

trong đó a, b, c là những số nguyên; a, b khác 0.

Định lý 2.1. Điều kiện cần và đủ để phương trình (2.1) có ít

nhất một nghiệm số nguyên là ước số chung lớn nhất của hai số a và

b là ước số của c.

Định lý 2.2. Nếu

 x y 0 0 , 

là một nghiệm nguyên của phương

trình (2.1) thì phương trình có vô số nghiệm nguyên và các nghiệm

8

nguyên

( , ) x y

của nó được cho bởi công thức

0

0

b

x x t

d

a

y y t

d



  



   

, (2.2)

trong đó

t 

và

d a b   , .

2.2.2. Ý nghĩa hình học của phƣơng trình vô định bậc nhất

hai ẩn

2.3. PHƢƠNG PHÁP TÌM NGHIỆM CỦA PHƢƠNG TRÌNH

VÔ ĐỊNH BẬC NHẤT HAI ẨN

Xét phương trình vô định

ax by c   , với

d a b c   , |  . (2.3)

Không mất tính tổng quát, ta có thể xem các hệ số a, b của

phương trình là những số nguyên dương.

2.3.1. Phƣơng pháp dùng thuật toán Euclide

2.3.2. Phƣơng pháp dùng liên phân số

Xét phương trình (2.3) và đặt

1

c dc 

, với

1

c  .

Chia cả hai vế của phương trình (2.3) cho d ta được:

a x b y c 1 1 1   , (2.4)

với

1 1 ,

a b a b

d d

 

và

a b 1 1 , 1   .

Giả sử số hữu tỷ

1

1

a

b

có biểu diễn liên phân số như sau:

 

1

1 2

1

, , ..., n

a

q q q

b

 ,

và

0 1

0 1

, , ...,

n

n

P P P

Q Q Q

là các giản phân của liên phân số này. Theo

Định lý 1.11, ta có:

1 1  1

n

P Q Q P n n n n     

, và

1

1

n

n

a P

b Q

 .

9

Vì

1

1

a

b

và

n

n

P

Q

đều là những phân số tối giản nên

1 1 , a P b Q  

n n

suy ra

1 1 1 1 1 1 1  1 1   

n n

n n

a Q c b P c c  

            

,

nghĩa là

0 1 1 0 1 1  1 , 1   

n n

n n

x Q c y P c       

là một nghiệm riêng

của phương trình (2.4) và là nghiệm riêng của phương trình (2.3).

2.3.3. Phƣơng pháp biến số nguyên

Bây giờ ta sẽ giải ví dụ 2.2 bằng phương pháp biến số nguyên.

Tìm nghiệm nguyên của phương trình:

15 9 6 x y   .

Giải. Ta có

d   15, 9 3, 3 6 

, suy ra phương trình có nghiệm

nguyên. Phương trình đã cho tương đương với:

6 15 2 2

9 3

x x

y x

 

     .

Đặt

2 2

3

x

z



 

. Suy ra

3 2 2 z x   hay

2 3 2 x z   2 3 2

2 2

z z

x z

        .

Đặt

2

2 2

2

z

t t z



    

. Dễ thấy

t z   1, 0 là

một nghiệm riêng của phương trình vừa tìm được.

Từ đó suy ra

x  1

và

y  1

là một riêng nghiệm riêng của

phương trình đã cho.

Vậy nghiệm của phương trình đã cho là:

1 3

1 5

x t

y t

   

   

, t  .

2.3.4. Phƣơng pháp hàm Euler

Định lý 2.4. Cho a và b là hai số nguyên dương, nguyên tố cùng

nhau và c là một số nguyên bất kì. Khi đó phương trình ax + by = c,

có một nghiệm nguyên là:

  1

0

b

x ca

 

 ,

 

0

1

b

a

y c

b





  .