# Exercises - Linear Congruences

1. Suppose $a_1 \equiv b_1 \pmod{m}$ and $a_2 \equiv b_2 \pmod{m}$. Prove the following:

1. $a_1 + a_2 \equiv b_1 + b_2 \pmod{m}$
2. $a_1 - a_2 \equiv b_1 - b_2 \pmod{m}$
3. $a_1 a_2 \equiv b_1 b_2 \pmod{m}$
2. Prove that if $ac \equiv bc \pmod{m}$ and $\gcd(c,m)=1$, then $a \equiv b \pmod{m}$.

3. Find all incongruent solutions to the following:

1. $7x \equiv 3 \pmod{15}$
2. $6x \equiv 5 \pmod{15}$
3. $x^2 \equiv 1 \pmod{8}$
4. $x^2 \equiv 2 \pmod{7}$
5. $x^2 \equiv 3 \pmod{7}$
4. Use congruences to prove the following divisibility tests for 4, 8, 3, 9, and 11 work.

1. A number is divisible by 4 if its last two digits yield a number divisible by 4
2. A number is divisible by 8 if its last three digits yield a number divisible by 8
3. A number is divisible by 3 if the sum of its digits is divisible by 3
4. A number is divisible by 9 if the sum of its digits is divisible by 9
5. A number whose digits are given by $d_n ... d_3 d_2 d_1 d_0$ is divisible by 11 if $d_0 - d_1 + d_2 - d_3 + \cdots + (-1)^n d_n$ is divisible by 11
5. Solve the following linear congruences

1. $8x \equiv 6 \pmod{14}$
2. $66x \equiv 100 \pmod{121}$
3. $21x \equiv 14 \pmod{91}$
6. Determine the incongruent solutions, if they exist, for each of the following:

1. $72x \equiv 47 \pmod{200}$
2. $4183x \equiv 5781 \pmod{15087}$
3. $1537x \equiv 2863 \pmod{6731}$

◆ ◆ ◆