Euclidean algorithm - Euclidean algorithm

A method for finding the greatest common divisor. Let _a1 and _a2 be natural numbers or polynomials. If they are natural numbers, _a1 ≧ _a2 . If they are polynomials, the degree of _a1 is greater than or equal to the degree of _a2 .

a ₁ =a ₂ q ₁ +a ₃ (a ₃ is the remainder)
a ₂ =a ₃ q ₂ +a ₄ (a ₄ is the remainder)
…………
a _n-1 = a _n q _n-1 + a _n+1
(a _n+1 is the remainder)
a _n = a _{n + 1} q _n
Then, a _n+1 is the greatest common divisor of a ₁ and a _2. When _{a n+1} =1, a ₁ and a ₂ are mutually prime. The greatest common divisor of 3553 and 2584 is 323, which can be found as follows.

3553=2584×1+969
2584=969×2+646
969=646×1+323
646=323×2
[Terada Fumiyuki]

Source: Shogakukan Encyclopedia Nipponica About Encyclopedia Nipponica Information | Legend

最大公約数を求める方法。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
［寺田文行］

出典　小学館　日本大百科全書(ニッポニカ)日本大百科全書(ニッポニカ)について　情報 | 凡例