ĐỌC VUI VÀ SUY NGHĨ

Cổ vũ lòng yêu thích các trò chơi hữu ích cho sự luyện tập trí óc trong cộng đồng người Việt

CP077 – Một bài toán Diophantine không tuyến tính

Hôm nay, thầy giáo dạy Toán ở lớp Đệ nhất 12B1 có dịp giải thích về phương trình Diophantine.  Đó là những phương trình hay hệ thống mà số ẩn số nhiều hơn số phương trình.  Trong đời sống thường ngày, chúng ta thường gặp những phương trình Diophantine tuyến tính, hay bậc nhất.

Thí dụ như bài toán ”Trâu ăn cỏ” trong dân gian:

Một trăm bó cỏ
Một trăm con trâu
Trâu đứng ăn 5
Trâu nằm ăn 3
Ba con trâu già ăn 1

Hỏi vậy: có bao nhiêu trâu đứng, trâu nằm và trâu già?

Bài toán nêu lên một hệ thống phương trình Diophantine tuyến tính vởi 3 ẩn số x: trâu đứng, y: trâu nằm và z: trâu già, với chỉ có 2 phương trình tuyến tính:

x + y + z   =  100
5x + 3y  +  (z/3)  =  100

Bài toán giải được, tức là có một số giới hạn lời giải,  khi có những điều kiện phụ thuộc giúp thay thế được những phương trình thiếu sót.  Trong bài toán trên, điều kiện phụ thuộc là  số trâu x, y và z phải là số nguyên.

Phương trình Diophantine không tuyến tính khi có chứa luỹ thừa lớn hơn 1 của ẩn số.
Phương trình Diophantine không tuyến tính quen thuộc là định lý Pythagore:
x2 + y2  =  z2
Phương trình có vô số nghiệm số nguyên (x,y,z), thí dụ (3,4,5), được gọi là các bộ 3 số Pythagore.

Phương trình Pell có dạng x2 – ny2 = 1, đặt theo tên của nhà toán học Anh John Pell.  Các nhà toán học cỗ Ấn độ đã tìm được lời giải của phương trình 61x2 + 1 = y2. Đó là:
x = 226153980  và   y = 1766319049.

Không có phương pháp nào tổng quát giúp giải được phương trình Diophantine không tuyến tính. Thường, người ta phải dựa vào những điều kiện phụ thuộc để mong tìm được một lời giải của bài toán

*        *        *

Thầy giáo nêu lên bài toán sau đây để làm thí dụ:

“Tìm một số điện thoại có 7 con số chia ra 2 phần, thí dụ abc-defg, phần thứ nhất có 3 con số, phần thứ hai có 4 con số. Phân nửa bình phương của phần thứ hai trừ bớt phần thứ nhất thì bằng số điện thoại nguyên vẹn với 7 con số”.

Lời giải khởi đi rất đơn giản.  Gọi N là số điện thoại nguyên vẹn với x và y lần lượt là phần đầu và phần sau của số điện thoại. Ta có:

N = (abcdefg),    x = (abc),    y = (defg)

N có nghĩa trong hệ thống thập phân:
N = 10000 (abc) + (defg)   =  10000 x + y           (1)

Theo giả thiết, thì:
½ y2 – x  =  N  =  10000 x + y
=>  (y – 1)2  =  20002 x  +  1                        (2)

Không cần để ý đến x, ta có thể thấy rằng (y – 1)2  khi chia cho 20002 sẽ cho dư số 1, hay:

(y – 1)2 =  bs(20002)  + 1     hay     (y – 1)2 = 1 mod(2002)
=>  y – 1    =  bs(20002)  ± 1

Phân tích 20002 thành thừa số 20002 = 73 * 274
=>   y – 1 =  bs(73 * 274) ± 1

Ta phải giải hệ thống:
y  –  1   =   bs73     ± 1
y  –  1   =   bs274  ±  1

Hay:

y  =  bs73   + 2   (3a)     hay     y  =  bs73      (3b)           (3)
y  =  bs274 + 2   (4a)     hay     y  =  bs274    (4b)           (4)

Số y phải thoả  một trong hai điều kiện trong (3) và một trong hai điều kiện trong (4).

Một cách để tìm nghiêm số y là: Tìm một bội số của y cũng là bội số của 73 hay là bội số của 73 cộng thêm 2.  Lập bảng sau đây:


y = 2192 thoả điều kiện (3a) và (4b)  nên nhận được là 1 nghiệm số.

Suy ra x từ (2):

(2)  =>   (2192 – 1)2 = 20002 x  +  1
=>  x  =  (21912 -1)  / 20002 = 240

Tóm lại:          Số điện thoại phải tìm là:  240-2192

 
Thuận Hoà

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

 
%d bloggers like this: