# Question on application of Chinese Remainder Theorem x <mspace width="thickmathspace" />

Semaj Christian 2022-06-26 Answered
Question on application of Chinese Remainder Theorem
$x\phantom{\rule{thickmathspace}{0ex}}\equiv \phantom{\rule{thickmathspace}{0ex}}3\phantom{\rule{thickmathspace}{0ex}}\left(\text{mod}\phantom{\rule{thickmathspace}{0ex}}30\right)$
$x\phantom{\rule{thickmathspace}{0ex}}\equiv \phantom{\rule{thickmathspace}{0ex}}5\phantom{\rule{thickmathspace}{0ex}}\left(\text{mod}\phantom{\rule{thickmathspace}{0ex}}56\right)$
I have a system of modular equation that I want to solve. However, I thought that this system has no solution because the modulos are not coprime. Further, attempting to solve using chinese remainder theorem:
$x\phantom{\rule{thickmathspace}{0ex}}\equiv \phantom{\rule{thickmathspace}{0ex}}56p\phantom{\rule{thickmathspace}{0ex}}+\phantom{\rule{thickmathspace}{0ex}}30q$
where $p$ is such that
$56p\phantom{\rule{thickmathspace}{0ex}}\equiv \phantom{\rule{thickmathspace}{0ex}}3\phantom{\rule{thickmathspace}{0ex}}\left(\text{mod}\phantom{\rule{thickmathspace}{0ex}}30\right)\phantom{\rule{thickmathspace}{0ex}}$
and $q$ is such that
$30q\phantom{\rule{thickmathspace}{0ex}}\equiv \phantom{\rule{thickmathspace}{0ex}}5\phantom{\rule{thickmathspace}{0ex}}\left(\text{mod}\phantom{\rule{thickmathspace}{0ex}}56\right)\phantom{\rule{thickmathspace}{0ex}}$
However, again the modular inverses of these do not exist.
Yet, one solution to this system of modular inequalities is 1293. How come the Chinese remainder theorem gives that no solution exists?
You can still ask an expert for help

## Want to know more about Inequalities systems and graphs?

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Govorei9b
Better if you write it as
$x\equiv 3\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}2\right),$
$x\equiv 3\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}15\right),$
$x\equiv 5\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}8\right),$
$x\equiv 5\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}7\right).$
The ones with 2 and 8 are consistent, as the one with 2 is just asking for an odd number, so the system is equivalent to
$x\equiv 3\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}15\right),$
$x\equiv 5\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}8\right),$
$x\equiv 5\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}7\right),$
where now the moduli are coprime. That is the requirement for the Chinese Remainder Theorem.
So we combine second and third again to get
$x\equiv 3\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}15\right),$
$x\equiv 5\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}56\right).$
For the 56 one, we have
$5,61,117,173,229,285,341,397,453,\dots$
and
$453\equiv 3\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}15\right).$
###### Did you like this example?

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee