Explore BrainMass

Explore BrainMass

    Congruence Functions Solved

    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).

    © BrainMass Inc. brainmass.com March 4, 2021, 5:41 pm ad1c9bdddf
    https://brainmass.com/math/algebra/congruence-functions-solved-6089

    Attachments

    Solution Summary

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

    $2.19

    ADVERTISEMENT