Explore BrainMass

# Congruence Functions Solved

Not what you're looking for? Search our solutions OR ask your own Custom question.

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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.

\$2.49