2
$\begingroup$

Came across this math problem while programming something:

Given positive $y$, $a$, and $b$, find an integer $x$, $a\lt x\lt b$, so that $y\bmod x$ (the remainder of $y$ when divided by $x$) is positive and less than or equal to $100$, $$0 \lt y\bmod x \leq 100.$$

I know sometimes it's not solvable depending on $y$ and the range. I'm not really sure where to begin because I wasn't very good at modular algebra.

I really don't want to have to try every possible number for $x$ between $a$ and $b$ because the range I'm using it for has over 25 million in length.

Edit: Sorry the question wasn't very clear. $y$, $a$, and $b$ are given. And I'm trying to find an $x$ that satisfies those conditions.

Edit 2: I've realize $y \bmod x$ need to be less than or equal to $100$ and also over $0$.

  • 3
    What's the actual question?2010-11-26
  • 0
    Is the question: find $x\in[a,b]$ such that $y \mod x \le 100$ ?2010-11-26

2 Answers 2

1

I'm not sure I understood your question. Let's suppose your question is the following :

Let $100=c

Here is a tentative algorithm, which is probably not optimal, but (slightly) better that trying all the possible values for $x$.

First, try the first possibility $x=a$ and perform an euclidean division to find $q$ and $r$ such that $y=qa+r$.

  • if $0
  • otherwise, divide $r$ by $q$ to find $k,l$ such that $r=kq+l$.
    • if $0
    • otherwise, increase $a$ by $k+1$ and start again from the beginning.

Of course, you stop repeating the above as soon as $a$ becomes bigger than $b$, which would mean that ther is no solution.

Edit to take into account the $0 < y \mod c$ condition

I don't think this condition change the search much, at least if you use the above algorithm. Hoxever, if you have a $z$ such that $y \mod z =0$, you can write $y=mz$, which might be helpful. For example, if $m\le c$, $x=z+1$ will be a solution.

Edit to correct for the $a+k>b$ case Edit To be more clear, the algorithm above find $k,q,l$ such that $y=(a+k)q+l$, and tries to get $l$ as small as possible (without trying too much)

  • 0
    Sorry I overlooked something in my question. y mod x needs to be less than 100 and over 0.2010-11-26
  • 0
    This algorithm doesn't work with $c = 100, a = 400, b = 505, y = 1520$. It gives me 506 as the answer which is out of the range.2010-11-27
  • 0
    OK I see the problem : I forgot to check the condition on b when trying do reduce the modulus. 505 is a solution. Actually, every integer between 474 and 505 are solutions. Do you need all the solutions, the smallest solution or any solution ?2010-11-27
  • 0
    The smallest solution would be better, since it would mean that $y mod x$ is the closest to $c$2010-11-28
  • 0
    OK, I've looked for the one with the smallest $y mod x$. To have a bigger modulus, you need to decrease $k$.2010-11-28
  • 0
    Seems to be working if I remove the $0 \lt l$ condition on the third step. What do I need to decrease if I wanna get the smallest modulus?2010-11-29
  • 0
    @this is a deas end:If you accept $l=0$, it means you accept $y\mod c=0$, which you have explicitely excluded in your question, no ?2010-11-29
  • 0
    Oh sorry. I overlooked something when testing one of the scenerios.2010-11-29
  • 0
    I found out the smallest solution is not always the best. With $c=100, a=400, b=505, y=54651835$, 409 is a solution, which gives me 28 for the remainder. But 410 is another solution and that gives me 65.2010-11-29
  • 0
    @this is a dead end: You are then in the parameter range where $y \gg b^2$ when the result in the modulus looks roughly random and you have no other choice than testing all solution (see @Ross Milikan's answer). Basically, my algorithm is useful only when the modulus is varying slowly, so that changing $x$ by does not change the quotient $y/x$. When $y$ is, the problem is much more difficult.2010-11-29
0

Your question is equivalent to asking whether any element of {y-1, y-2, $\ldots$, y-100} has a divisor in the range (a,b). So if you can factor all the 100 numbers, you can check that. Unfortunately, factoring is pretty hard and then you have the NP complete knapsack problem to solve in looking through all the factors for one that is in range.