Example

$\require{AMSsymbols}$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}$

  1. We could use the Euclidean Algorithm here, but playing around with the congruences gets us to the solution faster...

    $$\begin{align} 7x &\equiv 3 \pmod{15} \quad \textrm{now multiply both sides by 2}\\ 14x &\equiv 6 \pmod{15} \quad \textrm{which is nice as } 14 \equiv -1\\ -x &\equiv 6 \pmod{15} \quad \textrm{now multiply by -1}\\ x &\equiv -6 \pmod{15} \quad \textrm{now add 15 to -6}\\ x &\equiv 9 \pmod{15} \end{align}$$
  2. Consider the implications...

    $$\begin{align} 6x \equiv 5 \pmod{15} &\Rightarrow 6x - 5 = 15n \quad \textrm{for some integer $n$}\\ &\Rightarrow 6x - 15n = 5\\ &\Rightarrow 3(2x - 5n) = 5\\ &\Rightarrow 3 \mid 5 \end{align}$$

    This clearly contradicts what we know to be true (i.e., that $3 \nmid 5$). Hence, this linear congruence has no solution.

  3. We can solve this by exhaustively examining every possible remainder $\pmod{8}$:

    $$\begin{array}{c|c} x & x^2 \pmod{8}\\\hline 0 & 0\\ 1 & 1\\ 2 & 4\\ 3 & 1\\ 4 & 0\\ 5 & 1\\ 6 & 4\\ 7 & 1 \end{array}$$

    ...which yields $x \equiv 1, 3, 5, \textrm{ or } 7 \pmod{8}$

  4. We can solve this by exhaustively examining every possible remainder $\pmod{7}$:

    $$\begin{array}{c|c} x & x^2 \pmod{7}\\\hline 0 & 0\\ 1 & 1\\ 2 & 4\\ 3 & 2\\ 4 & 2\\ 5 & 4\\ 6 & 1 \end{array}$$

    ...which yields $x \equiv 3 \textrm{ or } 4 \pmod{8}$

  5. We can solve this by exhaustively examining every possible remainder $\pmod{7}$:

    $$\begin{array}{c|c} x & x^2 \pmod{7}\\\hline 0 & 0\\ 1 & 1\\ 2 & 4\\ 3 & 2\\ 4 & 2\\ 5 & 4\\ 6 & 1 \end{array}$$

    Notice, $x^2 \pmod{7}$ is never 3. Hence, $x^2 \equiv 3 \pmod{7}$ has no solution.