Euclidean algorithm for integers

整数辗转相除法

Number Theory · Undergraduate · Mathematics Resources editorial compilation (AI-assisted)

Other names / variants: Euclidean algorithm

Translation evidence: Literature usage

Meaning in context

Repeatedly replace a nonnegative integer pair $(a,b)$ with $(b,a\bmod b)$ while $b>0$; when $b=0$, the terminal first coordinate $a$ is the gcd of the original pair, including $\gcd(0,0)=0$ by convention.

对非负整数对 $(a,b)$，当 $b>0$ 时反复替换为 $(b,a\bmod b)$；当 $b=0$ 时，终止数对的第一个坐标 $a$ 就是原数对的最大公因数，包括约定的 $\gcd(0,0)=0$。

Example

$(30,18)\to(18,12)\to(12,6)\to(6,0)$ gives gcd $6$.

Usage and distinctions

The extended algorithm additionally computes integer linear-combination coefficients; ordinary remainder iteration computes only the gcd.

Read the encyclopedia explanation

Recommended reading in this subject · Preparation & skip guidance

Definition sources

1. Thomas W. Judson — Abstract Algebra: Theory and ApplicationsSubsection 2.2.1, The Euclidean Algorithm, Example 2.2.4 · Checked 2026-10-14

Translation sources

1. 张神星 — 初等数论习题课，中国科学院大学课程讲义，合肥工业大学托管第一章，4 补充，printed page 2, proof naming 辗转相除法 · Checked 2026-10-14

Original encyclopedia and terminology content: CC BY-SA 4.0. Contribute or report a correction.