ユークリッドの互除法（読み）ユークリッドのごじょほう

ブリタニカ国際大百科事典 小項目事典

ユークリッドの互除法
ユークリッドのごじょほう
Euclidean algorithm

二つの自然数 a₁と a₂の最大公約数（→約数）を求めるための一つの方法。a₁≧a₂として，次の割り算を実行する。

a1＝a2q1＋a3		q1は商，a3は余り
a2＝a3q2＋a4		q2は商，a4は余り
…………		…………
an-1＝anqn-1＋an+1		qn-1は商，an+1は余り
an＝an＋1qn		qnは商，余りはなし

最後に余りがなかったならば，この a_n+1が最初の 2数 a₁と a₂の最大公約数である。（→整数論，ユークリッド）

出典　ブリタニカ国際大百科事典 小項目事典

日本大百科全書(ニッポニカ)

ユークリッドの互除法
ゆーくりっどのごじょほう

最大公約数を求める方法。a₁、a₂を自然数あるいは整式とする。自然数のときは、a₁≧a₂で、整式のときは、a₁の次数のほうがa₂の次数以上であるとする。

　　a₁=a₂q₁+a₃　（a₃は剰余）
　　a₂=a₃q₂+a₄　（a₄は剰余）
　　　　…………
　　a_n-1=a_nq_n-1+a_n+1
　　　　　　　 　（a_n+1は剰余）
　　a_n=a_n+1q_n
となるとき、a_n+1がa₁とa₂の最大公約数である。a_n+1=1のときは、a₁とa₂は互いに素である。3553と2584の最大公約数は323であるが、これは次のようにして求める。

　　3553=2584×1+969
　　2584=969×2+646
　　969=646×1+323
　　646=323×2
［寺田文行］

出典　小学館　日本大百科全書(ニッポニカ)