Exercise 1.1

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}}

Let $a$ and $b$ be nonzero integers. We can find nonzero integers $q$ and $r$ such that $a = qb + r$ where $0 \leq r < b$. Prove that $(a, b) = (b, r)$.

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}
Notation : if $a,b$ are integers in  $\mathbb{Z}$, $a \wedge b$ is the non negative greatest common divisor of  $a,b$, the generator in  $\mathbb{N} = \{0,1,2,\ldots\} $ of the ideal $(a,b) = a\mathbb{Z}+ b \mathbb{Z}$.

Let $d \in \mathbb{Z}$.

$\bullet$ If $d \mid a, d \mid b$, then  $d \mid a-qb = r$, so $d \mid b, d \mid r$.

$\bullet$ If $d \mid b, d \mid r$, then $d \mid qb+r = a$, so $d \mid a, d \mid b$.

$$ \forall d \in \mathbb{Z}, \  ( d \mid b, d \mid r)  \iff (d \mid a, d \mid b).$$

If $a = bq+r$, the set of common divisors of $a,b$ is equal to the set of common divisors of $b,r$.

As $a \wedge b$ is the smallest positive element of this set, so is  $b \wedge r$, we conclude that $a \wedge b = b \wedge r$.
\end{proof}

Exercise 1.1

Answers

Comments

Exercise 1.1

Answers

Comments

Add answer