Loài bài toán này đã hơn 1600 năm tuổi

38

Loài bài toán này đã hơn 1600 năm tuổi

B. A. Kordemsky

Cốt truyện và hình thức ký hiệu bài toán đã thay đổi, các phương thức lời giải được tích lũy, nhưng bản chất vẫn không thay đổi: tìm số nguyên (thường là tự nhiên) $x$ và $y$, thỏa mãn phương trình
$$ax + by = c$$
(1)
Với. được cho bởi các hệ số nguyên $a$, $b$ và $c$.

Có lẽ $c$ là 1001 câu chuyện của Sheherezda và chúng tôi quan tâm đến việc Sheherezda sẽ mất bao nhiêu đêm để kể tất cả câu chuyện của mình nếu cô ấy kể 5 câu chuyện trong $x$ đêm và 3 câu chuyện trong $y$ đêm.

Những tác phẩm tuyệt vời rõ ràng sẽ cần $x+y$ đêm, trong đó $x$ và $y$ là nghiệm tự nhiên của phương trình $5x+3y=1001$.

Hoặc có thể $c$ là 10 $p$. 01 $\kappa$., số tiền này một số người chi cho $x$ chuyến đi bằng xe buýt (5 kopecks mỗi chuyến) và $y$ chuyến đi bằng xe điện (3 kopecks mỗi chuyến). Đáp số cho câu hỏi đã thực hiện bao nhiêu chuyến đi được đưa vào cùng một phương trình $5x+3y=1001$.

Nghiệm của phương trình này cũng cho chúng ta biết về những điểm trên đường thẳng

Cơm. 1.

$5x+3y=1001$ (xem hình), cả hai tọa độ đều là số tự nhiên (hoặc số nguyên - trong một số bài toán khác).

Các phương trình trong đó chỉ có các giá trị nguyên của ẩn số được tách ra khỏi tập hợp lời giải thường được gọi là Diophantine để vinh danh nhà toán học nổi tiếng thế kỷ 2-3. Diophanthus từ Alexandria.

Các vấn đề lý thuyết liên quan đến điều kiện tồn tại của số nguyên, đặc biệt là phương trình lời giải tự nhiên có dạng $ax+by=c$, được V. N. Vaguten xem xét trong bài “Thuật toán Euclide và Lý thuyết cơ bản của số học” («Kvant» Số 6, 1972). Chúng ta sẽ không đề cập đến lý thuyết này mà sẽ xem xét lời giải của một phương trình cụ thể $5x+3y=1001$ để chỉ ra, bằng cách sử dụng ví dụ này, các kỹ thuật khác nhau giúp tìm phương trình số nguyên lời giải *).

Lời giải theo cách “học sinh sáng tạo”

Chúng ta chia cả hai vế của phương trình $5x+3y=1001$ cho hệ số nhỏ hơn: $\frac{5}{3}x+y=\frac{1001}{3}$; ở bên phải và làm theo toàn bộ các phần:
$$x+\frac{2}{3}x+y=333+\frac{2}{3};$$
$$x+y+\frac{2(x-1)}{3}=333.$$ (2)

Vì $x$ và $y$ là số nguyên nên $\frac{x-1}{3}$ cũng phải là số nguyên; chúng tôi đặt $\frac{x-1}{3}=t$; thì $x=3t+1$. Thay vào (2), ta được
$$3t+1+y+2t=333; y=332-5t.$$

Trong bài viết được đề cập, V. N. Vagutena chứng minh rằng các biểu thức thu được cho $x$ và $y$ là “lời giải tổng quát”, nghĩa là chúng chứa

*) Chúng ta chỉ nhắc lại rằng sự tồn tại của số nguyên lời giải của phương trình (1) đảm bảo các điều kiện gcd ($a,b)=1$, do đó phương trình $5x+3y=1001$ có ​​lời giải là số nguyên.

39

chứa tất cả các số nguyên lời giải của phương trình đã cho.

Đưa tham số $t$ giá trị $t = 0, 1, 2, \dots, 66$, chúng ta tìm thấy 67 cặp nghiệm tự nhiên có thể có của phương trình này.

Bây giờ chúng ta hãy giả định thêm rằng Scheherazade muốn phân phát một nghìn lẻ một câu chuyện của cô ấy trong càng nhiều đêm càng tốt *). Yêu cầu này được thỏa mãn tối đa $(x + y)$, là tổng lớn nhất trong tổng các cặp nghiệm của phương trình. Chúng tôi có $x + y = 333 - 2t$; Rõ ràng, đạt được tối đa $(x + y)$ ở $t = 0$.

Vì vậy, Scheherazade sẽ kể những câu chuyện của mình trong nhiều nhất là 333 đêm, nếu cô ấy kể 3 câu chuyện trong 332 đêm và 5 câu chuyện chỉ trong một đêm. Cô ấy có thể rút ngắn thời gian “làm việc” của mình và nâng nó lên 201 đêm, nếu chỉ 2 lần (với khả năng sáng tạo tối đa của một học sinh sáng tạo), bạn đã nhận được $x + y + \frac{4y - 1}{3} = 77$. Bây giờ chúng ta nên tính toán và hành động như thế nào để thể hiện cách tiếp cận trước tiên là $y$, sau đó là $x$ cho đến toàn bộ $t$?

Lời giải theo cách của một “nhà toán học sáng tạo” **)

Đối với phương trình $ax + by = c$, quy trình như sau: tìm số dư $m$ khi $a$ chia cho $b$ (gọi $a > b$) và số dư $n$ khi $c$ chia cho $b$; nếu $n = 0$, thì ngay lập tức chúng ta nhận được $x = bt$, $y = \frac{c}{b} - at$, $t = 0, \pm 1, \pm 2, \dots$;

*) Tất nhiên, với điều kiện mỗi đêm cô ấy kể ba hoặc năm câu chuyện cổ tích.
**) Người phát minh ra phương pháp này, Taylor L. F., “Numbers”, London, 1970, không đặt tên cho nó.

nếu $n \neq 0$ thì nhân $m$ liên tiếp với 1, 2, …, $(b - 1)$ và viết dãy số dư khi chia các tích này cho $b$. Chuỗi kết quả sẽ chứa số $n$ (nếu không có thì sẽ không có phương trình số nguyên lời giải). Số vị trí bị chiếm bởi số $n$ trong dãy dư lượng là một trong những giá trị có thể có $x$.

Hãy áp dụng phương pháp này cho phương trình $5x + 3y = 1001$. Chúng ta có: $m = 2$, $n = 2$, nhân $m = 2$ với mỗi thành viên của chuỗi {1; 2}, ta được {2; 4}; chia cho 3 và viết số dư: {2; 1}. Chúng tôi lưu ý rằng số $n = 2$ chiếm vị trí đầu tiên trong chuỗi số dư này, do đó $x = 1$. Điều này xác định giá trị tương ứng $y = 332$.

Một cách dễ dàng và khá tổng quát lời giải cho số phương trình tuyến tính vô định của hai ẩn số!

Nhưng “phương pháp của nhà toán học sáng tạo”, không giống như phương pháp trước đó, chỉ cho chúng ta một cặp nghiệm: (1; 332). Phương pháp khiếm khuyết? Không có gì. Xem lại các công thức cho “tổng quát lời giải” bài toán, thu được “theo phương pháp học sinh”: $x = 1 + 3t$, $y = 332 - 5t$.

《Thương lời giải》 $x_0 = 1, y_0 = 332$ giống nhau trong các phương pháp chung và các hệ số $t$ (3 và 5) được xác định bởi các hệ số lời giải của phương trình: $3 = b; -5 = -a$. Và đây không phải là sự trùng hợp ngẫu nhiên mà là một quy luật: nếu $(x_0, y_0)$ là bất kỳ số nguyên lời giải nào của phương trình $ax + by = c$, và $a$ và $b$ là nguyên tố cùng nhau, thì tất cả các số nguyên lời giải của nó được xác định bởi các công thức: $x = x_0 + bt$, $y = y_0 - at$, $t = 0, \pm 1, \pm 2, \dots$.

Lời giải “bằng phương pháp so sánh mô-đun”

Đây là một cách hay và thường nhanh nhất để tìm phương trình số nguyên lời giải $ax + by = c$.

Đối với toàn bộ chúng ta, chỉ cần nhớ lại tuyên bố $a \equiv b$ (mod $m$) là đủ

40

tương đương với $a-b$ được chia cho $m$ hoặc $a=b+km$ ($a, b$ và $k$ là số nguyên, $m$ là số tự nhiên).

Hơn nữa, nếu $a \equiv b$ (mod $m$), thì đúng là $a \equiv b+km$ (mod $m$), trong đó $k$ là số nguyên bất kỳ $^*$). Ví dụ: đặt $3x \equiv 2$ (mod 5), sau đó $3x \equiv 2+2\cdot 5$ (mod 5), $3x \equiv 12$ (mod 5) và $x \equiv 4$ (mod 5).

Lưu ý rằng việc chia cả hai vế của modulo so sánh $m$ cho một thừa số chung $q$ chỉ được phép nếu $q$ và $m$ là các số nguyên tố tương đối.

Ví dụ sơ bộ. Hãy giải quyết sự so sánh $11x \equiv 2$ (mod 23). Việc cộng 23 vào vế phải là không thực tế cho đến khi bạn nhận được bội số của 11. Bạn phải tìm một đường đi thấp hơn. Ví dụ: cách này phù hợp: viết $22x \equiv 4$ (mod 23), sau đó trừ $23x$ từ vế trái; chúng tôi nhận được $-x \equiv 4$ (mod 23), $x \equiv -4$ (mod 23) và cuối cùng là $x \equiv 19$ (mod 23).

Đối với phương trình lời giải $5x+3y=1001$ “bằng phương pháp so sánh modulo”, bạn cần thực hiện như sau: $3y=1001-5x; 3y=1001$ (mod 5). Vì $1001=200\cdot 5+1$, thì $3y \equiv 1$ (mod 5) hoặc $3y \equiv 6$ (mod 5); $y \equiv 2$ (mod 5), do đó $y=2+5k$ ($k=0, \pm 1, \pm 2, \dots$). Dễ dàng nhận thấy rằng lời giải này tương đương với việc đến sớm

$$y=332-5t \ (t=0, \pm 1, \pm 2, \dots).$$

Lời giải “bằng phương pháp so sánh modulo” bạn cần thực hiện như sau: $3y=1001-5x; 3y=1001$ (mod 5). Vì $1001=200\cdot 5+1$, thì $3y \equiv 1$ (mod 5) hoặc $3y \equiv 6$ (mod 5); $y \equiv 2$ (mod 5), do đó $y=2+5k$ ($k=0, \pm 1, \pm 2, \dots$). Dễ dàng nhận thấy rằng lời giải này tương đương với việc đến sớm

$$y=332-5t \ (t=0, \pm 1, \pm 2, \dots).$$

*) Rất nhiều thông tin hữu ích về việc so sánh các số nguyên theo modulo được đưa ra trong các bài viết của A. A. Egorov “So sánh theo modulo và số học của số dư” («Kvant» Số 5, 1970), M. I. Bashmkov “Bạn có thích mày mò với số nguyên” («Kvant» Số 3, 1971) và phía trên các bài viết của V. N. Vaguten.

các phương trình ở “vùng đất trinh nguyên”:

$$\frac{a}{b} = [a_0; a_1, a_2, \dots, a_n],$$

tính trực tiếp tử số và mẫu số của phân số “khớp” áp chót $\frac{P_{n-1}}{Q_{n-1}}$ hoặc sử dụng công thức truy hồi

$$P_{k+1} = P_k \cdot a_{k+1} + P_{k-1};$$

$$Q_{k+1} = Q_k \cdot a_{k+1} + Q_{k-1},$$

trong đó $P_0=a_0$, $Q_0=1$ và $P_1=a_0 \cdot a_1+1$ và $Q_1=a_1$, $k=0, 1, 2, \dots$.

Lời giải bài toán được hoàn thành bằng cách áp dụng các công thức có sẵn*) biểu diễn tổng quát lời giải của phương trình đã cho

$$\begin{cases} x = (-1)^{n-1} \cdot c \cdot Q_{n-1} + b \cdot t, \\ y = (-1)^{n} \cdot c \cdot P_{n-1} - a \cdot t, \\ t = 0; \pm 1; \pm 2, \dots. \end{cases}$$

Chúng ta hãy xem phương trình $5x+3y=1001$ lần cuối. Hãy thực hiện chuyển đổi chi tiết số $\frac{5}{3}$ thành phân số tiếp theo:

$$\frac{-5}{3} \left| \frac{3}{1} \right| \dots a_0=1,$$

$$\frac{-3}{2} \left| \frac{2}{1} \right| \dots a_1=1,$$

$$\frac{2}{2} \left| \frac{1}{2} \right| \dots a_2=2,$$

từ đâu $\frac{5}{3} = [1; 1, 2]$. Hãy tạo một phân số “thích hợp”

$$\frac{P_0}{Q_0} = \frac{a_0}{1} = 1; \quad \frac{P_1}{Q_1} = a_0 + \frac{1}{a_1} = \frac{2}{1};$$

$$\frac{P_2}{Q_2} = a_0 + \frac{1}{a_1 + \frac{1}{a_2}} = \frac{5}{3}$$

(không cần phân số thích hợp cuối cùng, ngoài ra nó luôn bằng phân số đã cho

*) Nguồn gốc của các công thức này có thể được tìm thấy trong sách giáo khoa đặc biệt, hoặc, ví dụ, trong cuốn “Bách khoa toàn thư về toán tiểu học”, cuốn một, năm 1951 (bài viết của A. Ya. Khinchin “Các phần tử của lý thuyết số”). Phân số tiếp tục cũng được thảo luận trong bài viết “Phân số tiếp tục” của N. M. Beskin («Kvant» Số 1, 1970).

41

phần Nô-ê; chúng tôi thực hiện phép tính chỉ để điền vào cách soạn vô thời hạn các phân số “phù hợp”).

Vì ở đây $n = 2$, tử số $P_{n-1}$ và mẫu số $Q_{n-1}$ của phân số “phù hợp” áp chót lần lượt bằng nhau

$$P_{n-1} = P_1 = 2; \quad Q_{n-1} = Q_1 = 1.$$

Mọi thứ đã sẵn sàng để áp dụng công thức (3): $x = -1 \cdot 1001 \cdot 1 + 3t, y = 1 \cdot 1001 \cdot 2 - 5t, t = 0, \pm 1, \pm 2, \dots$.

Cuối cùng, $x = -1001 + 3t, y = 2002 - 5t, t = 0, \pm 1, \pm 2, \dots$.

Với sự xuất hiện của lời giải, có vẻ như một kết quả khác đã thu được một lần nữa, không được giữ nguyên với các kết quả trước đó, nhưng có thể dễ dàng phát hiện sự tương đương của nó với tất cả các bản ghi trước đó của phương trình tổng quát lời giải đang xem xét. Do đó, $x = 1$ và $y = 332$ được lấy từ đây tại $t = 334$. Bây giờ chúng ta hãy giải một bài toán khác.

Sau vụ đắm tàu

Năm thủy thủ đổ bộ lên đảo và đến tối đã thu được một chùm dừa. Việc phân chia được hoãn lại cho đến sáng. Một người trong số họ thức dậy vào ban đêm, đếm số dobtsych, đãi con khỉ một quả hạch và lấy chính xác $\frac{1}{5}$ phần số quả hạch còn lại, sau đó anh ta quay lại giường và nhanh chóng chìm vào giấc ngủ. Trong đêm, lần lượt các thủy thủ còn lại cũng làm như vậy; Hơn nữa, mỗi người đều không hề hay biết về hành động của những người đi trước. Sáng hôm sau họ chia đều số hạt còn lại, nhưng lần này không còn hạt thừa nào cho con khỉ. Các thủy thủ đã thu thập được bao nhiêu quả hạch?

Lời giải. Chúng ta hãy biểu thị số lượng hạt cần thiết là $x$. Biểu diễn các hành động tuần tự của các thủy thủ bằng phương trình, ta được $x = 5a + 1; 4a = 5b + 1; 4b = 5c + 1; 4c = 5d + 1; 4d = 25y + 1$ (nghĩ về ý nghĩa của các phương trình đã đề xuất).

Hệ thống này giảm xuống một phương trình không xác định

$$256x = 2101 + 15625y.$$

Tính lời giải bằng số nguyên của phương trình phức tạp này sẽ là một phần thưởng thú vị cho việc kiên nhẫn làm quen với bốn phương pháp được đề xuất - bạn có thể chọn phương pháp hiệu quả nhất cho một bài toán nhất định. Đáp số trong bài toán này là: $x = 3121$ là giá trị tự nhiên cao nhất có thể có của $x$.

Quét. Trong cuốn sách Câu đố toán học và giải trí (Thế giới, 1971) của M. Gardner, trong đó có bài toán, người ta viết rằng nó “được xếp trong số những câu đố được giải thường xuyên nhất nhưng dễ tuân theo nhất đối với lời giải Câu đố Diophantine” (trang 234). Khi bài toán này xuất hiện trên một tờ báo vào năm 1926 (không có lời giải và đáp số), thì trong 20 năm sau đó, luồng thư gửi đến tờ báo không dừng lại với yêu cầu báo cáo đáp số, hoặc với một biến thể lời giải của riêng họ.

Trận chiến

1. Tìm phương trình số nguyên lời giải $10x + 21y = 23$ bằng cách sử dụng từng phương pháp được mô tả.
2. Tìm một số có hai chữ số có tổng số hàng đơn vị là 13 nhỏ hơn ba lần số hàng chục.
3. Một số du khách được xếp đều trên 5 xe buýt (mỗi xe chở không quá 54 người) đã được đưa đến ga. Ở đó, họ có thêm 7 người nữa tham gia và tất cả những người tham gia chuyến du ngoạn được phân bổ đều ở 14 varonas. Tổng cộng có bao nhiêu khách du lịch ở đó?
4. Ví dụ: có $13x - 5y + 96 = 0$ điểm có tọa độ nguyên không vượt quá số 10 về giá trị tuyệt đối không?
5. Cho $n$ là một số tự nhiên. Tìm phương trình số nguyên lời giải

$$nx + (n + 1)y = 2n + 1.$$

6. Cần đổ 15 lít chất lỏng vào các chai 0,5 lít và 0,8 lít sao cho đầy các chai đã sử dụng. Cần bao nhiêu chai của cả hai?
7. Chứng minh rằng với mọi $x$ số lẻ thì phép so sánh $x^2 \equiv 1$ (mod 8) đúng, tức là bình phương của một số nguyên lẻ bất kỳ khi chia cho 8 đều có dư một.