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?
Solve modulus with constraints for multiple equations
algorithms;computer algebra
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.