(i). Determine the remainder when $376 \times 427$ is divided by $9$.

(ii). Determine the remainder when $23^8$ is divided by $7$.

Solution

(i). $(376 \times 427)(mod\, 9) = [( 376\, mod\, 9 ) \times ( 427\, mod\, 9 )]( mod\, 9)$

$= [7 \times 4 ]( mod\, 9 ) = 28( mod\, 9 ) = 1$.

(ii). $23^8( mod\, 7 ) = [ 23( mod\, 7 )]^8( mod\, 7)$

$= 2^8( mod\, 7 )$

$ = 256( mod\, 7 ) = 4$.

What is the remainder when $3^{209}$ is divided by $44$?

Solution

We need to calculate $3^{209}( mod\, 44 )$ .

Step 1

Write the exponent $(209)$ as a sum of powers of $2$:

$209 = 128 + 64 + 16 + 1.$

We note here that every positive integer can be expressed as a sum of distinct powers of $2$.

Step 2

Working modulo $44$, we repeatedly square $3$ to find $3^{2^k}$ for all $k$ such that $2^k \le 209$.

$k = 0: 3^{2^0} \equiv 3^1 \equiv 3( mod\, 44 )$

$k = 1: 3^{2^1} \equiv 3^2 \equiv 9( mod\, 44 )$

$k = 2: 3^{2^2} \equiv 3^4 \equiv ( 3^2 )^2 \equiv 9^2 \equiv 81 \equiv 37( mod\, 44 )$

$k = 3: 3^{2^3} \equiv 3^8 \equiv ( 3^4 )^2 \equiv 37^2 \equiv 1369 \equiv 5( mod\, 44 )$

$k = 4: 3^{2^4} \equiv 3^{16} \equiv ( 3^8 )^2 \equiv 5^2 \equiv 25( mod\, 44 )$

$k = 5: 3^{2^5} \equiv 3^{32} \equiv ( 3^{16} )^2 \equiv 25^2 \equiv 625 \equiv 9( mod\, 44 )$

$k = 6: 3^{2^6} \equiv 3^{64} \equiv ( 3^{32} )^2 \equiv 9^2 \equiv 81 \equiv 37( mod\, 44 )$

$k = 7: 3^{2^7} \equiv 3^{128} \equiv ( 3^{64} )^2 ≡ 37^2 ≡ 1369 ≡ 5( mod\, 44 )$.

We stop here as doubling the exponent again produces an exponent $(256)$ greater than the original $(209)$. At each step we simply square the output from the previous step so that, as we are working modulo $44$, we never have to work with a number larger than $43^2$. Furthermore, note that in this case the remainder cycles $(9, 37, 5, 25)$ and so we do not have to compute it at each subsequent step thereby making the calculations relatively straightforward.

Step 3

Since $209 = 128 + 64 + 16 + 1$ we have

$3^{209} \equiv 3^{128 + 64 + 16 + 1}( mod\, 44 )$

$\equiv 3^{128} \times 3^{64} \times 3^{16} × 3^1( mod\, 44 )$

$\equiv 5 \times 37 \times 25 \times 3( mod\, 44 )$

$\equiv 13875( mod\, 44 )$

$\equiv 15( mod\, 44 )$

Hence, $3^{209}( mod\, 44 ) \equiv 15\;(mod\,44)$ and the remainder when $\;3^{209}$ is divided by $44$ is $15$ .

Note that when evaluating $5 \times 37 \times 25 \times 3( mod\, 44 )$ we could split the calculation so that we are working with “manageable” numbers. For example, we could proceed as follows:

$5 \times 37 \times 25 \times 3( mod\, 44 )$

$\equiv [(5 \times 37 \times 3\, mod\, 44 )( 25\, mod\, 44 )]( mod\, 44 )$

$\equiv [( 555\, mod\, 44 )( 25\, mod\, 44 )]( mod\, 44 )$

$\equiv [ 27 \times 25 ]( mod\, 44 )$

$\equiv 675( mod\, 44 )$

$\equiv 15( mod\, 44 )$.

If possible solve each of the following congruence equations. If no solution exists, explain why not.

(i). $3x \equiv 1( mod\, 5 )$

(ii). $3x \equiv 1( mod\, 6 )$.

Solution

(i). $d = \;$gcd$(3, 5) = 1$ and so the equation has a unique solution.

As the modulus is small (5) we can test each of the numbers in $\mathbb{Z}_5 = \{0, 1, 2, 3, 4\}$ by substituting for $x$.

The equation requires that $5 \mid (3x - 1)$ .

We form the table below and test each of the numbers $0, 1, 2, 3$ and $4$ in turn.

The unique solution modulo 5 is $x = 2$ , since $5 \mid (3 \times 2 - 1)$ , i.e. $5 \mid 5$.

(The general solution is $2 + 5 k$ for $k \in \mathbb{Z}$)

Note: An alternative approach is to find the multiplicative inverse of $3$ in $\mathbb{Z}_5$ and multiply both sides of the equation by this inverse value.

We found earlier that in $\mathbb{Z}_5, 3^{-1} = 2$, see the multiplication table for $\mathbb{Z}_5$ in section 4.2.1.

Multiplying the equation through by $2$ gives, $x \equiv 2( mod\, 5 )$.

(ii). $d =\; $gcd$(3, 6) = 2$ , and $2 \nmid 1$ so the equation has no solution.

Alternatively, as the modulus is small $(6)$ we can test each of the numbers in $\mathbb{Z}_6 = \{0, 1, 2, 3, 4, 5\}$ to find that there is no value of $x$ that satisfies $6 \mid (3x - 1)$.

Another approach is to note that the multiplication table for $\mathbb{Z}_6$ shows that $3$ does not have a multiplicative inverse in $\mathbb{Z}_6$ and so the equation has no solution.

When the modulus in a congruence equation is large it becomes unrealistic to test individual values of $x$. In such cases the Euclidean Algorithm is employed to find $d =\; $gcd$(a, m)$ and then, if $d = 1$ , back-substitution is applied to arrive at an expression of the form $ax_0 + my_0 = 1$ where $x = x_0$ is a solution of the equation $ax \equiv 1( mod\, m )$.

Solve the congruence equation $387x \equiv 1 (mod\, 479)$ or show that there is no solution.

Solution

See Example 26 where we already solved this equation to find that the unique solution modulo $479$ is $x = 328$.

Solve the congruence equation $213x \equiv 1 (mod\, 243)$ or show that there is no solution.

Solution

Use either the Euclidean algorithm or prime factorisation to show that $d =\; $gcd$(243, 213) = 3$ and as $3 \nmid 1$ the equation has no solution.

If possible solve the following congruence equations:

(i). $3x \equiv 4( mod\, 5 )$.

(ii). $387x \equiv 63 ( mod\, 479 )$ .

Solution

(i). In Example 29(i) we showed that $x = 2$ is the unique solution modulo $5$ to the equation $3x \equiv 1( mod\, 5 )$. By the above theorem the unique solution $3x \equiv 4(mod\, 5)$ is therefore given by $x \equiv ( 4 \times 2 ) \equiv 8 \equiv 3( mod\, 5 )$.

In this example, as the modulus is small, we could have simply tested the values from $0$ to $4$ to show that the only value in $\mathbb{Z}_5$ for which $5 \mid ( 3x - 4 )$ is $x = 3$ and hence the only solution to $3x \equiv 4( mod\, 5 )$ . Alternatively, we could use the Cayley multiplication table to find $3^{-1} = 2$, and multiply the equation through by $2$ to obtain $x \equiv 8 \equiv 3( mod\, 5 )$.

(ii). In Examples 26 and 30 we showed that $x = 328$ is the unique solution modulo $479$ to the equation $387x \equiv 1( mod \,479 )$.

By the above theorem the unique solution modulo $479$ to $387x \equiv 63( mod\, 479 )$ is therefore given by $x \equiv ( 63 \times 328 )(mod\, 479 ) \equiv 67$.

Now watch the video at the link below.

📹 Solving Congruence Equations

If possible, solve $102x \equiv 96 ( mod \, 399 )$. (1)

Solution

Use the Euclidean algorithm to find $d =\; $gcd$( 399, 102 )$

$399 = 3 \times 102 + 93$

$102 = 1 \times 93 + 9$

$93 = 10 \times 9 + 3$

$ 9 = 3 × 3 + 0$.

Hence, $d =\; $gcd$( 399, 102 ) = 3$ and $3 \mid 96$, so there are $3$ solutions to the equation.

Now apply the Simplification Law to Eq (1) (as $3$ divides $102, 96$ and $399$) to obtain:

$34x \equiv 32 ( mod\, 133 )$.(2)

To solve Eq. (2) we first apply the Euclidean Algorithm to calculate $d =\; $gcd$( 133, 34 )$, which we know by the above theorem to be $1$ as $34$ and $133$ must be relatively prime:

$133 = 3 \times 34 + 31$

$34 = 1 \times 31 + 3$

$31 = 10 \times 3 + 1$

$3 = 3 \times 1 + 0$.

So, gcd$( 133, 34 ) = 1$ and as expected there is a unique solution to Eq. (2).

Now apply the Extended Euclidean algorithm to solve,

$34x \equiv 1( mod\, 133 )$.(3)

Rearrange the above in terms of the remainder:

$31 = 133 - 3 \times 34$

$3 = 34 - 1 \times 31$

$1 = 31 - 10 \times 3$.

Express the GCD as a linear combination of 34 and 133 using back-substitution:

$1 = 31 - 10 \times 3$

$= 1 \times 31 - 10 \times ( 34 - 1 \times 31 )$

$= 1 \times 31 - 10 \times 34 + 10 \times 31$

$= 11 \times 31 - 10 \times 34$

$= 11 \times (133 - 3 \times 34) - 10 \times 34$

$= 11 \times 133 - 33 \times 34 - 10 \times 34$

$= 11 \times 133 - 43 \times 34$

Hence, $34 \times (-43) + 133 \times 11 = 1$.

Using the Extended Euclidean algorithm the GCD (1) of $34$ and $133$ has been expressed as a linear combination, i.e. $34x + 133y = 1$, where $x = -43$ and $y = 11$.

Now, $-43\; mod(133) \equiv 90$ and so, $x = 90$ is the unique solution modulo $133$ to Eq. (3)

To find the unique solution to Eq. (2), which is also a solution to Eq. (1), we calculate:

$ x = (32 \times 90)(mod\, 133 ) = 87.$

The other solutions to Eq. (1) are found by adding $d - 1 = 2$ multiples of $133$ to $x = 87$.

We have,

$x = 87 + 1 \times 133 = 220$ and

$x = 87 + 2 \times 133 = 353$.

The three solutions modulo $399$ to Eq. (1) are therefore $x=87$, $x=220$ and $x=353$.

If possible, solve, $91x \equiv 193( mod\, 299 )$.

Solution

Applying Euclid’s Algorithm gives $d =\; $gcd$( 299, 91 ) = 13$ but $13 \nmid 193$ and so there are no solutions to the equation.