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.

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

**Subject Mathematics Abstract Algebra**

**Keywords**

Linear

Congruence

GCD

Equation

Integer

Euclidean

Combination

Unique

Solution

Algorithm