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$
3
  • $\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$ Jul 16, 2015 at 21:49
  • $\begingroup$ @YuvalFilmus Wow I didn't see that, thanks! $\endgroup$ Jul 16, 2015 at 21:52
  • $\begingroup$ And what would be your question? $\endgroup$
    – Raphael
    Jul 17, 2015 at 0:04

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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