Question

chapter 2. basic integer division 18

with sage you can calculate arbitrary gcds like this, so you can check
your work in this problem using the same command as before, but with
slightly different syntax.

gcd(3800,7600,1900)

1900

1. find the gcd of the four numbers 1240, 6660, 15540, and 19980 without

sage.

1. prove that \\(\gcd(a, a + 2) = 1\\) if \\(a\\) is odd and \\(\gcd(a, a + 2) = 2\\) if \\(a\\) is even.

1. let \\(a\\) be a positive integer. what is the greatest common divisor of \\(a\\) and

\\(a + 1\\)? prove it.

1. use the euclidean algorithm to find the gcd of 51 and 87, and then to

write that gcd as a linear combination of 51 and 87.

1. define the least common multiple of \\(a\\) and \\(b\\) to be the smallest positive

number which is divisible by both \\(a\\) and \\(b\\). prove that the least common
multiple of \\(a\\) and \\(b\\) is \\(ab\\) precisely when \\(a\\) and \\(b\\) are coprime.

1. find the gcd of 151 and 187 using the euclidean algorithm, then write the

gcd as a linear combination of these two numbers in two different ways.

Explanation:

Since you haven't specified which problem to solve, I'll pick problem 8: "Use the Euclidean algorithm to find the gcd of 51 and 87, and then to write that gcd as a linear combination of 51 and 87."

Step 1: Apply Euclidean Algorithm

We divide the larger number by the smaller one and find the remainder. Then we repeat the process with the divisor and the remainder until the remainder is 0. The last non - zero remainder is the gcd.

• Divide 87 by 51: \(87 = 51\times1+36\) (Here, dividend = divisor×quotient + remainder, so \(87\) is dividend, \(51\) is divisor, \(1\) is quotient, \(36\) is remainder)
• Now divide 51 by 36: \(51=36\times1 + 15\)
• Then divide 36 by 15: \(36 = 15\times2+6\)
• Next divide 15 by 6: \(15=6\times2 + 3\)
• Finally divide 6 by 3: \(6 = 3\times2+0\)

When the remainder is 0, the divisor (3) is the gcd of 51 and 87.

Step 2: Work Backwards to Find Linear Combination

We start from the equation where the remainder is the gcd (in this case, \(15 = 6\times2+3\)) and solve for the gcd (3):
\(3=15 - 6\times2\)

Now we substitute 6 from the previous equation (\(36 = 15\times2+6\) implies \(6 = 36-15\times2\)) into the above equation:
\(3=15-(36 - 15\times2)\times2=15\times5-36\times2\)

Next, substitute 15 from the equation \(51 = 36\times1+15\) (which implies \(15 = 51 - 36\times1\)) into the equation:
\(3=(51 - 36\times1)\times5-36\times2=51\times5-36\times7\)

Then substitute 36 from the equation \(87 = 51\times1+36\) (which implies \(36 = 87 - 51\times1\)) into the equation:
\(3=51\times5-(87 - 51\times1)\times7=51\times12-87\times7\)

Answer:

The gcd of 51 and 87 is 3, and \(3 = 12\times51-7\times87\) (or other equivalent linear combinations, for example, we can also write it by rearranging the steps in a different order, but this is one valid linear combination).