I'm stuck with following problem and would need some help:
Express the following congruence system as a single congruence equation
$$
x\equiv 3\pmod{7}\\x\equiv 9\pmod{13}
$$
i.e.
$$
x\equiv a\pmod{b}
$$
With the Chinese remainder theorem I have found that
$$
x\equiv a\pmod{91},
$$
where $1\le a\le 91$. I know the answer too, $a=87$, i.e.
$$
x\equiv 87\pmod{91}
$$
It can be solved either with intuition or testing all numbers from 1 to 91. However, I have to find solution to this algebraically, not intuitively, in which I have not been very successful. So, is there someone able to come up with the steps to the correct solution?
Best Answer
You know that $x \equiv 3 \pmod{7}$, so $x=3+7n$ for some $n$. Plug that into the other congruence and solve:
$$3+7n \equiv 9 \pmod{13}$$
$$7n\equiv 6 \pmod{13}$$
$$n \equiv 14n \equiv 12 \equiv -1 \pmod{13}$$
So $n = -1 +13k$ for some $k$. Put that in the first equation:
$$x = 3 + 7(-1+13k) = -4 + 91k.$$
The last expression represents all solutions. Take $k=1$ and you get $87.$