Here's my problem. I have to find the sum of 123456 and 987456 using chinese remainder theorem with least moduli. We know sum = 123456+987456=1,110,912. Let me assume that we have to use n number of moduli m1,m2,...mn(pairwise relatively prime to represent the integers as n tuple). Eg: If I assume m1=99,m2=98,m3=97,m4=95 then (123456)=(3,74,72,51). Similarly for 987456 and the sum. I also know that sum < m1m2m3*m4. And I get system of linear congruences. Now my question is basically how to find the m1...mn which are pairwise and also the smallest combination possible (unique) so that it is just greater than the sum. Eg: I could have also taken m1=81,m2=83,m3=85,m4=89 that satisfies the above condition. Surely there are other combinations as well. Is there any theorem where can I find smallest number of moduli such that I don't have to do hit and trial to search for moduli as it is very time consuming? Here's one example of such problem in the book Discrete maths by Rosen. Using chinese remainder theorem to do large integer arithmetic
In the book , it basically tells us to do with moduli 99,98,97,95. However it gives no idea about how to find smallest combination of moduli we can take.
You probably need Method 4. Giving other methods as well.
Method 1:
First, there are infinitely many primes. So, we can always find primes greater than the sum $a+b$ where $a = 123456$ and $b = 987456$ as given.
It so happens $1110913, 1110917, 1110919, 1110929, 1110931, \cdots$ are all greater than $a+b$ and are prime. Coincidentally, $1110913 = a+b+1$.
Similarly, we have $2, 3, 5, \cdots, 1110859, 1110881, 1110887$ as primes less than $a+b$. If we take $\{2,1110887\}$ as the moduli, the sum will lie within the range $(0, 2 \times 1110887-1)$.
Method 2:
Another way is to construct the modulii set by taking successive numbers and taking them into the modulii set only if it is relatively prime to the running product of the items in the modulii set.
For e.g., You start with $\{2\}$. Then check the numbers $3,4,5,\cdots$ to see if they are relatively prime. You can do this using the GCD algorithm. $\gcd(3,2)=1$. So, we add that to our set which is now $\{2,3\}$ and the running product is $6$ which is less than $a+b$. If we continue this way, we will get $\{2, 3, 5, 7, 11, 13, 17, 19\}$. The product upto $17$ is $510510$ and upto $19$ is $9699690$ and our sum $a+b$ lies in this range. So, this modulii set will work.
Method 3:
The set we constructed has small primes. If we want small primes and the size of the set to also be small, one way to do that would be to remove smaller primes whose product is lesser than the largest prime in the set. For eg: when $7$ was added to the set, $2,3$ can be removed since $2\cdot 3 \lt 7$. So the set is $\{5,7\}$. We can continue building the set this way.
Method 4:
Another way is to use the inequality
$$ p < \lfloor \sqrt{a+b} \rfloor < \lfloor \sqrt{pq} \rfloor < q < a+b < pq $$
We start with $\lfloor \sqrt{a+b} \rfloor$ and then search for primes in its neighborbood (both below and above). The first such primes are $p$ and $q$ respectively and $\{p,q\}$ will be small and the size of the set is just $2$. No other set of size $2$ exists with the product being less than this $pq$.
If you want primes, you need a primality test for checking the candidates.
You don't need primes, just relatively prime integers. So, the search can be done using successive values and checking for coprimality using the GCD algorithm which is very fast [$O(\log n)$]. Rest of it remains same.