Exercise 1.2

Question

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

If $r
eq 0$, we can find $q_1$ and $r_1$ such that $b = q_1r+r_1$, with $0 \leq r_1 < r$. Show that $(a,b) = (r,r_1)$. This process can be repeated. Show that it must end in finitely many steps. Show that the last nonzero remainder must equal $(a,b)$. The process looks like
\begin{align*}
a &= b q + r,  &0 \leq r <b\
b &= q_1 r + r_1, &0 \leq r_1 <r\
r &= q_2 r_1 + r_2,  &0\leq r_2 <r_1\
&\vdots\
r_{k-1} &= q_{k+1} r_k + r_{k+1}, &0 \leq r_{k+1} <r_k\
r_k &= q_{k+2} r_{k+1}\
\end{align*}

Then $r_{k+1} = (a,b)$. This process of finding $(a,b)$ is known as the Euclidian algorithm.

Richard Ganaye · Accepted Answer

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof}
The Euclidian division of $b$ by $r$ gives $b = q_1 r + r_1, 0\leq r_1 < r$. The result of exercise 1.1 applied to the couple $(b,r)$ shows that
$$b \wedge r = r \wedge r_1.$$
Let $N \in \mathbb{N}$. While the remainders $r_i, i \leq N$, are not equal to 0, we can define the sequences $(q_i), (r_i)$ by

$$r_{-1} = a, r_0 = b, \qquad r_{i-1} = q_{i+1} r_i  + r_{i+1},\  0\leq r_{i+1} < r_i \quad  0\leq i \leq N$$.

If no  $r_i, i\in \mathbb{N}$, is equal to 0, we can continue this construction indefinitely. So we obtain a strictly decreasing sequence $(r_i)_{i \in \mathbb{N}}$ of positive numbers : it is impossible. Therefore, there exists an index $k$ such as $r_{k+2} = 0$, this is the end of the algorithm.

\begin{align*}
a &= b q + r,  &0 \leq r <b\
b &= q_1 r + r_1, &0 \leq r_1 <r\
r &= q_2 r_1 + r_2,  &0\leq r_2 <r_1\
&\vdots\
r_{k-1} &= q_{k+1} r_k + r_{k+1}, &0 \leq r_{k+1} <r_k\
r_k &= q_{k+2} r_{k+1}, &r_{k+2} = 0\
\end{align*}

From exercise 1,  $r_{i-1} \wedge r_{i} = r_{i} \wedge r_{i+1}, 0 \leq i \leq k$,  so

$$a \wedge b = b \wedge r = \cdots = r_k \wedge r_{k+1} = r_{k+1} \wedge r_{k+2} =  r_{k+1} \wedge 0 = r_{k+1}.$$

The last non zero remainder is the gcd of $a,b$. 
\end{proof}

Exercise 1.2

Answers

Comments

Exercise 1.2

Answers

Comments

Add answer