I'm starting to learn some elementary number theory and i came across a task i don't know how to solve.

$$x \equiv 5 (mod \ 6)$$ $$x \equiv A (mod \ 35)$$

and the second one

$$x \equiv A (mod \ 10)$$ $$x \equiv 14(mod \ 21)$$

If i'm thinking in good way then we have to find such A's that we get same solution x for both systems. It reminds me about chinese remainder theory because 6 and 35 are relatively prime and 10 and 21 are too. But i have no idea how to use those facts to solve this problem.
I'd be really happy to know how to deal with such tasks. Cheers!


Hint $\ $ Using CRT to reduce each system to equivalent systems mod primes we obtain

$\ \ x \equiv\ 1\pmod{2},\ x\equiv 2\pmod 3,\ x\equiv A\pmod 5,\ x\equiv \color{#c00}A\pmod 7\ $ is equivalent to the $1$st. $\ \ x \equiv \color{#c00}A\pmod{2},\ x\equiv 2\pmod 3,\ x\equiv A\pmod 5,\ x\equiv\ 0\pmod 7\ $ is equivalent to the $2$nd.

Thus the two systems are equivalent $\iff \color{#c00}A \equiv\, \ldots$

  • $\begingroup$ If i'm thinking in right direction, only possible A's are that $2|A-1$ and $7|(x-A)$ and those two makes: A must be odd and A must be a multiply of 7, am i right? $\endgroup$ – Krzysztof Lewko May 13 '14 at 19:00
  • $\begingroup$ @Chris The $2$nd should be $\, 7\mid 0 -A,\, $ so we reduce to solving $\, \color{#c00}A\equiv 1\pmod 2,\ \color{#c00}A\equiv 0\pmod 7 $ $\endgroup$ – Bill Dubuque May 13 '14 at 19:03

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.