丟番圖

亞歷山大港的丟番圖（希臘語：Διόφαντος ὁ Ἀλεξανδρεύς，生卒年約公元200～214至公元284～298），有「代數之父」之稱；也有人認為^[1]此稱謂應與比他大約晚出生五百年的一位波斯數學家花拉子米共享。丟番圖是古希臘亞歷山大港的數學家，他作著的叢書《算術》（Arithmetica）處理求解代數方程組的問題，但其中有不少已經遺失。後來當法國數學家費馬（Pierre de Fermat）研究《算術》一書時，對其中某個方程頗感興趣並認為其無解，說他對此「已找到一個絕妙的證明」，但他卻沒有寫下來，三個世紀後才出現完整的證明，詳見費馬大定理。在數論中常常能看到他的名字，如丟番圖方程、丟番圖幾何、丟番圖逼近等都是數學裡重要的研究領域。丟番圖是第一個承認分數是一種數的希臘數學家－－他允許方程中的系數和解為有理數，這是在數學史中具有開創性的。不過在今天，丟番圖方程一詞通常指以整數作為系數的代數方程，而其解也要求是整數。丟番圖在數學符號方面也作出了貢獻。

……

丟番圖方程

丟番圖方程，是變數僅容許是整數的整數係數多項式等式；即形式如 $a_{1}x_{1}^{b_{1}}+a_{2}x_{2}^{b_{2}}+......+a_{n}x_{n}^{b_{n}}=c$ 的等式，並且其中所有的 $a_{j}$ 、 $b_{j}$ 和 $c$ 均是整數，若其中能找到一組整數解 $m_{1},m_{2}...m_{n}$ 者則稱之有整數解。

丟番圖問題一般可以有數條等式，其數目比未知數的數目少；丟番圖問題要求找出對所有等式都成立的整數組合。換言之，丟番圖問題定義了代數曲綫或者代數曲面，或更爲一般的幾何形，要求找出其中的柵格點。對丟番圖問題的數學研究稱為丟番圖分析。綫性丟番圖方程爲綫性整數係數多項式等式，即此多項式爲次數爲0或1的單項式的和。

丟番圖方程的名字來源於3世紀希臘數學家亞歷山大城的丟番圖，他曾對這些方程進行研究，並且是第一個將符號引入代數的數學家。

關於丟番圖方程的理論的形成和發展是二十世紀數學一個很重要的發展。丟番圖方程的例子有貝祖等式、勾股定理的整數解、佩爾方程、四平方和定理和費馬最後定理等。

───

費馬閱讀代數之父丟番圖之《算術》，是否真的發現

$x^n + y^n = z^n \ , \ n \geq 3$

沒有『整數解』之巧妙證明？若有人閱讀安德魯‧懷爾斯 Andrew John Wiles 以及其學生理查‧泰勒 Richard Taylor 的晦澀『證明』，能不能另闢蹊徑，找到容易理解的闡釋？『簡單』的提問往往卻是『不容易』回答！更別說數理邏輯之精深，讓人嘆為觀止矣！

丟番圖分析

經典問題

有解答嗎？
除了一些顯然易見的解答外，還有哪些解答？
解答的數目是有限還是無限？
理論上，所有解答是否都能找到？
實際上能否計算出所有解答？

希爾伯特第十問題

主條目：希爾伯特第十問題

1900年，希爾伯特提出丟番圖問題的可解答性為他的23個問題中的第10題。1970年，一個數理邏輯的結果馬蒂雅謝維奇定理（Matiyasevich’s theorem）說明：一般來說，丟番圖問題都是不可解的。更精確的說法是，不可能存在一個演算法能夠判定任何丟番圖方程是否有解，甚至，在任何相容於皮亞諾算數的系統當中，都能具體構造出一個丟番圖方程，使得沒有任何辦法可以判斷它是否有解。

即使知道二元一次不定方程式

$ax + by = c$

的通解為

$x = x_1 + \frac{b}{gcd(a,b)} t$

$y = y_1 - \frac{a}{gcd(a,b)} t$

，此處 $x_1, y_1$ 為該方程式的任一組解。

一次不定方程

一次不定方程是形式如 $a_{1}x_{1}+a_{2}x_{2}+...+a_{n}x_{n}=c$ 的方程，一次不定方程有整數解的充要條件為：

gcd

(a_{1},...,a_{n})|c

換言之 $gcd(a_{1},...,a_{n})$ 須是 $c$ 的因數，其中 $gcd(a_{1},...,a_{n})$ 表示 $a_{1},...,a_{n}$ 的最大公因數。

若有二元一次不定方程 $ax+by=c$ ，且 $gcd(a,b)|c$ ，則其必有一組整數解 $x_{1},y_{1}$ ，並且還有以下關係式：

$x=x_{1}+[b/(a,b)]t$
$y=y_{1}-[a/(a,b)]t$

$t$ 為任意整數，故此一次不定方程有無限多解。請參見貝祖等式。

如何求取 $x_1, y_1$ 還得明白『輾轉相除法』也。

Extended Euclidean algorithm

In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, which computes, besides the greatest common divisor of integers a and b, the coefficients of Bézout’s identity, that is integers x and y such that

ax+by=\gcd(a,b).

This is a certifying algorithm, because the gcd is the only number that can simultaneously satisfy this equation and divide the inputs. It allows one to compute also, with almost no extra cost, the quotients of a and b by their greatest common divisor.

Extended Euclidean algorithm also refers to a very similar algorithm for computing the polynomial greatest common divisor and the coefficients of Bézout’s identity of two univariate polynomials.

The extended Euclidean algorithm is particularly useful when a and b are coprime, since x is the modular multiplicative inverse of a modulo b, and y is the modular multiplicative inverse of b modulo a. Similarly, the polynomial extended Euclidean algorithm allows one to compute the multiplicative inverse in algebraic field extensions and, in particular in finite fields of non prime order. It follows that both extended Euclidean algorithms are widely used in cryptography. In particular, the computation of the modular multiplicative inverse is an essential step in RSA public-key encryption method.

如是自然知道 sympy 的符號算術有其極限乎？

Diophantine equations

The word “Diophantine” comes with the name Diophantus, a mathematician lived in the great city of Alexandria sometime around 250 AD. Often referred to as the “father of Algebra”, Diophantus in his famous work “Arithmetica” presented 150 problems that marked the early beginnings of number theory, the field of study about integers and their properties. Diophantine equations play a central and an important part in number theory.

We call a “Diophantine equation” to an equation of the form, $f(x_1, x_2, \cdots , x_n) = 0$ where $n \geq 2$ and $x_1, x_2, \cdots, x_n$ $x_{1}, x_{2}, \dots x_{n}$ are integer variables. If we can find $n$ integers $a_1, a_2, \cdots , a_n$ such that $x_1 = a_1, x_2 = a_2, \cdots , x_n = a_n$ $x_{1} = a_{1}, x_{2} = a_{2}, \dots x_{n} = a_{n}$ satisfies the above equation, we say that the equation is solvable. You can read more about Diophantine equations in [1] and [2].

Currently, following five types of Diophantine equations can be solved using diophantine() and other helper functions of the Diophantine module.

Linear Diophantine equations: $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b$ .
General binary quadratic equation: $a x^2 + b x y + c y^2 + d x + e y + f = 0$ $a x^{2} + b x y + c y^{2} + d x + e y + f = 0$
Homogeneous ternary quadratic equation: $a x^2 + b y^2 + c z^2 + d x y + e y z + f z x = 0$ $a x^{2} + b y^{2} + c z^{2} + d x y + e y z + f z x = 0$
Extended Pythagorean equation: $a_1 {x_1}^2 + a_2 {x_2}^2 + \cdots + a_n {x_n}^2 = a_{n+1} {x_{n+1}}^2$ $a_{1} x_{1}^{2} + a_{2} x_{2}^{2} + \dots + a_{n} x_{n}^{2} = a_{n + 1} x_{n + 1}^{2}$
General sum of squares: ${x_1}^2 + {x_2}^2 + \cdots + {x_n}^2 = k$ $x_{1}^{2} + x_{2}^{2} + \dots + x_{n}^{2} = k$

pi@raspberrypi:~ $ python3
Python 3.4.2 (default, Oct 19 2014, 13:31:11) 
[GCC 4.9.1] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from sympy import *
>>> from sympy.solvers.diophantine import diop_solve
>>> x, y = symbols('x, y')
>>> diop_solve(2*x + 3*y - 5)
(3*t_0 - 5, -2*t_0 + 5)
>>>

因此據聞畢式學派也不能正確得到畢氏三元數之通式解。難到果真奇怪耶？？

FreeSandal

萬象在說話︰簡單問不容易答

丟番圖