Use this method (called the Euclidean algorithm) to find the following greatest common divisors. We shall study this algorithm in much more detail later in the term.
$$\operatorname{gcd}(64,81), \operatorname{gcd}(6,121), \operatorname{gcd}(169,273), \operatorname{gcd}(51,187), \operatorname{gcd}(999,2187) \text {. }$$
The following is maybe the most important elementary fact about greatest common divisors and relatively prime integers.

The Euclidean algorithm is a method for computing the greatest common divisor (gcd) of two integers. The key idea is to repeatedly apply the algorithm to pairs of integers where the larger integer is replaced by the difference between the two. We stop when one of the integers is 0, and the other one will be the gcd.

Here’s how you would compute the gcd for the given pairs:

$\text{gcd}(64, 81)$: 81 and 64 have no common factor other than 1 since one is odd and the other is even. Hence, $\text{gcd}(64, 81) = 1$.

$\text{gcd}(6, 121)$: 121 is odd and 6 is even. They have no common factor other than 1. Hence, $\text{gcd}(6, 121) = 1$.

$\text{gcd}(169, 273)$: Using the Euclidean algorithm, 273 = 169*1 + 104, 169 = 104*1 + 65, 104 = 65*1 + 39, 65 = 39*1 + 26, 39 = 26*1 + 13, 26 = 13*2, So, $\text{gcd}(169, 273) = 13$.

$\text{gcd}(51, 187)$: The Euclidean algorithm yields: 187 = 51*3 + 34, 51 = 34*1 + 17, 34 = 17*2, So, $\text{gcd}(51, 187) = 17$.

$\text{gcd}(999, 2187)$: The Euclidean algorithm gives: 2187 = 999*2 + 189, 999 = 189*5 + 84, 189 = 84*2 + 21, 84 = 21*4, So, $\text{gcd}(999, 2187) = 21$.

As for the elementary fact about greatest common divisors and relatively prime integers, it might be the statement that two integers are relatively prime if and only if their gcd is 1.

Prove this. Hint: This is one of many times in the near future we will be using the assumption $\operatorname{gcd}(a, b)=1$ by using that there are integers $x$ and $y$ with $a x+b x=1$. As we have $a \mid b c$ there is a integer $k$ such $b c=a k$. Multiply $a x+b x=1$ by $c$ to get $a c x+b c x=c$. Now replace $b c$ by $a k$ and the result is $a c x+a k x=c$. Now it should be easy to show $a \mid c$.

The following is really a corollary to the last result, but is important enough to get promoted to a Proposition.

The goal is to prove that if $\text{gcd}(a, b) = 1$ and $a | bc$, then $a | c$.

We start with the assumptions that $\text{gcd}(a, b) = 1$ and $a | bc$. This means there exist integers $x$ and $y$ such that $ax + by = 1$, and there exists an integer $k$ such that $bc = ak$.

Multiplying the equation $ax + by = 1$ by $c$ gives us $acx + bcy = c$. Then, we substitute $ak$ for $bc$ in this equation to get $acx + aky = c$.

Now, factoring out the $a$ from the left side of the equation gives $a(cx + ky) = c$. Since $cx + ky$ is an integer (let’s call it $n$), we have shown that $c = an$ for some integer $n$.

Therefore, we have shown that $a | c$ given the original assumptions, which completes the proof.

The proposition that follows from this result might be something like: If $\text{gcd}(a, b) = 1$ and $a | bc$, then $\text{gcd}(a, c) = 1$. This is because if $a | c$, as we’ve shown, then $a$ is a common divisor of $a$ and $c$, and hence the greatest common divisor of $a$ and $c$ is not greater than $a$ itself. So the gcd cannot be any number other than 1.

E-mail: help-assignment@gmail.com  微信:shuxuejun

help-assignment™是一个服务全球中国留学生的专业代写公司