ユークリッドの互除法

\(gcd(a,b)\)は\(a\)と\(b\)の最大公約数のことである

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

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

\(a=bq+r\)  

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

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

\(a=bq+r\)  

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

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

証明

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

除法の性質より

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

①\(a=bq+r\)
②\(b=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\)