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

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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