Question

Discrete Mathematics I

5. Find all integers that satisfy the congruence relation 33x ≡ 38 (mod 280) .

Answer 1

ANSWER

The general solution is $86+280n$, where $n$ is an  integer

EXPLANATION

In order  to solve the linear congruence;

$33x \equiv 38(mod\:280)$

We need to determine the inverse of $33$ (which is a Bézout coefficient for 33).

To do that we must first use  the Euclidean Algorithm to verify the existence of the inverse by showing that;

$gcd(33,\:280)=1$

Now, here we go;

$280=8\times33+16$

$33=2\times 16+1$

$16=2\times 8+0$

The greatest common divisor is the last remainder before the remainder of zero.

Hence, the $gcd(33,\:280)=1$.

We now express this gcd of 1 as a linear combination of  33 and 280.

We can achieve this by making all the non zero remainders the subject and making a backward substitution.

$1=33-2\times 16--(1)$

$16=280-33\times8--(2)$

Equation (2) in equation (1) gives,

$1=33-2\times (280-8\times33)$

$1=33-2\times 280+16\times33$

$1=17\times33-2\times 280$

The above linear combination tells us that  $17$ is the inverse of $33$.

Now we multiply both sides of our congruence relation by $17$.

$17\times 33x \equiv 17\times 38(mod\:280)$

This implies that;

$x \equiv 646(mod\:280)$

$x \equiv 86$.

Since this is modulo, the solution is not unique because any integral addition or subtraction of the modulo (280 in this case) produces an equivalent solution.

Therefore the general solution is,

$86+280n$, where $n$ is an  integer