Question

Let a, b be integers with not both 0. Prove that hcf(a, b) is the smallest...

Let a, b be integers with not both 0. Prove that hcf(a, b) is the smallest positive integer m of the form ra + sb where r and s are integers.
Hint: Prove hcf(a, b) | m and then use the minimality condition to prove that m | hcf(a, b).

Math   Advanced-Math   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Given non-zero integers a, b ∈ Z, let X := {ra + sb | r, s...
Given non-zero integers a, b ∈ Z, let X := {ra + sb | r, s ∈ Z and ra + sb > 0}. Then: GCD(a, b) is the least element in X.
9. Let a, b, q be positive integers, and r be an integer with 0 ≤...
9. Let a, b, q be positive integers, and r be an integer with 0 ≤ r < b. (a) Explain why gcd(a, b) = gcd(b, a). (b) Prove that gcd(a, 0) = a. (c) Prove that if a = bq + r, then gcd(a, b) = gcd(b, r).
The least common multiple of nonzero integers a and b is the smallest positive integer m...
The least common multiple of nonzero integers a and b is the smallest positive integer m such that a | m and b | m; m is usually denoted [a,b]. Prove that [a,b] = ab/(a,b) if a > 0 and b > 0.
Prove: Let a and b be integers. Prove that integers a and b are both even...
Prove: Let a and b be integers. Prove that integers a and b are both even or odd if and only if 2/(a-b)
Let Z be the integers. (a) Let C1 = {(a, a) | a ∈ Z}. Prove...
Let Z be the integers. (a) Let C1 = {(a, a) | a ∈ Z}. Prove that C1 is a subgroup of Z × Z. (b) Let n ≥ 2 be an integer, and let Cn = {(a, b) | a ≡ b( mod n)}. Prove that Cn is a subgroup of Z × Z. (c) Prove that every proper subgroup of Z × Z that contains C1 has the form Cn for some positive integer n.
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).
Let a, b, c, m be integers with m > 0. Prove the following: (a) ”a...
Let a, b, c, m be integers with m > 0. Prove the following: (a) ”a ≡ 0 (mod 2) if and only if a is even” and ”a ≡ 1 (mod 2) if and only if a is odd”. (b) a ≡ b (mod m) if and only if a − b ≡ 0 (mod m) (c) a ≡ b (mod m) if and only if (a mod m) = (b mod m). Recall from Definition 8.10 that (a...
1)Let ? be an integer. Prove that ?^2 is even if and only if ? is...
1)Let ? be an integer. Prove that ?^2 is even if and only if ? is even. (hint: to prove that ?⇔? is true, you may instead prove ?: ?⇒? and ?: ? ⇒ ? are true.) 2) Determine the truth value for each of the following statements where x and y are integers. State why it is true or false. ∃x ∀y x+y is odd.
Prove by contradiction: Let a and b be integers. Show that if is odd, then a...
Prove by contradiction: Let a and b be integers. Show that if is odd, then a is odd and b is odd. a) State the negation of the above implication. b) Disprove the negation and complete your proof.
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...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT