Question

If an are integers, not all zero, then their greatest common divisor (gcd) is the largest integer d such that $d|a_i$for every i. Prove that there exist integers such that .

role="math" localid="1646114291924" $d=a_1{u}_1+a_2{u}_2+....+a_n{u}_n$

Short answer

It is proved that there exist integers such that $u_i$such that$d=a_1{u}_1+a_2{u}_2+....+a_n{u}_n$

Step-by-step solution

To consider

Let us consider that $S=\left\{a_1{x}_1+a_1{x}_1+....+a_n{x}_n\right\}$, where $x_1,x_2,.....,x_n$are integers.

According to the proof of theorem 1.2, set S does not contain some positive elements, that is, $a_i\ne 0$, and ${a_j}^2\in S$is positive.

According to Well Ordering Axiom, the set S contains the smallest positive element.

Let us consider that$t=a_1{u}_1+a_2{u}_2+....+a_n{u}_n$ for some integers $u_j$.

To prove that t=d

Now, we will prove that t=d.

First, we will show that $t|a_1$. According to the division algorithm, there exist integers q and r such that $a_1=tq+r,0\le r<t.$.

This implies that the following:

$\begin{array}{rcl}r& =& a_1-tq\\ & =& a_1\left(1-u_{1}q\right)+a_2\left(-u_{2}q\right)+...+a_n\left(-u_{n}q\right)\end{array}$

So, r is an element of S as $r<t$, and r is not positive, As $r\ge 0$, the possibility is $r=0$.

This implies that $a_1=tq$and $t|a_1$.

Similarly, we can prove that $t|a_j$, and t is a common divisor of $a_1,a_2,....,a_n$.

$a_1,a_{2,...,}{a}_n$.

Step-3

This implies that $t\le d$.

As d divides every integer linear combination $a_1,a_{2,...,}{a}_n$.

As $t>0$, this implies that $d\le t$.