Sunday, April 16, 2017

elementary number theory - Chinese Remainder Theorem Transformation with not coprime moduli


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?

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...