1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I might be missing something, but you can compute $s = (c-1)/2$ and $m = (b-1)/s$ (both must be real), and then verify that $m(s+1) = a$. $\endgroup$ – Yuval Filmus Jul 16 '15 at 21:49
  • $\begingroup$ @YuvalFilmus Wow I didn't see that, thanks! $\endgroup$ – Ryan Jul 16 '15 at 21:52
  • $\begingroup$ And what would be your question? $\endgroup$ – Raphael Jul 17 '15 at 0:04
3
$\begingroup$

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). $$

$\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.