Solve modulus with constraints for multiple equations

Question

I'm trying write a program to solve equations from the following form:

$$ \begin{align} a \bmod x &= t_1 \\ b \bmod x &= t_2 \\ \end{align} $$

where $a$, $b$, $t_1$ and $t_2$ are known values.

I have multiple equations of the same form and I'd like to solve them for $x$. Assuming I have constraints on $t_1$ and on $t_2$ for some constant $C$:

$$ \begin{align} 0 \le t_1 \lt C \\ 0 \le t_2 \lt C \\ \end{align} $$

e.g : for $a=150$, $b=50$, $t1=2$, $t_2=1$: $$ \begin{align} 150 \bmod x &= 2 \\ 50 \bmod x &= 1 \\ 1, 2 \lt 5 \\ \end{align} $$

What would be the most efficient way to program such a thing?

Answer 1

As user8962 explains, an equation of the form $a \pmod{x} = b$ is equivalent to $x | a-b$ and $x > b$. Now suppose you have equations $a_i \pmod{x} = b_i$ for $i=1,\ldots,n$. You first compute $g = \gcd(a_1-b_1,\ldots,a_n-b_n)$ (you do that iteratively: $\gcd(x,y,z) = \gcd(\gcd(x,y),z)$ and so on); we know that $x$ is a divisor of $g$ satisfying $x > B = \max_{i=1}^n b_i$. If $B \geq g$ then there is no solution. Otherwise, $g$ is one solution, and there may be other solutions: all divisors of $g$ larger than $B$.

In your example, $150 \pmod{x} = 2$ and $50 \pmod{x} = 1$. So $g = \gcd(150-2,50-1)=1$ and $B = \max(2,1) = 2$, and since $B \geq g$ there is no solution.

Answer 2

Expand the equivalences $150 \equiv 2 \pmod{x}$, $50 \equiv 1 \pmod{x}$ into $150 = 2 + k_1 x$, $50 = 1 + k_2 x$ for some integers $k_1, k_2$ and deduce that $148 = k_1 x, 49 = k_2 x$. There is no integer solution since $\gcd(148, 49) = 1$. But (for example; another system) if you replace $150$ with say $65$, then you have $\gcd(49, 63) = 7$. Since $x$ must be $> t_1, t_2$ (or your given upper bound on $t_1, t_2$), we can set $x = 7$ (or other factors of the gcd which satisfy the aforementioned conditions). You can probably turn this into an algorithm. The dominant cost is gcd computation.