3. (Linear Congruence). An equation in integers of the form ax=b (mod m) is called a linear congruence. We want to find an integer x that will satisfy it. (Note that ax=b (mod m) is equivalent to saying ax-b=nm for some integer n.Solution
a) Prove that if (a, m) = 1 then there is always a solution. (Hint: express the gcd as a linear combination and multiply by b.).
b) For 56 and 15 use the Euclidean algorithm to express the gcd 1= (56, 15) as a linear combination 56s+15t=1.
c) Use part b to find a value of x so that 15x=7 (mod 56).