主題
Search

丟番圖方程

丟番圖方程是隻允許整數解的方程。

希爾伯特第十問題詢問是否存在一種演算法來確定任意丟番圖方程是否有解。對於一階丟番圖方程的解，這樣的演算法確實存在。然而，尤里·馬季亞謝維奇在 1970 年證明了獲得通解是不可能的 (Matiyasevich 1970, Davis 1973, Davis and Hersh 1973, Davis 1982, Matiyasevich 1993)，他透過證明關係式 n=F_(2m) (其中 F_(2m) 是第 (2m) 個 斐波那契數) 是丟番圖式的。更具體地說，馬季亞謝維奇證明存在一個關於 P，n、m 和一些其他變數 x、y、z、... 的多項式 P，其性質是 n=F_(2m) 當且僅當 存在整數 x、y、z、... 使得 P(n,m,x,y,z,...)=0。

馬季亞謝維奇的結果填補了馬丁·戴維斯、希拉里·普特南和朱莉婭·羅賓遜先前工作中的一個關鍵空白。馬季亞謝維奇和羅賓遜隨後的工作證明，即使對於包含十三個變數的方程，也不可能存在確定是否存在解的演算法。馬季亞謝維奇隨後將此結果改進為僅包含九個變數的方程 (Jones and Matiyasevich 1982)。

奧格威和安德森 (1988) 給出了一些具有已知和未知解的丟番圖方程。

線性丟番圖方程（在兩個變數中）是以下一般形式的方程

ax+by=c,
(1)

其中解是在 a、b 和 c 為整數的情況下尋求的。這類方程可以完全求解，第一個已知的解是由婆羅摩笈多構造的。考慮方程

ax+by=1.
(2)

現在使用歐幾里得演算法的變體，令 a=r_1 且 b=r_2

r_1=q_1r_2+r_3
(3)
r_2=q_2r_3+r_4
(4)
r_(n-3)=q_(n-3)r_(n-2)+r_(n-1)
(5)
r_(n-2)=q_(n-2)r_(n-1)+1.
(6)

從底部開始得到

1=r_(n-2)-q_(n-2)r_(n-1)
(7)
r_(n-1)=r_(n-3)-q_(n-3)r_(n-2),
(8)

因此

1=r_(n-2)-q_(n-2)(r_(n-3)-q_(n-3)r_(n-2))
(9)
=-q_(n-2)r_(n-3)+(1+q_(n-2)q_(n-3))r_(n-2).
(10)

將此過程一直繼續回到頂部。

以方程為例

1027x+712y=1
(11)

並應用上述演算法得到

1027 = 712· 1+ 315; 712 = 315· 2+ 82; 315 = 82· 3+ 69; 82 = 69· 1+ 13; 69 = 13· 5+ 4; 13 = 4· 3+ 1; |; |; |; |; |; v; 1= -165· 1027+ 238· 712; 1= 73· 712- 165· 315; 1= -19· 315+ 73· 82; 1= 16· 82- 19· 69; 1= -3· 69+ 16· 13; 1= 1· 13- 3· 4; 1= 0· 4+ 1· 1^; |; |; |; |; |; |
(12)

因此解為 x=-165，y=238。

上述過程可以簡化，注意到最左邊的兩列偏移一個條目並且符號交替，因為它們必須如此，因為

1=-A_(i+1)r_i+A_ir_(i+1)
(13)
r_(i+1)=r_(i-1)-r_iq_(i-1)
(14)
1=A_ir_(i-1)-(A_iq_(i-1)+A_(i+1)),
(15)

因此 r_(i-1) 和 r_(i+1) 的係數相同，並且

A_(i-1)=-(A_iq_(i-1)+A_(i+1)).
(16)

因此，使用此資訊重複上述示例得到

1027 = 712· 1+ 315; 712 = 315· 2+ 82; 315 = 82· 3+ 69; 82 = 69· 1+ 13; 69 = 13· 5+ 4; 13 = 4· 3+ 1; |; |; |; |; |; v; (-) 165· 1+ 73 = 238; (+) 73· 2+ 19 = 165; (-) 19· 3+ 16 = 73; (+) 16· 1+ 3 = 19; (-) 3· 5+ 1 = 16; (+) 1· 3+ 0 = 3; (-) 0· 1+ 1 = 1^; |; |; |; |; |; |
(17)

並且我們恢復了上述解。

稱以下方程的解為

ax+by=1
(18)

x_0 和 y_0。如果 ax 或 by 前面的符號為負，則解上述方程並從下表獲取解的符號

方程xy
ax+by=1x_0y_0
ax-by=1x_0-y_0
-ax+by=1-x_0y_0
-ax-by=1-x_0-y_0

事實上，方程的解

ax-by=1
(19)

等價於找到 a/b 的連分數，其中 a 和 b 互質 (Olds 1963)。如果分數中有 n 項，則取第 (n-1) 個收斂項 p_(n-1)/q_(n-1)。但是

p_nq_(n-1)-p_(n-1)q_n=(-1)^n,
(20)

因此一個解是 x_0=(-1)^nq_(n-1)，y_0=(-1)^np_(n-1)，通解為

x=x_0+kb
(21)
y=y_0+ka
(22)

其中 k 是任意整數。用最小正整數表示的解是透過選擇適當的 k 給出的。

現在考慮以下形式的一般一階方程

ax+by=c.
(23)

最大公約數 d=GCD(a,b) 可以除以得到

a^'x+b^'y=c^',
(24)

其中 a^'=a/d，b^'=b/d，且 c^'=c/d。如果 dc，則 c^' 不是整數，並且該方程不可能有整數解。因此，一般一階方程有整數解的充要條件是 d|c。如果是這種情況，則解

a^'x+b^'y=1
(25)

並將解乘以 c^'，因為

a^'(c^'x)+b^'(c^'y)=c^'.
(26)

D. 威爾遜編制了一個正整數的最小第 n 次冪的列表，這些正整數是不同較小正整數的第 n 次冪之和。前幾個是 3、5、6、15、12、25、40，...(OEIS A030052)

3^1=1^1+2^1
(27)
5^2=3^2+4^2
(28)
6^3=3^3+4^3+5^3
(29)
15^4=4^4+6^4+8^4+9^4+14^4
(30)
12^5=4^5+5^5+6^5+7^5+9^5+11^5
(31)
25^6=1^6+2^6+3^6+5^6+6^6+7^6+8^6+9^6+10^6+12^6+13^6+15^6+16^6+17^6+18^6+23^6
(32)
40^7=1^7+3^7+5^7+9^7+12^7+14^7+16^7+17^7+18^7+20^7+21^7+22^7+25^7+28^7+39^7
(33)
84^8=1^8+2^8+3^8+5^8+7^8+9^8+10^8+11^8+12^8+13^8+14^8+15^8+16^8+17^8+18^8+19^8+21^8+23^8+24^8+25^8+26^8+27^8+29^8+32^8+33^8+35^8+37^8+38^8+39^8+41^8+42^8+43^8+45^8+46^8+47^8+48^8+49^8+51^8+52^8+53^8+57^8+58^8+59^8+61^8+63^8+69^8+73^8
(34)
47^9=1^9+2^9+4^9+7^9+11^9+14^9+15^9+18^9+26^9+27^9+30^9+31^9+32^9+33^9+36^9+38^9+39^9+43^9
(35)
63^(10)=1^(10)+2^(10)+4^(10)+5^(10)+6^(10)+8^(10)+12^(10)+15^(10)+16^(10)+17^(10)+20^(10)+21^(10)+25^(10)+26^(10)+27^(10)+28^(10)+30^(10)+36^(10)+37^(10)+38^(10)+40^(10)+51^(10)+62^(10).
(36)

另請參閱

abc 猜想, 阿基米德牛群問題, 巴歇方程, 婆羅摩笈多問題, 炮彈問題, 卡塔蘭猜想, 丟番圖, 丟番圖方程——2 次冪 丟番圖方程——3 次冪, 丟番圖方程——4 次冪, 丟番圖方程——5 次冪 丟番圖方程——6 次冪, 丟番圖方程——7 次冪, 丟番圖方程——8 次冪, 丟番圖方程——9 次冪, 丟番圖方程——10 次冪, 丟番圖方程——n 次冪, 丟番圖性質, 尤拉磚塊, 尤拉四次猜想, 費馬最後定理, 費馬橢圓曲線定理, 虧格定理, 赫爾維茨方程, 馬爾可夫數, 猴子與椰子問題, 多次方程組, p-adic 數, 佩爾方程, 畢達哥拉斯四元組, 畢達哥拉斯三元組, 有理距離問題, 圖厄方程 在 課堂中探索此主題

使用 探索

參考文獻

Alpern, D. "Sums of Powers." http://www.alpertron.com.ar/SUMPOWER.HTM.Bashmakova, I. G. Diophantus and Diophantine Equations. Washington, DC: Math. Assoc. Amer., 1997.Beiler, A. H. Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. New York: Dover, 1966.Carmichael, R. D. The Theory of Numbers, and Diophantine Analysis. New York: Dover, 1959.Courant, R. and Robbins, H. "Continued Fractions. Diophantine Equations." §2.4 in Supplement to Ch. 1 in What Is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 49-51, 1996.Davis, M. "Hilbert's Tenth Problem is Unsolvable." Amer. Math. Monthly 80, 233-269, 1973.Davis, M. and Hersh, R. "Hilbert's 10th Problem." Sci. Amer. 229, 84-91, Nov. 1973.Davis, M. "Hilbert's Tenth Problem is Unsolvable." Appendix 2 in Computability and Unsolvability. New York: Dover, 1999-235, 1982.Dickson, L. E. "Linear Diophantine Equations and Congruences." Ch. 2 in History of the Theory of Numbers, Vol. 2: Diophantine Analysis. New York: Dover, pp. 41-99, 2005.dmoz. "Equal Sums of Like Powers." http://dmoz.org/Science/Math/Number_Theory/Diophantine_Equations/Equal_Sums_of_Like_Powers/.Dörrie, H. "The Fermat-Gauss Impossibility Theorem." §21 in 100 Great Problems of Elementary Mathematics: Their History and Solutions. New York: Dover, pp. 96-104, 1965.Ekl, R. L. "New Results in Equal Sums of Like Powers." Math. Comput. 67, 1309-1315, 1998.Guy, R. K. "Diophantine Equations." Ch. D in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 139-198, 1994.Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, 1979.Hunter, J. A. H. and Madachy, J. S. "Diophantos and All That." Ch. 6 in Mathematical Diversions. New York: Dover, pp. 52-64, 1975.Ireland, K. and Rosen, M. "Diophantine Equations." Ch. 17 in A Classical Introduction to Modern Number Theory, 2nd ed. New York: Springer-Verlag, pp. 269-296, 1990.Jones, J. P. and Matiyasevich, Yu. V. "Exponential Diophantine Representation of Recursively Enumerable Sets." Proceedings of the Herbrand Symposium, Marseilles, 1981. Amsterdam, Netherlands: North-Holland, pp. 159-177, 1982.Lang, S. Introduction to Diophantine Approximations, 2nd ed. New York: Springer-Verlag, 1995.Matiyasevich, Yu. V. "Solution of the Tenth Problem of Hilbert." Mat. Lapok 21, 83-87, 1970.Matiyasevich, Yu. V. Hilbert's Tenth Problem. Cambridge, MA: MIT Press, 1993. http://www.informatik.uni-stuttgart.de/ifi/ti/personen/Matiyasevich/H10Pbook/.Meyrignac, J.-C. "Computing Minimal Equal Sums of Like Powers." http://euler.free.fr/.Mordell, L. J. Diophantine Equations. New York: Academic Press, 1969.Nagell, T. "Diophantine Equations of First Degree." §10 in Introduction to Number Theory. New York: Wiley, pp. 29-32, 1951.Ogilvy, C. S. and Anderson, J. T. "Diophantine Equations." Ch. 6 in Excursions in Number Theory. New York: Dover, pp. 65-83, 1988.Olds, C. D. Ch. 2 in Continued Fractions. New York: Random House, 1963.Sloane, N. J. A. Sequence A030052 in "The On-Line Encyclopedia of Integer Sequences."Weisstein, E. W. "Books about Diophantine Equations." http://www.ericweisstein.com/encyclopedias/books/DiophantineEquations.html.

在 上被引用

丟番圖方程

請引用為

Weisstein, Eric W. "丟番圖方程。" 來自 Web 資源。 https://mathworld.tw/DiophantineEquation.html

學科分類