Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

Solve the congruence 150x ≡ 680 (mod 823) for 0 ≤ x ≤ 823, given that gcd(150,823) = 1?

1 Answer

Relevance
  • kb
    Lv 7
    8 years ago
    Favorite Answer

    Since gcd(10, 823) = 1, we can divide both sides of the congruence by 10 without reducing the modulus, obtaining 15x ≡ 68 (mod 823).

    (Of course, since gcd(150, 823) = 1 and 15 | 150, we have gcd(15, 823) = 1.)

    Now, we use the Euclidean Algorithm to find 15^(-1) (mod 823).

    823 = 54 * 15 + 13

    15 = 1 * 13 + 2

    13 = 6 * 2 + 1.

    So, 13 - 6 * 2 = 1

    ==> 13 - 6(15 - 13) = 1

    ==> 7 * 13 - 6 * 15 = 1

    So, 7(823 - 54 * 15) - 6 * 15 = 1

    ==> 7 * 823 - 384 * 15 = 1

    Thus, -384 * 15 ≡ 1 (mod 823)

    ==> 15^(-1) ≡ -384 ≡ 439 (mod 823).

    ----------

    So, multiplying both sides of 15x ≡ 68 (mod 823) by 439 yields

    x ≡ 68 * 439 ≡ 224 (mod 823).

    I hope this helps!

Still have questions? Get your answers by asking now.