# 数学代写|数论代写number theory代考MAT115A|The Euclidean algorithm

#### Doug I. Jones

Lorem ipsum dolor sit amet, cons the all tetur adiscing elit

couryes™数论number theory代写，免费提交作业要求， 满意后付款，成绩80\%以下全额退款，安全省心无顾虑。专业硕 博写手团队，所有订单可靠准时，保证 100% 原创。couryes™， 最高质量的数论number theory作业代写，服务覆盖北美、欧洲、澳洲等 国家。 在代写价格方面，考虑到同学们的经济条件，在保障代写质量的前提下，我们为客户提供最合理的价格。 由于统计Statistics作业种类很多，同时其中的大部分作业在字数上都没有具体要求，因此数论number theory作业代写的价格不固定。通常在经济学专家查看完作业要求之后会给出报价。作业难度和截止日期对价格也有很大的影响。

couryes™ 为您的留学生涯保驾护航 在澳洲代写方面已经树立了自己的口碑, 保证靠谱, 高质且原创的澳洲代写服务。我们的专家在数论number theory代写方面经验极为丰富，各种数论number theory相关的作业也就用不着 说。

couryes™为您提供可以保分的包课服务

## 数学代写|数论代写number theory代考|Finding the gcd

Most readers will know the Euclidean algorithm, used to find the greatest common divisor (ged) of two given integers. For example, to determine the greatest common divisor of 85 and 48 , we begin by subtracting the smaller from the larger, 48 from 85 , to obtain $85-48=37$. Now $\operatorname{gcd}(85,48)=\operatorname{gcd}(48,37)$, because the common divisors of 48 and 37 are precisely the same as those of 85 and 48 , and so we apply the algorithm again to the pair 48 and 37. So we subtract the smaller from the larger to obtain $48-37=11$, so that $\operatorname{ged}(48,37)=\operatorname{gcd}(37,11)$. Next we should subtract 11 from 37 , but then we would only do so again, and a third time, so let’s do all that in one go and take $37-3 \times 11=4$, to obtain $\operatorname{gcd}(37,11)=\operatorname{ged}(11,4)$. Similarly we take $11-2 \times 4=3$, and then $4-3=1$, so that the ged of 85 and 48 is 1. This is the Euclidean algorithm that you might already have seen, 1 but did you ever prove that it really works?

To do so, we will first carefully define terms that we have implicitly used in the above paragraph, perhaps mathematical terms that you have used for years (such as “divides”, “quotient”, and “remainder”) without a formal definition. This may seem pedantic but the goal is to make sure that the rules of basic arithmetic are really established on a sound footing.

Let $a$ and $b$ be given integers. We say that $a$ is divisible by $b$, or that $b$ divides $a, 2$ if there exists an integer $q$ such that $a=q b$. For convenience we write ” $b \mid a$ ” $3 .$ We now set an exercise for the reader to check that the definition allows one to manipulate the notion of division in several familiar ways.

## 数学代写|数论代写number theory代考|Linear combinations

The Euclidean algorithm can also be used to determine a linear combination $]^{7}$ of $a$ and $b$, over the integers, which equals $\operatorname{gcd}(a, b)$; that is, one can always use the Euclidean algorithm to find integers $u$ and $v$ such that
$$a u+b v=\operatorname{gcd}(a, b) \text {. }$$
Let us see how to do this in an example, by finding integers $u$ and $v$ such that $85 u+48 v=1$; remember that we found the ged of 85 and 48 at the beginning of section 1.1. We retrace the steps of the Euclidean algorithm, but in reverse: The final step was that $1=1 \cdot 4-1 \cdot 3$, a linear combination of 4 and 3 . The second to last step used that $3=11-2 \cdot 4$, and so substituting $11-2 \cdot 4$ for 3 in $1=1 \cdot 4-1 \cdot 3$, we obtain
$$1=1 \cdot 4-1 \cdot 3=1 \cdot 4-1 \cdot(11-2 \cdot 4)=3 \cdot 4-1 \cdot 11,$$
a linear combination of 11 and 4. This then implies, since we had $4=37-3 \cdot 11$, that
$$1=3 \cdot(37-3 \cdot 11)-1 \cdot 11=3 \cdot 37-10 \cdot 11,$$
a linear combination of 37 and 11. Continuing in this way, we successively deduce, using that $11=48-37$ and then that $37=85-48$,

## 数学代写|数论代写number theory代考|The set of linear combinations of two integers

Theorem 1.1 states that the greatest common divisor of two integers is a linear combination of those two integers. This suggests that it might be useful to study the set of linear combinations
$$I(a, b):={a m+b m: m, n \in \mathbb{Z}}$$
of two given integers $a$ and $b \otimes$ We see that $I(a, b)$ contains $0, a, b, a+b, a+$ $2 b, 2 b+a, a-b, b-a, \ldots$ and any sum of integer multiples of $a$ and $b$, so that $I(a, b)$ is closed under addition. Let $I(a):=I(a, 0)={a m: m \in \mathbb{Z}}$, the set of integer multiples of $a$. We now prove that $I(a, b)$ can be described as the set of integer multiples of ged $(a, b)$, a set which is easier to understand:
Corollary 1.3.1. For any given non-zero integers $a$ and b, we have
$${a m+b n: m, n \in \mathbb{Z}}={g k: k \in \mathbb{Z}}$$
where $g:=\operatorname{gcd}(a, b)$; that is, $I(a, b)=I(g)$. In other words, there exist integers $m$ and $n$ with $a m+b n=c$ if and only if $\operatorname{ged}(a, b)$ divides $c$.

Proof. By Theorem $1.1$ we know that there exist $u, v \in \mathbb{Z}$ for which $a u+b v=g$. Therefore $a(u k)+b(v k)=g k$ so that $g k \in I(a, b)$ for all $k \in \mathbb{Z}$; that is, $I(g) \subset I(a, b)$. On the other hand, as $g$ divides both $a$ and $b$, there exist integers $A, B$ such that $a=g A, b=g B$, and so any $a m+b n=g(A m+B n) \in I(g)$. That is, $I(a, b) \subset I(g)$. The result now follows from the two inclusions.

## 数学代写|数论代写number theory代考|Linear combinations

$$a u+b v=\operatorname{gcd}(a, b)$$

$$1=1 \cdot 4-1 \cdot 3=1 \cdot 4-1 \cdot(11-2 \cdot 4)=3 \cdot 4-1 \cdot 11$$
11 和 4 的线性组合。这意味着，因为我们有 $4=37-3 \cdot 11$ ，那
$$1=3 \cdot(37-3 \cdot 11)-1 \cdot 11=3 \cdot 37-10 \cdot 11$$
37 和 11 的线性组合。以这种方式继续，我们依次推导，使用 $11=48-37$ 然后那个 $37=85-48$,

## 数学代写|数论代写number theory代考|The set of linear combinations of two integers

$$I(a, b):=a m+b m: m, n \in \mathbb{Z}$$

real analysis代写analysis 2, analysis 3请认准UprivateTA™. UprivateTA™为您的留学生涯保驾护航。

Days
Hours
Minutes
Seconds

# 15% OFF

## On All Tickets

Don’t hesitate and buy tickets today – All tickets are at a special price until 15.08.2021. Hope to see you there :)