Question

4. Let a, b, c be integers. (a) Prove if gcd(ab, c) = 1, then gcd(a,...

4. Let a, b, c be integers.

(a) Prove if gcd(ab, c) = 1, then gcd(a, c) = 1 and gcd(b, c) = 1. (Hint: use the GCD characterization theorem.)

(b) Prove if gcd(a, c) = 1 and gcd(b, c) = 1, then gcd(ab, c) = 1. (Hint: you can use the GCD characterization theorem again but you may need to multiply equations.)

(c) You have now proved that “gcd(a, c) = 1 and gcd(b, c) = 1 if and only if gcd(ab, c) = 1.” Is this statement true if the greatest common divisor is not 1?

So is the following statement true: “gcd(a, c) = d and gcd(b, c) = d if and only if gcd(ab, c) = d?”

Homework Answers

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
1. (a) Let a, b and c be positive integers. Prove that gcd(ac, bc) = c...
1. (a) Let a, b and c be positive integers. Prove that gcd(ac, bc) = c x gcd(a, b). (Note that c gcd(a, b) means c times the greatest common division of a and b) (b) What is the greatest common divisor of a − 1 and a + 1? (There are two different cases you need to consider.)
8. Let a, b be integers. (a) Prove or disprove: a|b ⇒ a ≤ b. (b)...
8. Let a, b be integers. (a) Prove or disprove: a|b ⇒ a ≤ b. (b) Find a condition on a and/or b such that a|b ⇒ a ≤ b. Prove your assertion! (c) Prove that if a, b are not both zero, and c is a common divisor of a, b, then c ≤ gcd(a, b).
Prove that for positive integers a and b, gcd(a,b)lcm(a,b) = ab. There are nice proofs that...
Prove that for positive integers a and b, gcd(a,b)lcm(a,b) = ab. There are nice proofs that do not use the prime factorizations of a and b.
prove that if gcd(a,b)=1 then gcd (a-b,a+b,ab)=1
prove that if gcd(a,b)=1 then gcd (a-b,a+b,ab)=1
1.13. Let a1, a2, . . . , ak be integers with gcd(a1, a2, . ....
1.13. Let a1, a2, . . . , ak be integers with gcd(a1, a2, . . . , ak) = 1, i.e., the largest positive integer dividing all of a1, . . . , ak is 1. Prove that the equation a1u1 + a2u2 + · · · + akuk = 1 has a solution in integers u1, u2, . . . , uk. (Hint. Repeatedly apply the extended Euclidean algorithm, Theorem 1.11. You may find it easier to prove...
Let a, b, c be natural numbers. We say that (a, b, c) is a Pythagorean...
Let a, b, c be natural numbers. We say that (a, b, c) is a Pythagorean triple, if a2 + b2 = c2 . For example, (3, 4, 5) is a Pythagorean triple. For the next exercises, assume that (a, b, c) is a Pythagorean triple. (c) Prove that 4|ab Hint: use the previous result, and a proof by con- tradiction. (d) Prove that 3|ab. Hint: use a proof by contradiction. (e) Prove that 12 |ab. Hint : Use the...
Given that the gcd(a, m) =1 and gcd(b, m) = 1. Prove that gcd(ab, m) =1
Given that the gcd(a, m) =1 and gcd(b, m) = 1. Prove that gcd(ab, m) =1
Prove that for all non-zero integers a and b, gcd(a, b) = 1 if and only...
Prove that for all non-zero integers a and b, gcd(a, b) = 1 if and only if gcd(a, b^2 ) = 1
The greatest common divisor c, of a and b, denoted as c = gcd(a, b), is...
The greatest common divisor c, of a and b, denoted as c = gcd(a, b), is the largest number that divides both a and b. One way to write c is as a linear combination of a and b. Then c is the smallest natural number such that c = ax+by for x, y ∈ N. We say that a and b are relatively prime iff gcd(a, b) = 1. Prove that a and n are relatively prime if and...
Let gcd(m1,m2) = 1. Prove that a ≡ b (mod m1) and a ≡ b (mod...
Let gcd(m1,m2) = 1. Prove that a ≡ b (mod m1) and a ≡ b (mod m2) if and only if (meaning prove both ways) a ≡ b (mod m1m2). Hint: If a | bc and a is relatively prime to to b then a | c.