1
$\begingroup$

Find a number $x$ such that:

$x \equiv 1 \mod m$ for $m = 2$ to $18$

$x \equiv 0 \mod 19$

I think the problem can be solved using Chinese Remainder Theorem, but the theorem requires all modulos to be pairwise coprime. Here, the modulos ($2$ to $19$) are not pairwise coprime.

Is there any general procedure to create a subset of pairwise coprime modulos which will give the value of $x$?

Will this procedure work for all problems of the form given below?

Find a number $x$ such that:

$x \equiv a \mod m$ for finite given pairs of "$a$" and "$m$"

$\endgroup$
0
$\begingroup$

In general the system of congruence relation doesn't have to have a solution if the moduli aren't coprime. Anyway here's a way how to solve the system then. Decompose the composite moduli into power of primes. In your example you can write:

$$x \equiv 1 \pmod {12} \iff \left\{ \begin{array}{c} x \equiv 1 \pmod 4 \\ x \equiv 1 \pmod 3 \end{array} \right. $$

Now if you obtain a contradiction, like having an equation $x \equiv 3 \pmod 4$ in your system you can conclude that the system has no solution. Also note that the equation $x \equiv a \pmod{p^k} \implies x \equiv a \pmod{p^{k-1}}$, so we can get rid of the smaller powers of a prime if there's no contradiction as above. Hence we can rewrite the above system as:

$$\left\{ \begin{array}{c} x \equiv 1 \pmod {16} \\ x \equiv 1 \pmod 9 \\ x \equiv 1 \pmod 5 \\ x \equiv 1 \pmod 7 \\ x \equiv 1 \pmod {11} \\ x \equiv 1 \pmod {13} \\ x \equiv 1 \pmod {17} \\ x \equiv 0 \pmod {19} \\ \end{array} \right.$$

This one can be solved using the CRT.

$\endgroup$
3
$\begingroup$

In this case there is a shortcut. Choose $x = 18! + 1$ and note that $19 \mid x$.

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