Integer relation that equals one My question is related to the Integer Relation Detection Problem which can be formulated as:
$a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0$
Where $\forall_{a_i} a_i\in\mathbb{Z},a_i<c$ and $\exists_{a_i} a_i\neq 0$, and $\forall_{x_i} x\in \mathbb{R}$. $c$ and vector $\mathbf{x}$ are given, and the problem is to find a valid vector $\mathbf{a}$ that satisfies these constraints.
There are a few algorithms to solve this problem, listed on the wikipedia page linked.
My question: are there algorithms for a solution to the same problem with the modification that:
$a_1x_1 + a_2x_2 + \cdots + a_nx_n = 1$
Or equivalently (I believe):
$a_1x_1 + a_2x_2 + \cdots + a_nx_n = b$
$b\in \mathbb R$ is a given.
I would love to see some reduction to an existing problem with a polynomial-time algorithm, such as Integer Relation Detection, or Simultaneous Integer Relation Detection. Another possibility is that this is a hard problem.
 A: Here's an example of what I meant.  Suppose you want to solve (approximately) $a_1 x_1 + a_2 x_2 + a_3 x_3 = 1$ where $x_1 = .234532$, $x_2 = .876834$, $x_3 = .917409$.  You take $x_4 = -1$ and give LLL the vectors $[1,0,0,0,234532], [0,1,0,0,876834], [0,0,1,0,917409], [0,0,0,1,-1000000]$.
The result (in Maple 16) is $[[6, 8, -7, 2, 1], [-1, -6, -6, -11, 10], [-28, 17, -8, 1, 10], [-30, -11, -93, -102, -171]]$.  The third vector $[-28, 17, -8, 1, 10]$ tells you that
$-28 x_1 + 17 x_2 - 8 x_3 + x_4$ is very near $0$ (in fact is $.000010$), so
$-28 x_1 + 17 x_2 - 8 x_3$ is nearly $-x_4 = 1$.  However, you could also use the first and second vectors, which have $a_4 = 2$ and $-11$ respectively.  Since $1 = 6 \times 2 - 11$,
we take $6 [6, 8, -7, 2, 1] + [-1, -6, -6, -11, 10] = [35, 42, -48, 1, 16]$ and find that
$35 x_1 + 42 x_2 - 48 x_3$ is very nearly $1$.  In order to write $1$ as an integer linear combination of $2$ and $-11$, we needed the fact that $\gcd(2,-11) = 1$.
A: If $b=\dfrac{p}{q}$ with $p,q \in \mathbb{Z}$ (and $q \ne 0$) then you could solve
$$x_1(qa_1) + \cdots + x_n(qa_n) - a_{n+1}p = 0$$
and then take the solutions of the form $(a_1, \cdots, a_n, 1)$.
If $b \in \mathbb{R}$ then you run into problems if you can only use integers; but if $b \in \mathbb{R}$ then I doubt somewhat that such an algorithm would work anyway!
