(a) Consider the equation ax = b mod m, where x is the unknown and a, b and m ar

Question

(a) Consider the equation ax = b mod m, where x is the unknown and a, b and m are given. Show that this equation has either no solutions mod m, or d solutions mod m, where d = gcd(a, m); also, describe when each of these two cases holds. [HINT: Consider the (non-modular) integer equation ax - km = b (for some integer k), and consider dividing by d.]

(b) Using your answer from the previous part, describe all the solutions mod 63 of each of the following three equations:
(i) 4x + 28 = 2 mod 63
(ii) 7x + 50 = 35 mod 63
(iii) 7x + 50 = 36 mod 6

Explanation / Answer

7X=-14[MOD 63]=49[MOD 63]

[7,63]=7 DIVIDES 49

SO IT CAN BE SOLVED

7X=49[MOD 63]

X=7[MOD 63]

X=7+63P

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.