# Find a solution to congruence system $x\equiv 3\pmod{7}$ and $x\equiv 9\pmod{13}$

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?

• Have you learned about reciprocals in number theory? Sep 12 at 12:40
• $\frac{p}{q}\Rightarrow \frac{q}{p}$? Yes, I have. Sep 12 at 12:47
• For instance, what's the reciprocal of 3 mod 7? The answer is 5. Sep 12 at 13:08
• $x\equiv-4\bmod 7,13$, so $x\equiv-4\bmod 91$ Sep 13 at 14:05

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.$$

Alternative approach that piggybacks on the intermediate result from B. Goddard's answer:

$$x = 3 + 7n \equiv 9 \pmod{13}.$$

Identify, either by trial and error, or the Euclidean Algorithm, that the reciprocal of $$7 \pmod{13}$$ is $$(2)$$.

That is $$2 \times 7 \equiv 1 \pmod{13}.$$

Therefore, $$2x = 6 + [(2 \times 7) \times n] \equiv 6 + n \equiv (2 \times 9) = 18 \equiv 5 \pmod{13}.$$

Therfore, the problem reduces to solving for $$n$$ where

$$6 + n \equiv 5 \pmod{13} \implies n \equiv 12 \pmod{13}.$$

Therefore, $$x \equiv 3 + (7 \times 12) = 87 \pmod{7 \times 13}.$$

$$9-3=6$$ and $$13\equiv 6\pmod 7$$ turn $$13z+9=7a+3$$ into $$6(z+1)=7a$$ which means it has a multiple of $$42=6\cdot 7$$ just $$3$$ below it. So it's either $$45$$ or $$87$$ . And checking modulo $$13$$ shows it's $$87$$

• Needs mathjax editing. Sep 12 at 22:55
• Thanks @user2661923 stupidly missed a single dollar sign matchup Sep 12 at 22:56