hw01-r5.md

Proposition. Prove $(a,b)=(a,b+a)$ for all $a,b\in\mathbb{Z}$

Proof. For some $x,y\in\mathbb{Z}$. $$ d_1=(a,b)=ax+by $$

Thus $d_1$ divides both $a$ and $b$.

\begin{align*} d_2=(a,b+a)&=ax+(b+a)y\ &\Leftrightarrow ax+by+ay\ &\Leftrightarrow a(x+y)+by \end{align*}

Similarly $d_2$ divides both $a$ and $b$.

By the definition of GCD $d_1$ and $d_2$ are then both the largest elements in the set of numbers which divide both $a$ and $b$ and thus are the same number, and $(a,b)=(a,b+a)$.