Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

  1. a1 through an are positive bounded integers
  2. x1 through xn are positive bounded integers
  3. '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?
share|improve this question
    
What does 'positive bounded' mean exactly? Your condition for $n=2$ doesn't always work if $x_1$ and $x_2$ are bounded. It also doesn't work if when $S = 17$ and $a_1 = a_2 = 2$. –  François G. Dorais Mar 28 '10 at 5:34

2 Answers 2

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

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

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.