# Clever way to find zero remainder with decreasing divisor

I need to factorize a number starting from an initial divisor and going down by $$1$$ at each step. For example, starting from $$99$$ and decreasing it one by one

$$9779 = 99 \times 98 + 77$$ $$9779 = 98 \times 99 + 77$$ $$9779 = 97 \times 100 + 79$$ $$\vdots$$ $$9779 = 77 \times 127 + 0$$

I reach the zero remainder after $$23$$ steps.

I was wondering if there is a clever way to "predict" the first null remainder given the first division(s). I saw this question but mine has a particular pattern so maybe there is a better solution than brute force.

Thanks a lot

• Well, you can certainly jump two each time if looking for factors of an odd number as they'll never be even Dec 23, 2019 at 16:25
• Aren't you just asking for the largest divisor of the number less than 100? Dec 23, 2019 at 16:26
• You could do trial division by only using the primes. If you have completed the factorization, you can easily find all divisors. Knowing that $1001$ is divisible by $7$ and $11$ here gives immediately two prime divisors. Dec 23, 2019 at 16:26
• In the end , it simply depends upon the number you choose as the starting value . If you would have started at $150$ , it would take you $24$ steps to reach to the first divisor , i.e $127.$ Dec 23, 2019 at 16:27
• Why do you start with 99? Dec 23, 2019 at 16:29