Diophantine equation of first degree - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T22:59:49Z http://mathoverflow.net/feeds/question/19587 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/19587/diophantine-equation-of-first-degree Diophantine equation of first degree mingming 2010-03-28T04:55:22Z 2010-03-28T06:53:04Z <p>a1*x1 + a2*x2 + ... + an*xn = S, where:</p> <ol> <li>a1 through an are positive bounded integers</li> <li>x1 through xn are positive bounded integers</li> <li>'S' is the sum of the expression for n=2 say a1*x1 + a2*x2=S we know when S>a1*a2-a1-a2 the equation has solution. Do any of you know such kind of condition when n is in general?</li> </ol> http://mathoverflow.net/questions/19587/diophantine-equation-of-first-degree/19590#19590 Answer by François G. Dorais for Diophantine equation of first degree François G. Dorais 2010-03-28T05:24:17Z 2010-03-28T06:53:04Z <p>Your question is a little imprecise. In general, when the integers $x_i$'s are bounded above and below, such problems are very difficult to decide whether there is a solution see the <a href="http://en.wikipedia.org/wiki/Knapsack_problem" rel="nofollow">Knapsack Problem</a>, the <a href="http://en.wikipedia.org/wiki/Subset_sum_problem" rel="nofollow">Subset Sum Problem</a>, and <a href="http://en.wikipedia.org/wiki/Linear_programming#Integer_unknowns" rel="nofollow">Integer Linear Programming</a>.</p> http://mathoverflow.net/questions/19587/diophantine-equation-of-first-degree/19593#19593 Answer by Pete L. Clark for Diophantine equation of first degree Pete L. Clark 2010-03-28T06:01:04Z 2010-03-28T06:09:04Z <p>It sounds to me like the OP is asking about the Diophantine Problem of Frobenius. This is as follows: let $(a_1,\ldots,a_n)$ be positive integers which generate the unit ideal (i.e., their setwise gcd is $1$). The <strong>Frobenius number</strong> $f(a_1,\ldots,a_n)$ is the largest positive integer $N$ such that there do not exist non-negative integers $x_1,\ldots,x_n$ such that</p> <p>$a_1 x_1 + \ldots + a_n x_n = N$.</p> <p>In the case of $n = 2$, the Frobenius number was explicitly computed by J.J. Sylvester (before Frobenius!): it is $a_1 a_2 - a_1 - a_2$, as the OP mentioned. Using this fact, it is a nice exercise to show by induction on $n$ that every sufficiently large integer $N$ can indeed be represented as a non-negative integer linear combination of the $a_i$'s.</p> <p>Perhaps the two most famous results on the Frobenius problem are as follows:</p> <p>I. Schur's Theorem: if we define </p> <p><code>$r(a_1,\ldots,a_n;N) = \# \ \{(x_1,\ldots,x_n) \in \mathbb{N}^n \ | \ a_1 x_1 + \ldots + a_n x_n = N\}$</code></p> <p>to be the number of representations of $N$, then as $N \rightarrow \infty$ we have </p> <p>$r(a_1,\ldots,a_n;N) = \frac{N^{n-1}}{(a_1 \cdots a_n) (n-1)!} + O(N^{n-2})$. </p> <p>II. (Alfred) Brauer's theorem: for $1 \leq i \leq n$, put $e_i = \operatorname{gcd}(a_1,\ldots,a_i)$. Then </p> <p>$f(a_1,\ldots,a_n) \leq \sum_{i=2}^n a_i \frac{e_{i-1}}{e_i} - \sum_{i=1}^n a_i + 1$, </p> <p>with equality iff for all $i \geq 2$, $\frac{e_{i-1}}{e_i} a_i$ can be represented as a non-negative integer combination of the integers $(a_1,\ldots,a_i)$. </p> <p>There have been on the order of a thousand papers written about various aspects of this problem and as well as a rather authoritative recent book:</p> <blockquote> <p>Ramírez Alfonsín, J. L. The Diophantine Frobenius problem. Oxford Lecture Series in Mathematics and its Applications, 30. Oxford University Press, Oxford, 2005. </p> </blockquote>