Exercises - Linear Congruences

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

$a_1 + a_2 \equiv b_1 + b_2 \pmod{m}$
$a_1 - a_2 \equiv b_1 - b_2 \pmod{m}$
$a_1 a_2 \equiv b_1 b_2 \pmod{m}$

First note, as a beginning to each of the following arguments, $a_1 \equiv b_1 \pmod{m}$ implies $b_1 = a_1 + mk_1$ for some integer $k_1$, while $a_2 \equiv b_2 \pmod{m}$ implies $b_2 = a_2 + mk_2$ for some integer $k_2$.

Now consider the following:

$\displaystyle{\begin{align} b_1 + b_2 &= (a_1 + mk_1) + (a_2 + mk_2)\\ &= (a_1 + a_2) + m(k_1 + k_2)\\ \end{align}}$

which implies $a_1 + a_2 \equiv b_1 + b_2 \pmod{m}$
$\displaystyle{\begin{align} b_1 - b_2 &= (a_1 + mk_1) - (a_2 + mk_2)\\ &= (a_1 - a_2) + m(k_1 - k_2)\\ \end{align}}$

which implies $a_1 - a_2 \equiv b_1 - b_2 \pmod{m}$
$\displaystyle{\begin{align} b_1 b_2 &= (a_1 + mk_1) (a_2 + mk_2)\\ &= a_1 a_2 + a_1 m k_2 + a_2 m k_1 + m^2 k_1 k_2\\ &= a_1 a_2 + m(a_1 k_2 + a_2 k_1 + mk_1 k_2) \end{align}}$

which implies $a_1 a_2 \equiv b_1 b_2 \pmod{m}$

Prove that if $ac \equiv bc \pmod{m}$ and $\gcd(c,m)=1$, then $a \equiv b \pmod{m}$.

Turning the given congruence into a statement about divisibility, we have: $$\begin{align} ac \equiv bc \pmod{m} &\Rightarrow m \mid bc - ac\\ &\Rightarrow m \mid c \cdot (b-a)\\ &\Rightarrow m \mid b-a \quad \textrm{ ...as $m$ and $c$ are relatively prime}\\ &\Rightarrow b \equiv a \pmod{m} \end{align}$$ QED.

Find all incongruent solutions to the following:

$7x \equiv 3 \pmod{15}$
$6x \equiv 5 \pmod{15}$
$x^2 \equiv 1 \pmod{8}$
$x^2 \equiv 2 \pmod{7}$
$x^2 \equiv 3 \pmod{7}$

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}$$
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.
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}$
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}$
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.

Use congruences to prove the following divisibility tests for 4, 8, 3, 9, and 11 work.

A number is divisible by 4 if its last two digits yield a number divisible by 4
A number is divisible by 8 if its last three digits yield a number divisible by 8
A number is divisible by 3 if the sum of its digits is divisible by 3
A number is divisible by 9 if the sum of its digits is divisible by 9
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

Solve the following linear congruences

$8x \equiv 6 \pmod{14}$

First, we translate things back into an equation form.

$8x \equiv 6 \pmod{14}$ implies $8x - 6 = 14n$ for some integer $n$. This in turn, suggests that we can write 6 as a linear combination of 8 and 14: $$8x - 14n = 6$$ By inspection, we note that the gcd of 8 and 14 is 2, so we verify that 6 is a multiple of 2, which it is. Given that these numbers are as small as they are, we could probably find one solution for $x$ and $n$ by inspection. That said, let us go through the process we would use if the numbers were much larger...

First, we will try to find a single solution to the intermediate equation: $8x_1 - 14n_1 = 2$, using the Euclidean algorithm.
$$\begin{align} 14 &= 1 \cdot 8 + 6\\ 8 &= 1 \cdot 6 + \fbox{2} \leftarrow \textrm{gcd}\\ 6 &= 3 \cdot 2 + 0 \end{align}$$
Now writing the gcd, 2, as different linear combinations, we find:
$$\begin{align} 2 &= 8 - 6\\ &= 8 - (14-8)\\ &= 2 \cdot 8 - 1 \cdot 14\\ \end{align}$$
So $x_1=2$, $n_1=1$ is a solution to $8x_1 - 14n_1 = 2$

Now we can use this to find a solution to our original equation: $8x - 14n = 6$. Simply multiply both $x_1$ and $n_1$ by 3 (since $6 = 2 \cdot 3$).

Thus $x=6$, $n=3$ is a solution to $8x - 14n = 6$

Adding the appropriate multiples to find all solutions from this one solution, we get
$$x=6+\dfrac{14}{2}k \quad \textrm{ and } \quad n=3+\dfrac{8}{2}k$$
Simplifying, we find, $x=6+7k$ and $n=3+4k$ gives all solutions to $8x - 14n = 6$

Of course, we don't really care what $n$ is, since it doesn't appear in our original congruence. Further, if we are only considering the possible values of $x \pmod{14}$, there are only two that fit the $6+7k$ form: $x \equiv 6 \textrm{ or } 13 \pmod{14}$. These are our solutions.
$66x \equiv 100 \pmod{121}$

First, we translate things back into equation form.

$66x \equiv 100 \pmod{121}$ implies $66x - 100 = 121n$ for some integer $n$. This in turn, suggests that we can write 100 as a linear combination of 66 and 121: $$66x - 121n = 100$$ However, we have a problem!

The gcd of 66 and 121 is 11, which would imply that $66x-121n$ must be a multiple of 11. More precisely, $66x-121n = 11(6x-11n)$. But this is impossible, as that would imply that 11 is also a divisor of 100, which clearly is not the case.

Consequently, there is no solution to this linear congruence.
$21x \equiv 14 \pmod{91}$

First, we translate things back into equation form.

$21x \equiv 14 \pmod{91}$ implies $14 - 21x = 91n$ for some integer $n$. This in turn, suggests that we can write 14 as a linear combination of 91 and 21:
$$21x + 91n = 14$$
By inspection, we note that the gcd of 91 and 21 is 7, so we verify that 14 is a multiple of 7, which it is. Given that these numbers are as small as they are, we could probably find one solution for $x$ and $n$ by inspection. That said, let us go through the process we would use if the numbers were much larger...

First, we will try to find a single solution to the intermediate equation: $21x_1 + 91n_1 = 7$, using the Euclidean algorithm.
$$\begin{align} 91 &= 4 \cdot 21 + \fbox{7} \leftarrow \textrm{gcd}\\ 21 &= 3 \cdot 7 + 0 \end{align}$$
We can use the above to write the gcd, 7, as a linear combination of 21 and 91 (it falls out in a single step this time):
$$7 = 1 \cdot 91 - 4 \cdot 21$$
So $x_1=-4$, $n_1=1$ is a solution to $21x_1 + 91n_1 = 7$

Now we can use this to find a solution to our original equation: $21x +91n = 14$. Simply multiply both $x_1$ and $n_1$ by 2 (since $14 = 2 \cdot 7$).

Thus $x=-8$, $n=2$ is a solution to $21x +91n = 14$

Adding the appropriate multiples to find all solutions from this one solution, we get
$$x=-8+\dfrac{91}{7}k \textrm{ and }n=2-\dfrac{21}{7}k$$
Simplifying, we find, $x=-8+13k$ and $n=2-3k$ gives all solutions to $21x +91n = 14$

Of course, we don't really care what $n$ is, since it doesn't appear in our original congruence. Further, if we are only considering the possible values of $x \pmod{91}$, there are only 7 that fit the $-8+13k$ form:
$$x \equiv 5, 18, 31, 44, 57, 70, \textrm{ and } 83 \pmod{91}$$
These are our solutions.

Determine the incongruent solutions, if they exist, for each of the following:

$72x \equiv 47 \pmod{200}$

First, we translate things back into equation form.

$72x \equiv 47 \pmod{200}$ implies $47 - 72x = 200n$ for some integer $n$. This in turn, suggests that we can write 46 as a linear combination of 72 and 200: $$72x + 200n = 47$$ However, we have a problem!

The gcd of 72 and 200 is 2, which would imply that $72x+200n$ must be a multiple of 2. More precisely, we have $72x+200n = 2(36x+100n)$. But this is impossible, as that would imply that 2 is also a divisor of 47, which clearly is not the case.

Consequently, there is no solution to this linear congruence.
$4183x \equiv 5781 \pmod{15087}$

First, we translate things back into equation form.

$4183x \equiv 5781 \pmod{15087}$ implies $5781 - 4183x = 15087n$ for some integer $n$. This in turn, suggests that we can write 5781 as a linear combination of 15087 and 4183:
$$4183x + 15087n = 5781$$
It is not clear by inspection, what the gcd of 4183 and 15087 is, so we proceed with the Euclidean algorithm to find out.
$$\begin{align} 15087 &= 3 \cdot 4183 + 2538\\ 4183 &= 1 \cdot 2538 + 1645\\ 2538 &= 1 \cdot 1645 + 893\\ 1645 &= 1 \cdot 893 + 752\\ 893 &= 1 \cdot 752 + 141\\ 752 &= 5 \cdot 141 + \fbox{47} \leftarrow \textrm{gcd}\\ 141 &= 3 \cdot 47 + 0 \end{align}$$
This tells us that the gcd of 4183 and 15087 is 47, so we verify that 5781 is a multiple of 47, which it is ($5781 = 123 \cdot 47$). We are thus guaranteed some solution, so we continue. We will first try to find a single solution to the intermediate equation: $4183x_1 + 15087n_1 = 47$, using the results of the Euclidean algorithm above.
$$\begin{align} 47 &= 752 - 5 \cdot 141\\ &= 752 - 5 \cdot (893 - 752)\\ &= 6 \cdot 752 - 5 \cdot 893\\ &= 6 \cdot (1645 - 893) - 5 \cdot 893\\ &= 6 \cdot 1645 - 11 \cdot 893\\ &= 6 \cdot 1645 - 11 \cdot (2538 - 1645)\\ &= 17 \cdot 1645 - 11 \cdot 2538\\ &= 17 \cdot (4183 - 2538) - 11 \cdot 2538\\ &= 17 \cdot 4183 - 28 \cdot 2538\\ &= 17 \cdot 4183 - 28 \cdot (15087 - 3 \cdot 4183)\\ &= 101 \cdot 4183 - 28 \cdot 15087 \end{align}$$
So $x_1=101$, $n_1=-28$ is a solution to $4183x_1 + 15087n_1 = 47$

Now we can use this to find a solution to our original equation: $4183x +15087n = 5781$. Simply multiply both $x_1$ and $n_1$ by 123 (since $5781 = 123 \cdot 47$).

Thus $x=12423$, $n=-3444$ is a solution to $4183x +15087n = 5781$

Adding the appropriate multiples to find all solutions from this one solution, we get
$$x=12423+\dfrac{15087}{47}k \textrm{ and }n=-3444-\dfrac{4183}{47}k$$
Simplifying, we find, $x=12423+321k$ and $n=-3444-89k$ gives all solutions to $4183x +15087n = 5781$

Of course, we don't really care what $n$ is, since it doesn't appear in our original congruence. Further, we are only considering the possible values of $x \pmod{15087}$, of which there are 47 that fit the $12423+321k$ form. Given the large number of solutions, we don't list them all. Instead, we can simply write our solution as:
$$x \equiv 12423 + 321k \pmod{15087} \textrm{, where $k$ is any integer}$$
If we want an even tighter form, we might subtract off as many 321's from 12423 as we can without going negative, so that smaller numbers are used:
$$x \equiv 225 + 321k \pmod{15087} \textrm{, where $k$ is any integer}$$
$1537x \equiv 2863 \pmod{6731}$

First, we translate things back into equation form.

$1537x \equiv 2863 \pmod{6731}$ implies $2863-1537x = 6731n$ for some integer $n$. This in turn, suggests that we can write 2863 as a linear combination of 6731 and 1537:
$$1537x + 6731n = 2863$$
It is not clear by inspection what the gcd of 1537 and 6731 is, so we appeal to the Euclidean algorithm:
$$\begin{align} 6731&= 4 \cdot 1537+ 583\\ 1537&= 2 \cdot 583+ 371\\ 583&= 1 \cdot 371+ 212\\ 371&= 1 \cdot 212+ 159\\ 212&= 1 \cdot 159+ \fbox{53} \leftarrow \textrm{gcd}\\ 159&= 3 \cdot 53+ 0 \end{align}$$
So the gcd of 1537 and 6731 is 53.

However, we have a problem!

This value for the gcd implies that $1537x + 6731n$ must be a multiple of 53. More precisely, $1537x - 6731n = 53(29x+127n)$. But this is impossible, as that would imply that 53 is also a divisor of 2863, which is not the case (2863/53 leaves a remainder of 1).

Consequently, there is no solution to this linear congruence.