Complexity of finding these original parameters

Question

I am given (or rather, generate randomly) three positive integers $a, b, c$. I want to know if there exist integers $m \ge 2, s \ge 1$ such that $ms+m = a, ms+1 = b, 2s+1 = c$. If there are multiple solutions, I want the minimal (if possible).

It is clear that $c$ has to be odd, so if $c$ given to me is not, then I can immediately stop the computation. However, I'm not sure what other cases there can be.

Also, I'm not sure if there is a better alternative than the following (or even brute-force): let $d = \min(a, b, c)$, and have $m, s$ be roughly $\sqrt{d}-m$, and try brute-force starting from there.

Answer 1

You can compute $m,s$ from the equations: $s = (c-1)/2$ and $m = (b-1)/s$; both must be integral. You can then check that indeed $m(s+1) = a$. If this holds, then you have found the unique solution $m,s$, otherwise there is no solution. More generally, this method allows you to find the unique real solution to your system of equations, if any exists.

Note that $m = (b-1)/s = 2(b-1)/(c-1)$. Hence $s,m$ are integers if $s$ is odd and $c-1$ divides $2(b-1)$. If they are integers, the final equation is satisfied if $$ a = ms + m = b-1 + \frac{2(b-1)}{c-1} = (b-1) \frac{c+1}{c-1}. $$ Another way to state this condition is $$ a(c-1) = (b-1)(c+1). $$