Using the last statement in Theorem 46.9, show that for nonzero a, b, n ∈ Z, the congruence ax ≡ b (mod n) has a solution in Z if a and n are relatively prime.

Data from Theorem 46.9

Let D be a Euclidean domain with a Euclidean norm v, and let G and b be nonzero elements of D. Let r₁ be as in Condition 1 for a Euclidean norm, that is, a = bq₁ + r₁, where either r₁ = 0 or v(r₁) < v(b). If r₁ ≠ 0, let r₂ be such that b = r₁q₂ + r₂ where either r₂ = 0 or v(r₂) < v(r₁). In general, let r_i+1 be such that r_i-1 = r_iq_i+1+ r_i+1, where either r_i+1 = 0 or v(r_i+1) < v(r_i). Then the sequence r_i, r₂, ···must terminate with some r_s = 0. If r₁ = 0, then b is a gcd of a and b. If r₁ ≠ 0 and r_s is the first r_i = 0, then a gcd of G and b is r_s-1. Furthermore, if d is a gcd of a and b, then there exist λ and µ, in D such that d = λa+ µb. 

Proof Since v(r_i) < v(r_i-1) and v(r_i) is a nonnegative integer, it follows that after some finite number of steps we must arrive at some r_s = 0. If r₁ = 0, then a = bq₁, and b is a gcd of G and b. Suppose r₁ ≠ 0. Then if d|G and d|b, we have d|(a - bq₁), So d|r₁. However, if d₁|r₁ and d₁|b, then d₁|(bq₁ + r₁), so d₁|G. Thus the set of common divisors of a and b is the same set as the set of common divisors of band r₁. By a similar argument, if r₂ ≠ 0, the set of common divisors of b and r₁ is the same set as the set of common divisors of r₁ and r₂. Continuing this process, we see finally that the set of common divisors of a and b is the same set as the set of common divisors of r_s-2 and r_s-1, where r_s is the first r_i equal to 0. Thus a gcd of r_s-2 and r_s-1 is also a gcd of a and b. But the equation r_s-2 = q_sr_s-1 + r_s = q_sr_s-1 shows that a gcd of r_s-2 and r_s-1 is r_s-1· It remains to show that we can express a gcd d of a and b as d = λa+ µb. In terms of the construction just given, if d = b, then d = 0a + 1b and we are done. If d = r_s-1, then, working backward through our equations, we can express each r_i in the form λ_ir_i-1 + µ_ir_i-2 for some λ_iμ_i ∈ D. To illustrate using the first step, from the equation r_s-3 = q_s-1r_s-2 + r_s-1  we obtain d = r_s-1 = r_s-3 -q_s-1r_s-2. We then express r_s-2 in terms of r_s-3 and r_s-4 and substitute in Eq. (1) to express din terms of rs-3 and r_s-4. Eventually, we will have 

 d = λ₃r₂ + μ₃r₁ = λ₃(b − r₁q₂) + µ₃r₁ = λ₃b + (μ₃ - λ₃q₂)r₁ -

    = λ₃b + (μ₃ - λ₃q₂)(a - bq₁) 

which can be expressed in the form d = λa + µb. If d' is any other gcd of a and b, then
d' = ud for some unit u, so d' = (λu)a + (μu)b.