This article is motivated by the work done for prior blog articles on splitting primes into sums of squares. Lately, I have been wanting to extend that work to compute the splitting of primes into d·a2 + b2 for arbitrary positive integers d instead of limiting myself to d equal to 2, 3, and 4. As part of that work, I found I needed to solve the following problem.
Given a positive integer b and an arbitrary rational number find an integer in the range from 1 to b - 1 (from 1 to one less than b) such that multiplying by that number will yield a number that is within 1/b of an integer, either below or above. In the practical scenario that I envision, b tends not to be that large while the rational number can have a numerator and denominator with hundreds of digits.
In the following assume % is the operator that computes the remainder after division and · represents taking the product. Then the problem posed above is equivalent to the following problem.
Given arbitrary positive integers p, q, and b with b > 2,
find a number m in the range {1..b-1} such that
if we set r = (p·m·b) % (b·q), then r ≤ q or r ≥ (b - 1)·q.
In this statement, the rational number being approximated to an integer is p over q.
The fact that such an m exists has an interesting proof, which I will not do here, I will leave it as an exercise for the reader. Our focus is on efficiently finding the m.
There are two ways to view this problem. Given a particular b, then with preparation work allowed for that b, implement an efficient algorithm for any p and q. The other approach is given any p, q, and b find a general efficient algorithm. I have had some success with the first view of the problem. For the second, I am not able to find an algorithm that is significantly faster than trying every possible multiple from 1 to b - 1.
For the first view, I have implemented a Groovy script that can be found at https://groovyconsole.dev//?gist=sampwhite/94a1657599bf049073b42156fc18b75d#MDujiDMMSL. It works well with b up to 1,000 and can be stretched to work with b up to 10,000 if you are willing to wait a few minutes. I will be incorporating this work into my next version of code that splits a prime into b times a square plus a square.
For the second view, I have been researching the problem with Google with little success. It feels like there should be some type of Euclidean algorithm style solution that will allow me to do useful computations with b greater than 10,000, but I have not found anything. The closest analogous problem I have found is on Diophantine Approximation, but that approach does not allow for multiplying by an integer as part of their construction.
Part of my struggle, which I have referenced before in prior blog articles, is coming up with the correct words to characterize the problem. Is it a real number approximating an integer problem, a problem in calculating the class group in quadratic imaginary number fields, or a prime ideal calculation problem in number fields? When I have researched these topics, either there is no interest in multiplying the input number by a small integer before approximating an integer, or the mathematics is very advanced and uninterested in algorithmic implementations.