2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.