Diophantine equation of first degree

2010-03-28T04:55:22Z

a1*x1 + a2*x2 + ... + an*xn = S, where:

a1 through an are positive bounded integers
x1 through xn are positive bounded integers
'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?

Answer by François G. Dorais for Diophantine equation of first degree

2010-03-28T05:24:17Z

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 Knapsack Problem, the Subset Sum Problem, and Integer Linear Programming.

Answer by Pete L. Clark for Diophantine equation of first degree

2010-03-28T06:01:04Z

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 Frobenius number $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

$a_1 x_1 + \ldots + a_n x_n = N$.

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.

Perhaps the two most famous results on the Frobenius problem are as follows:

I. Schur's Theorem: if we define

$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\}$

to be the number of representations of $N$, then as $N \rightarrow \infty$ we have

$r(a_1,\ldots,a_n;N) = \frac{N^{n-1}}{(a_1 \cdots a_n) (n-1)!} + O(N^{n-2})$.

II. (Alfred) Brauer's theorem: for $1 \leq i \leq n$, put $e_i = \operatorname{gcd}(a_1,\ldots,a_i)$. Then

$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$,

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)$.

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:

Ramírez Alfonsín, J. L. The Diophantine Frobenius problem. Oxford Lecture Series in Mathematics and its Applications, 30. Oxford University Press, Oxford, 2005.

Diophantine equation of first degree - MathOverflow

Diophantine equation of first degree

Answer by François G. Dorais for Diophantine equation of first degree

Answer by Pete L. Clark for Diophantine equation of first degree