Question

Discrete Mathematics I

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

Answer 1

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

Step-by-step 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*33+16`

`33=2* 16+1`

`16=2* 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* 16--(1)`

`16=280-33*8--(2)`

Equation (2) in equation (1) gives,

`1=33-2* (280-8*33)`

`1=33-2* 280+16*33`

`1=17*33-2* 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* 33x \equiv 17* 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