Diophantine equation with bounded variables I was reading the follow paper about cryptography:  Fully Homomorphic Encryption over the Integers, but I faced a proof of Lemma which I didn't undestand: the Lemma A.1.
In short, there is a proposition that says that
"$x$ can be write as $p\alpha + 2\beta$."
In this expression, $p$ is a given odd  number, all the values are integers and $\alpha$ and $\beta$ are the unknowns. Normally, it should be trivially true, because the greatest common divisor between $p$ and $2$ is $1$, and $1$ divides $x$ (See Diophantine equation if you don't know why $1$ divides $x$ implies this equation has solution).
But in this case, it isn't too easy prove that proposition, because we have the follow restrictions:
$\lambda \in Z : \lambda > 0$
$p \in (2Z + 1) ∩ [2^{\lambda^2−1} , 2^{\lambda^2})$
$x = pq + r$, with $q \in Z∩[0, \frac{2^{\lambda^5}}{p})$ and $r \in Z∩(−2^\lambda, 2^\lambda)$
$\beta \in [-2^\lambda, 2^\lambda]$
So, can someone here prove or give a counter example (some values of $p$, $q$ and $r$) that for a given $x$ of the form $pq + r$ (respecting these restrictions above), we can always find values of $\alpha$ and $\beta$ (also respecting these restrictions) such that $x = p\alpha + 2\beta$ ?
I had tried it, but found nothing.
 A: Consider the equality $$pq+r = x = p\alpha + 2\beta$$
Clearly, if $r$ is even, we can simply set $\alpha=q$ and $\beta=\frac{r}{2}$. Otherwise we can rewrite it slightly and take absolute values to obtain $$p|q-\alpha| = |r-2\beta|$$
Since the right-hand side is odd, the left-hand side cannot be equal to zero. This means we have the following chain of (in)equalities:
$$2^{\lambda^2-1}\leq p\leq p|q-\alpha| = |r - 2\beta| \leq |r| + 2|\beta| < 2^{\lambda} + 2\cdot 2^{\lambda} = 3\cdot 2^{\lambda}$$
Comparing the leftmost and rightmost expression in this chain, we see it is violated by any $\lambda\geq 3$. Thus, if $\lambda \geq 3$, any valid choice of $p$ and $q$ combined with odd $r$ provides a counter-example to the claim.
A: I think the Peter Košinár's anwser is a good one (I accepted it as the correct answer), but I'm posting here the answer I found, just to make this question richer and, hopping someone discuss my solution...
So, I found a counter example to any $\lambda >= 2$, as follow:
Given a $\lambda \in Z$, such that $\lambda > 0$, take
$p = 2^{\lambda^2} - 1$ and $q = r = 1$. Then, $$x = qp + r = 2^{\lambda^2}$$
So, we have to solve this diophantine equation in $\alpha$ and $\beta$:
$$ 2^{\lambda^2} = p\alpha + 2\beta$$
Since $p$ is odd, $\gcd(p, 2) = 1$, this equation has solutions and, we now that the solutions are of the form $\alpha = \alpha_0 - 2t$ and $\beta = \beta_0 + pt$, for any $t \in Z$, where $\alpha_0$ and $\beta_0$ is any particular solution.
So, we can use $\alpha_0 = 0$ and $\beta_0 = 2^{\lambda^2 - 1}$ as this particular solution. Then, the solutions are $ \alpha = -2t$ and $\beta = 2^{\lambda^2 - 1} + pt$.
But, between these all solutions, we just want those satisfying 
$$ -2^{\lambda} \le \beta \le 2^{\lambda}$$
that is equivalent to
$$ -2^{\lambda} - \beta_0 \le \beta - \beta_0 \le 2^{\lambda} - \beta_0$$
and divinding by p
$$ \frac{-2^{\lambda} - \beta_0}{p} \le \frac{\beta - \beta_0}{p} \le \frac{2^{\lambda} - \beta_0}{p}$$
Using the fact that $t = \frac{\beta - \beta_0}{p}$ and assuming $\lambda >= 2$, we have 
$$ -1 < \frac{-2^{\lambda} - \beta_0}{p} \le t \le \frac{2^{\lambda} - \beta_0}{p} < 0$$
so, there is no integer $t$ that satisfies this inequallity, wich means that there is no solution satisfying these restrictions.
