# Finding the lowest number (or an upper bound to the lowest number) not congruent to a set of moduli

Note: if finding x is not possible, an upper bound, where there must be at least one number less than said number which is not congruent to the set, would be helpful.

The set:

For my purposes, the set is quite specific. It will contain, as moduli, only primes. The moduli must start with 5 and continue on, in the order of the primes, until the last prime included in the set ($p_n$) is reached. For each prime, there will be 2, non-zero, remainders which are distinct, meaning the two remainders for 5 can't be 1 and 6, since those have described the same residues.

Essentially:

Find a the number (x) which is not congruent to: $$r_1 \pmod{5}$$ or $$r_2 \pmod{5}$$ or $$r_3 \pmod{7}$$ or $$r_4 \pmod{7}$$ $$......$$ or $$r_{2n} \pmod{p_n}$$ or $$r_{2n+1} \pmod{p_n}$$

I've tried to apply the Chinese Remainder Theorem, but I couldn't manipulate it to seek numbers which are not congruent to a set of congruences.

I think you could use the chinese remainder theorem to a find a number which is congruent to one of the remainders for every prime, and then add or subtract a number, which will change each of the remainder, but you would have to be careful to not make it hit the other remainder for the prime. And I think that number would be quite high.

Thanks.

• As noted elsewhere, the trivial bound is the product of the moduli. Improving on it is, in general, not easy. – Gerry Myerson Aug 17 '14 at 5:13

Since you are aware of the Chinese remainder theorem, you can always find a solution which is smaller than $5\cdot 7\cdots p_n$

(Just to mention: the number $0$ is always the smallest solution to your problem)

Just choose a specific remainder $r_i$ different from the two ones given at the beggining for every prime $p_i$ and search for the number $X\equiv r_i \ (mod p_i)$ for every prime moduli.

If you want an algorithmic solution:
Suppose that the primes are $p_1,....p_n$ with $p_1=5,p_2=7$ and the two remainders you want to avoid are $r_{i_1},r_{i_2}$(with respect to every prime $p_i$)
Then apply the Chinese Rem.theorem to find the number $X\equiv r_{i_1}+ r_{i_2} \ (mod p_i)$ for all $i=1,2,...,n$
Because the remainders are nonzero it is easy to see that $r_{i_1}+ r_{i_2}\neq r_{i_1}$ and $r_{i_1}+ r_{i_2}\neq r_{i_2}$

For example if you have $3$ primes : $5,7,11$ and you want to find a number which is not congruent to : $2 , 3\ (mod5)$ and $1 , 4\ (mod7)$ and $3 , 6\ (mod11)$ then find the least number $X$ with the property:
$X\equiv2 + 3\ (mod5)\Rightarrow X\equiv0\ (mod5)$
$X\equiv 1 + 4\ (mod7)\Rightarrow X\equiv 5\ (mod7)$
$X\equiv 3+6\ (mod11)\Rightarrow X\equiv 9\ (mod11)$

We then can find that $X=75$.