Finding the existatnce of solution for CRT like congurences

47 Views Asked by At

Problem

There exists a number such that it consists of two components and can be expressed as a sequence: $$ N=n(a_{0}+a_{1})+a_{1},n∈ \mathbb{N} $$ The task is to find a smallest value of N for a system of congruences as such: $$ a = \{a_{0}, a_{1} \}, \space b = \{b_{0}, b_{1} \}, \space c = \{c_{0}, c_{1} \} \\~\\ f(a,b,c)= N, where \begin{cases} N=n_{0}(a_{0}+a_{1})+a_{1} \\ N=n_{2}(b_{0}+b_{1})+b_{1} \\ N=n_{1}(c_{0}+c_{1})+c_{1} \\ \end{cases} $$ Notice, any $ n $ is unknown. This problem is related to CRT, LCM and GCD. I am aware of that.

Question

The problem lies in the fact that values of $ a_{1}, b_{1}, c_{1} $ can be $ 0 $ and co-prime. I have an algorithm which already calculates N based on these criteria. However, I have a problem with efficiently figuring out if a system has no solutions. For example $$ \begin{array}{lcl} f( \{70,5\}, \{160,3\}) & = & 4370 \\ f( \{70,5\}, \{160,3\}, \{101,2\} ) & = & 237005 \\ f( \{70,5\}, \{160,3\}, \{108,2\} ) & = & No \space solution \\ \end{array} $$ My question is whether there exists an efficient method of figuring out whether the solution exists for $ f(a,b,c,d,e ...) = N $ without needing to iterate through very large numbers.