2
$\begingroup$

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.

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

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.