ユークリッドの互除法

SNS Accounts

SHARE

Side Menu

高校数学編

論理・集合

数・式

変化

空間

確率

論理・集合

数・式

群環体論

線形代数学

整数論

表現論

実解析学

複素解析学

関数解析学

位相幾何学

微分幾何学

代数幾何学

Side Menu

数・式

有理式

8.ユークリッドの互除法

ユークリッドの互除法の原理

\(a=bq+r\)  

\(0<r<b\)のとき     \(gcd(a,b)=gcd(b,r)\)
\(r=0\)のとき        \(gcd(a,b)=b\)

証明

\(gcd(a,b)=m\),   \(gcd(b,r)=n\)とおく

除法の性質より

\((q \in \mathbb{Z},0<r<b)\)

①\(a=bq+r\)
②\(r=a-bq\)

①より
\(a=n(b'q+r')\)とかけるので
\(n\)は\(a\)の約数、\(n\)は\(a\)と\(b\)の公約数となる

\(m\)は\(a\)と\(b\)の公約数で最大なので
\(n≤m\)

②より
\(r=m(a'-b'q)\)とかけるので
\(m\)は\(r\)の約数、\(m\)は\(b\)と\(r\)の公約数となる

\(n\)は\(b\)と\(r\)の公約数で最大なので
\(m≤n\)

よって\(m=n\)

\(gcd(899,696)=gcd(696,203)=gcd(203,87)=gcd(87,29)=29\)

←剰余と合同式

線形代数学
Menu

一次不定方程式→