0
$\begingroup$

Suppose that $x \equiv 3 \pmod 7, x \equiv 3 \pmod {10}$ and $x \equiv 23 \pmod{25}$. Explain why the Chinese Remainder Theorem does not apply to compute x. Transform the problem to an equivalent problem where the Chinese Remainder Theorem can be used and solve it.

The question is unsolvable before transformation because the theorem requires modular numbers to be relatively prime to each other and $\gcd(10,25)=5$ so they are not relatively prime. How do I transform it and solve it?

$\endgroup$
  • $\begingroup$ Please read this text about how to ask a good question. $\endgroup$ – José Carlos Santos Nov 25 '17 at 10:37
  • $\begingroup$ You can apply the CRT because here $\gcd(7,10,25)=1$ so you just have to build the right $x$ using an interesting Bézout relation ! $\endgroup$ – Maman Nov 26 '17 at 13:22
1
$\begingroup$

Note that you can write $x \equiv 3 \pmod {10}$ as system of two equations namely $x \equiv 3 \pmod{5}$ and $x \equiv 3 \pmod{2}$. But note that the first first equation is already contained in $x \equiv 23 \pmod{25}$, so it's redundant. Therefore we have:

$$ \begin{cases} x \equiv 3 \pmod 7 \\ x \equiv 3 \pmod {10} \\ x \equiv 23 \pmod{25} \end{cases}\iff \begin{cases} x \equiv 3 \pmod 7 \\ x \equiv 3 \pmod {2} \\ x \equiv 3 \pmod {5} \\ x \equiv 23 \pmod{25} \end{cases}\iff \begin{cases} x \equiv 3 \pmod 7 \\ x \equiv 3 \pmod {2} \\ x \equiv 23 \pmod{25} \end{cases}$$

Now solving the system on the right is just a simple application of Chinese Remainder Theorem.

$\endgroup$
  • $\begingroup$ why is it already implied by? $\endgroup$ – james black Nov 25 '17 at 22:29
  • $\begingroup$ If $x\equiv 23 \pmod{25}$ then $x\equiv 23 \equiv 3 \pmod{5}$ $\endgroup$ – Stefan4024 Nov 25 '17 at 22:32
1
$\begingroup$

The idea is to find modulo the highest powers of distinct primes

$x\equiv3\pmod{10}\implies x\equiv3\pmod2\ \ \ \ (1)$

and $x\equiv3\pmod5$

which is already implied by $$x\equiv23\pmod{25}$$

$\endgroup$
  • $\begingroup$ why is it already implied by? $\endgroup$ – james black Nov 25 '17 at 22:29

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.