tags: 2023冬期講習会

Day 5

はじめに

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

---

定義

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

$a$，

$b$，

$q$，

$r$を整数とし

$a=bq+r$とする。

$a$と

$b$の最大公約数を

$k$すると，

$$k=(a,b)=(b,r)$$

---

互除法の性質(1)

$$(a,b)=(b,a)$$

$$(na,nb)=n(a,b)$$

---

負の数について

$a$と

$b$が整数であるときの最大公約数

$(a,b)$について，

$$(a,b)=(-a,b)=(a,-b)=(-a,-b)$$

---

0の導入

$$(x,0)=x(x\in \mathbb{N})$$

---

0と0の最大公約数は0

$$(0,0)=0$$

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

---

互除法の性質(2)

$$(b,c)=1\mathrm{の}\mathrm{と}\mathrm{き}，(a,b)=(ac,b)$$

---