Gratest Common Divisor
Definition
- $a, b \in \mathbb{Z}$,
$b$ is said to be a divisor of $a$ if there is a $q \mathbb{Z}$ sucht that
\[a = bq.\]We denote
\[b \mid a.\]$b$ divides $a$. $a$ is a multiple of $b$.
■
Definition Common Divisor
- $a_{1}, \ldots, a_{k} \in \mathbb{Z}$,
- $d \in \mathbb{Z}$
$d$ is a common divisor of $a_{1}, \ldots, a_{k}$ if
\[d \mid a_{i} \quad \forall i.\]A common divisor $d$ is said to be the gratest common divisor if $d \in \mathbb{N}$ and for all common divisor $e$
\[e \mid d.\]The gratest common divisor $d$ of $a_{1}, \ldots, a_{k}$ is written
\[(a_{1}, \ldots, a_{k}) = d.\]■
Remark
If $a > 0$,
\[(a, a) = a.\] \[(a, 1) = 1.\]■
Proposition
- $a_{1}, \ldots, a_{k} \in \mathbb{Z}$,
(1)
(2)
\[(a_{1}, a_{2}) = d_{2}, \ (d_{2}, a_{3}) = d_{3}, \ldots (d_{k-1}, a_{k}) = d_{k} .\]$d_{k}$ is the greatest common divisor of $a_{1}, \ldots, a_{k}$.
(3) If $(a, b) = 1$ and $a \mid bc$,
\[a \mid c.\]proof
$\Box$