Diophantine equation with bounded variables

Question

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.

Answer 1

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.

Answer 2

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.