# Congruence Functions Solved

Solve the congruence 42x 12 (mod 90).

Problem:

Solve the congruence 42x 12 (mod 90).

Solution:

We have gcd (42, 90) = 6, so by Theorem Given below, there is a solution since 6 is a factor of 12.

The congruence ax b (mod n) has a solution if and only if b is divisible by d, where d = (a, n).

If d | b, then there are d distinct solutions modulo n, and these solutions are congruent modulo n / d.

Solving the congruence

42x 12 (mod 90) is equivalent to solving the equation

42x = 12 + 90q for integers x and q. This reduces to

7x = 2 + 15q, or 7x 2 (mod 15).

Equivalently, we obtain

7x 2 (mod 15) by dividing

42x 12 (mod 90) through by 6.

We next use trial and error to look for the multiplicative inverse of 7 modulo 15. The numbers congruent to 1 modulo 15 are 16, 31, 46, 61, etc., and -14, -29, -34, etc. Among these, we see that -14 is a multiple of 7, so we can multiply both sides of the congruence

7x 2 (mod 15) by -2 since

(-2) (7) = -14 1 (mod 15). Thus we have

7x 2 (mod 15)

-14x -4 (mod 15)

x 11 (mod 15).

The solution to the original congruence is

x 11, 26, 41,56,71,86 (mod 90).

https://brainmass.com/math/algebra/congruence-functions-solved-6089

#### Solution Summary

The congruence functions are solved. The multiplicative inverse functions are examined.