0
$\begingroup$

I'm trying to solve the following system of equations for $p$ and $q$, given fixed integers $x$, $y$ and $c$:

$$r = {{c x + p} \over {c y + q}} \ , \, \, \, r \in \mathbb{Z}$$

where

$$\{x, y, p, q, c\} \in \mathbb{Z}$$

$$0 \leq y \lt x$$

$$0 \leq \{p, q\} \lt c$$

$$c = 2^b$$

i.e. this is a fixed point fraction $x / y$, shifted by $b$ bits, with fractional adjustment terms $p$ and $q$ on the numerator and denominator. I'm trying to solve for the values of $p$ and $q$ that make the denominator evenly divide the numerator, or I need to know when there is no solution.

There will always a solution for some integer values $p$ and $q$, just not necessarily within the range $\left[0, c\right)$.

Often there is more than one solution. I am much more interested in knowing when there are no solutions than when there are one or more solutions, so if there is no easy way to find or enumerate solutions, but there's a way to quickly (ideally in $\mathrm O(1)$) determine when there are no solutions, it would solve my problem.

I have a feeling this is not a "fullblown" Diophantine equation problem, and that there's some nice simple trick involving modulo arithmetic or remainders, but I haven't been able to find it.

$\endgroup$

1 Answer 1

1
$\begingroup$

[Answering my own question]: I realized that there are no integer solutions $r$ when

$$\lfloor r_{MAX} \rfloor > \lfloor r_{MIN} \rfloor\,,$$ where the min and max values are defined by the range of $p$ and $q$, i.e. when

$$\left\lfloor {cx + c - 1 \over {cy + 0}} \right\rfloor > \left\lfloor {cx + 0 \over {cy + c - 1}} \right\rfloor$$

because if $(r_{MIN},r_{MAX})$ does not span an integer boundary, there can be no integer solutions for $r$.

This is not the full answer that would generate actual values for $p$ and $q$ that give a whole-numbered result $r$, but it solves the most useful part of the question for my current needs, which is to determine when such a solution cannot exist.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .