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

  • 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 be 4 given integers, how to find $x$ such that $ a\le x \le b \text{ and } y \mod x \le 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, $x=a$ and you're done
  • otherwise, divide $r$ by $q$ to find $k,l$ such that $r=kq+l$.
    • if $0, $x=a+k$ is your solution if it is in $[a,b]$. If not, try $b$. If $b$ is not a solution either, then tere is no solution.
    • 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
    @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.