Theorem 3.4. Let a and b be integers, not both zero, and suppose that b =...

Theorem 3.4. Let a and b be integers, not both zero, and suppose that b = aq + r

for some integers q and r. Then gcd(b, a) = gcd(a, r).

a) Suppose that for some integer k > d, k | a and k | r. Show that k | b also. Deduce that k is a common divisor of b and a.

b) Explain how part (a) contradicts the assumption that d = gcd(b, a).

Solutions

Expert Solution

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

Let a and b be integers which are not both zero. (a) If c is an...

Let a and b be integers which are not both zero. (a) If c is an integer such that there exist integers x and y with ax+by = c, prove that gcd(a, b) | c. (b) If there exist integers x and y such that ax + by = 1, explain why gcd(a, b) = 1. (c) Let d = gcd(a,b), and write a = da′ and b = db′ for some a′,b′ ∈ Z. Prove that gcd(a′,b′) = 1.

a.) Prove the following: Lemma. Let a and b be integers. If both a and b...

a.) Prove the following: Lemma. Let a and b be integers. If both a and b have the form 4k+1 (where k is an integer), then ab also has the form 4k+1. b.)The lemma from part a generalizes two products of integers of the form 4k+1. State and prove the generalized lemma. c.) Prove that any natural number of the form 4k+3 has a prime factor of the form 4k+3.

Let a and b be integers and consider (a) and (b) the ideals they generate. Describe...

Let a and b be integers and consider (a) and (b) the ideals they generate. Describe the intersection of (a) and (b), the product of (a) and (b), the sum of (a) and (b) and the Ideal quotient (aZ:bZ).

Let a and b be integers. Recall that a pair of Bezout coefficients for a and...

Let a and b be integers. Recall that a pair of Bezout coefficients for a and b is a pair of integers m, n ∈ Z such that ma + nb = (a, b). Prove that, for any fixed pair of integers a and b, there are infinitely many pairs of Bezout coefficients.

Let a,b be an element in the integers with a greater or equal to 1. Then...

Let a,b be an element in the integers with a greater or equal to 1. Then there exist unique q, r in the integers such that b=aq+r where z less than or equal r less than or equal a+(z-1). Prove the Theorem.

Rolle's Theorem, "Let f be a continuous function on [a,b] that is differentiable on (a,b) and...

Rolle's Theorem, "Let f be a continuous function on [a,b] that is differentiable on (a,b) and such that f(a)=f(b). Then there exists at least one point c on (a,b) such that f'(c)=0." Rolle's Theorem requires three conditions be satisified. (a) What are these three conditions? (b) Find three functions that satisfy exactly two of these three conditions, but for which the conclusion of Rolle's theorem does not follow, i.e., there is no point c in (a,b) such that f'(c)=0. Each...

Let P be the uniform probability on the integers from 1 to 99. Let B be...

Let P be the uniform probability on the integers from 1 to 99. Let B be the subset of numbers which have the digit 3. Let A be the subset of even numbers. What is P(A), P(B)? What is P(A|B)? P(B|A)?

Let a and b be positive integers, and let d be their greatest common divisor. Prove...

Let a and b be positive integers, and let d be their greatest common divisor. Prove that there are infinitely many integers x and y such that ax+by = d. Next, given one particular solution x0 and y0 of this equation, show how to find all the solutions.

Bezout’s Theorem and the Fundamental Theorem of Arithmetic 1. Let a, b, c ∈ Z. Prove...

Bezout’s Theorem and the Fundamental Theorem of Arithmetic 1. Let a, b, c ∈ Z. Prove that c = ma + nb for some m, n ∈ Z if and only if gcd(a, b)|c. 2. Prove that if c|ab and gcd(a, c) = 1, then c|b. 3. Prove that for all a, b ∈ Z not both zero, gcd(a, b) = 1 if and only if a and b have no prime factors in common.

Below is a proof of Theorem 4.1.1 (b): For the zero vector ⃗0 in any vector...

Below is a proof of Theorem 4.1.1 (b): For the zero vector ⃗0 in any vector space V and k ∈ R, k⃗0 = ⃗0. Justify for each of the eight steps why it is true. k⃗0+k⃗0=k(⃗0+⃗0) = k ⃗0 k⃗0 is in V and therefore −(k⃗0) is in V . It follows that (k⃗0 + k⃗0) + (−k⃗0) = (k⃗0) + (−k⃗0) and thus k⃗0 + (k⃗0 + (−k⃗0)) = (k⃗0) + (−k⃗0). We conclude that k⃗0 + ⃗0...

Subjects