Solve the following congruence equations:
(a) $3x ≡ 1 \pmod 5$
(b) $4x ≡ 2 \pmod 7$
(c) $7x ≡ 0 \pmod 8$
(d) $10x ≡ 5 \pmod {13}$
(e) $8x ≡ 4 \pmod {15}$
(f) $9x ≡ 10 \pmod {16}$
We will use Proposition (3.15) which says the linear congruence $ax ≡ b \pmod n$ has a solution if and only if $g \mid b$ where $g= \gcd (a, n)$. In addition, Proposition (3.16) says there are exactly $g$ solutions, if they exist.
(a) $\gcd(3,5)=1$, and $1 \mid 1$, so a solutions exists, and there is only one.
$3x \equiv 1 \pmod 5$ means $3x = 1 + 5y$ for some integer $y$. Rewriting $x = \frac{1+5y}{3}$. To ensure integer $x$, we can't have $y=0$, however $y=1, x=2$ works. Since there is only one solution, we don't need to find any more pairs of $x,y$.
So the solution is $$x \equiv 2 \pmod 5$$
(b) $\gcd(7,4)=1$ and $1\mid 2$, so a solution exists, and there is only one.
$4x \equiv 2 \pmod 7$ means $4x = 2 + 7y$ for some integer $y$. The pair $y=2, x=4$ is an integer solution. Since there is only one solution, we don't need to find anymore parts of $x,y$.
So the solution is $$x \equiv 4 \pmod 7$$
(c) $\gcd(7,8)=1$ and $1 \mid 0$, so a solution exists, and there is only one.
By inspection the solution is $$x \equiv 0 \pmod 8$$
(d) $\gcd(13,10) = 1$ and $1 \mid 5$, so a solution exists, and there is only one.
$10x \equiv 5 \pmod {13}$ means $10x = 5 + 13y$ for some integer $y$. The pair $y=5, x=7$ is an integer solution. Since there is only one solution, we don't need to find more.
So the solution is $$x \equiv 7 \pmod {13}$$
(e) $\gcd(15, 8) =1$ and $1 \mid 4$, so a solution exists, and there is only one.
$8x \equiv 4 \pmod {15}$ means $8x = 4 + 15y$ for some integer $y$. The pair $y=4, x = 8$ is an integer solution. Since there is only one solution, we don't need to find more.
So the solution is $$x \equiv 8 \pmod {15}$$
(f) $\gcd(16,9)=1$ and $1 \mid 10$, so a solution exists, and there is only one.
$9x \equiv 10 \pmod {16}$ means $9x = 10 + 16y$ for some integer $y$. The pair $y = 5, x= 10$ is an integer solution. Since there is only one solution, we don't need to find more.
So the solution is $$x \equiv 10 \pmod {16}$$