## Exercises - Primality Testing and Carmichael Numbers

1. Solve the system of congruences: $$\begin{array}{rcl} x \equiv 6\pmod{7}\\ x \equiv 4\pmod{8} \end{array}$$

By the first congruence, $x = 7k+6$ for some integer $k$. Substituting this into the second congruence leads to $7k+6 \equiv 4\pmod{8}$, and then $7k \equiv -2\pmod{8}$.

Solving this in the usual way (Euclidean Algorithm and "back-solving"), we find $k \equiv 2\pmod{8}$. So $k = 8m+2$ for some integer $m$. Substituting this back into the equation for $x$ above, we have $x = 7(8m+2)+6$ which simplifies to $x = 56m + 20$. Thus,

$$x \equiv 20\pmod{56}$$

2. Solve the system of congruences: $$\begin{array}{rcl} 2x \equiv 5\pmod{7}\\ 3x \equiv 4\pmod{8} \end{array}$$

$$x \equiv 20\pmod{56}$$

3. Solve the system of congruences: $$\begin{array}{rcl} x \equiv 3\pmod{4}\\ x \equiv 0\pmod{6} \end{array}$$

There are no solutions, as the first implies $x$ is odd, the second that $x$ is even.

4. Solve the system of congruences: $$\begin{array}{rcl} x \equiv 2\pmod{5}\\ x \equiv 3\pmod{7}\\ x \equiv 10\pmod{11} \end{array}$$

$x \equiv 87\pmod{385}$

5. Solve the system of congruences: $$\begin{array}{rcl} 2x \equiv 6\pmod{14}\\ 3x \equiv 9\pmod{15}\\ 5x \equiv 20\pmod{60} \end{array}$$

$x \equiv 388\pmod{420}$

6. Solve the system of congruences: $$\begin{array}{rcl} x \equiv 3\pmod{8}\\ x \equiv 7\pmod{12} \end{array}$$

Note the moduli are not relatively prime. Can you figure out what $x$ would be$\pmod{8}$ and$\pmod{3}$?