---
title: ユークリッドの互除法の拡張
slideOptions:
theme: white
slideNumber: 'c/t'
center: false
# transition: 'none'
# keyboard: true
width: '93%'
height: '100%'

---

tags: `2023冬期講習会`

## Day 5
### はじめに

互除法の計算を整数で行うことができるように拡張します。そのためには，整数の最大公約数についてどう定義するかが問題となります。

---

### 定義

ユークリッドの互除法を整数に拡張するときに，次の関係が成り立つように構成を考えます。

:::info

$a$，$b$，$q$，$r$を整数とし$a=bq+r$とする。$a$と$b$の最大公約数を$k$すると，
$$k=(a,\,b)=(b,\,r)$$
:::
---

### 互除法の性質(1)

:::warning
$$(a,\,b)=(b,\,a)$$
:::

:::warning
$$(na,\,nb)=n(a,\,b)$$
:::
---

### 負の数について

$a$と$b$が整数であるときの最大公約数$(a,\,b)$について，

:::info
$$(a,\,b)=(-a,\,b)=(a,\,-b)=(-a,\,-b)$$
:::

---

### 0の導入

:::info
$$(x,\,0)=x\quad (x\in\mathbb{N})$$
:::
---

### 0と0の最大公約数は0

:::warning
$$(0,\,0)=0$$
:::

これは難しいので，こちらの解説をどうぞ。
https://note.com/katobungen/n/nb20d1c15ea2c

---

### 互除法の性質(2)

:::danger

$$(b,\,c)=1のとき，(a,b)=(ac,b)$$
:::

----