## Diophantine  equation of first degree

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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?
-

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 2010 at 5:34

## 2 Answers

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.

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 26, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.930301308631897, "perplexity_flag": "head"}