What are the solution for this system?

Question

I have a congruence system of equations :

$a\equiv-1\pmod 7$

$a\equiv0\pmod{13}$

what are the possible values for $a$ knowing that $a\in \mathbb{Z}$.

i tried to put $13k$ in the first equation and solve for $k$ but i get stuck.

Answer 1

You want to solve

$$\begin{align} a\equiv-1&\pmod 7 \\ a\equiv0&\pmod{13}. \end{align}$$

To do this, we will analyze what these mean in turn. $a \equiv -1 \bmod 7$ means that $7 \mid (a+1)$, or that $a = 7n -1$ for some $n$. Let's take this to the next congruence equation.

$a = 7n-1 \equiv 0 \bmod 13$, or that $7n \equiv 1 \bmod 13$. What does this make $n$? It means that $n \equiv 2 \bmod 13$ (because it's the inverse of $7 \bmod 13$). So $n = 2 + 13m$ for some $m$. Putting this back into our $a$ expression, we see that $a = 7(2 + 13m) - 1 = 13 + 91m$, or equivalently that $a \equiv 13 \bmod 91$.

Let's go back and check. $13 \equiv 0 \bmod 13$, so that's good, and $13 \equiv -1 \bmod 7$, so it all works out. Thus $a \equiv 13 \bmod 91$ is the solution.

Aside: In the comments, the Chinese Remainder Theorem was mentioned. The Chinese Remainder Theorem is a statement about these solutions, when they exist, and how many there are. I wrote a post on the Chinese Remainder Theorem for my students one summer which you might appreciate.