text:
Euclidean algorithm

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (c. 300 BC). It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (as $252 = 21 × 12$ and $105 = 21 × 5)$, and the same number 21 is also the GCD of 105 and $252 − 105 = 147$. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers. By reversing the steps or using the extended Euclidean algorithm, the GCD can be expressed as a linear combination of the two original numbers, that is the sum of the two numbers, each multiplied by an integer (for example, $21 = 5 × 105 + (−2) × 252$). The fact that the GCD can always be expressed in this way is known as Bézout's identity.

The version of the Euclidean algorithm described above—which follows Euclid's original presentation—can take many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by Gabriel Lamé in 1844 (Lamé's Theorem), and marks the beginning of computational complexity theory. Additional methods for improving the algorithm's efficiency were developed in the 20th century.

The Euclidean algorithm has many theoretical and practical applications. It is used for reducing fractions to their simplest form and for performing division in modular arithmetic. Computations using this algorithm form part of the cryptographic protocols that are used to secure internet communications, and in methods for breaking these cryptosystems by factoring large composite numbers. The Euclidean algorithm may be used to solve Diophantine equations, such as finding numbers that satisfy multiple congruences according to the Chinese remainder theorem, to construct continued fractions, and to find accurate rational approximations to real numbers. Finally, it can be used as a basic tool for proving theorems in number theory such as Lagrange's four-square theorem and the uniqueness of prime factorizations.

The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as Gaussian integers and polynomials of one variable. This led to modern abstract algebraic notions such as Euclidean domains.

Background: greatest common divisor
The Euclidean algorithm calculates the greatest common divisor (GCD) of two natural numbers $a$ and $b$. The greatest common divisor $g$ is the largest natural number that divides both $a$ and $b$ without leaving a remainder. Synonyms for GCD include greatest common factor (GCF), highest common factor (HCF), highest common divisor (HCD), and greatest common measure (GCM). The greatest common divisor is often written as $gcd(a, b)$ or, more simply, as $(a, b)$, although the latter notation is ambiguous, also used for concepts such as an ideal in the ring of integers, which is closely related to GCD.

If $gcd(a, b) = 1$, then $a$ and $b$ are said to be coprime (or relatively prime). This property does not imply that $a$ or $b$ are themselves prime numbers. For example, 6 and 35 factor as 6 = 2 × 3 and 35 = 5 × 7, so they are not prime, but their prime factors are different, so 6 and 35 are coprime, with no common factors other than 1.

Let $a×b$. Since $c$ and $c$ are both multiples of $a$, they can be written $g = gcd(a, b)$ and $b$, and there is no larger number $a = mg$ for which this is true. The natural numbers $a$ and $b$ must be coprime, since any common factor could be factored out of $g$ and $b = ng$ to make $m$ greater. Thus, any other number $n$ that divides both $m$ and $n$ must also divide $g$. The greatest common divisor $c$ of $a$ and $b$ is the unique (positive) common divisor of $g$ and $g$ that is divisible by any other common divisor $a$.

The greatest common divisor can be visualized as follows. Consider a rectangular area $b$ by $a$, and any common divisor $b$ that divides both $c$ and $a$ exactly. The sides of the rectangle can be divided into segments of length $b$, which divides the rectangle into a grid of squares of side length $c$. The GCD $a$ is the largest value of $b$ for which this is possible. For illustration, a $G > g$ rectangular area can be divided into a grid of: $24×60$ squares, $1×1$ squares, $2×2$ squares, $3×3$ squares, $4×4$ squares or $6×6$ squares. Therefore, $12×12$ is the GCD of $12$ and $24$. A $60$ rectangular area can be divided into a grid of $24×60$ squares, with two squares along one edge ($12×12$) and five squares along the other ($24/12 = 2$).

The greatest common divisor of two numbers $c$ and $c$ is the product of the prime factors shared by the two numbers, where each prime factor can be repeated as many times as it divides both $g$ and $c$. For example, since $60/12 = 5$ can be factored into $1386$, and $2 × 3 × 3 × 7 × 11$ can be factored into $3213$, the GCD of $3 × 3 × 3 × 7 × 17$ and $1386$ equals $3213$, the product of their shared prime factors (with 3 repeated since $63 = 3 × 3 × 7$ divides both). If two numbers have no common prime factors, their GCD is $3 × 3$ (obtained here as an instance of the empty product); in other words, they are coprime. A key advantage of the Euclidean algorithm is that it can find the GCD efficiently without having to compute the prime factors. Factorization of large integers is believed to be a computationally very difficult problem, and the security of many widely used cryptographic protocols is based upon its infeasibility.

Another definition of the GCD is helpful in advanced mathematics, particularly ring theory. The greatest common divisor $a$ of two nonzero numbers $b$ and $a$ is also their smallest positive integral linear combination, that is, the smallest positive number of the form $1$ where $b$ and $g$ are integers. The set of all integral linear combinations of $a$ and $b$ is actually the same as the set of all multiples of $u$ ($v$, where $a$ is an integer). In modern mathematical language, the ideal generated by $b$ and $g$ is the ideal generated by $mg$ alone (an ideal generated by a single element is called a principal ideal, and all ideals of the integers are principal ideals). Some properties of the GCD are in fact easier to see with this description, for instance the fact that any common divisor of $m$ and $a$ also divides the GCD (it divides both terms of $ua + vb$). The equivalence of this GCD definition with the other definitions is described below.

The GCD of three or more numbers equals the product of the prime factors common to all the numbers, but it can also be calculated by repeatedly taking the GCDs of pairs of numbers. For example,

Thus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of arbitrarily many integers.

Procedure
The Euclidean algorithm can be thought of as constructing a sequence of non-negative integers that begins with the two given integers $$r_{-2} = a$$ and $$r_{-1} = b$$ and will eventually terminate with the integer zero: $$\{ r_{-2} = a,\ r_{-1} = b,\ r_0,\ r_1,\ \cdots,\ r_{n-1},\ r_n = 0 \}$$ with $$r_{k+1} < r_k$$. The integer $$r_{n-1}$$ will then be the GCD and we can state $$\text{gcd}(a,b) = r_{n-1}$$. The algorithm indicates how to construct the intermediate remainders $$r_k$$ via division-with-remainder on the preceding pair $$(r_{k-2},\ r_{k-1})$$ by finding an integer quotient $$q_k$$ so that:

 * $$r_{k-2} = q_k \cdot r_{k-1} + r_k \text{,   with } \ r_{k-1} > r_k \geq 0.$$

Because the sequence of non-negative integers $$\{ r_k \}$$ is strictly decreasing, it eventually must terminate. In other words, since $$r_k \ge 0$$ for every $$k$$, and each $$r_k$$ is an integer that is strictly smaller than the preceding $$r_{k-1}$$, there eventually cannot be a non-negative integer smaller than zero, and hence the algorithm must terminate. In fact, the algorithm will always terminate at the n-th step with $$r_n$$ equal to zero.

To illustrate, suppose the GCD of 1071 and 462 is requested. The sequence is initially $$\{r_{-2} = 1071,\ r_{-1} = 462 \}$$ and in order to find $$r_0$$, we need to find integers $$q_0$$ and $$r_0 < r_{-1}$$ such that:

 * $$1071 = q_0 \cdot 462 + r_0$$.

This is the quotient $$q_0 = 2$$ since $$1071 = 2 \cdot 462 + 147$$. This determines $$r_0 = 147$$ and so the sequence is now $$\{1071,\ 462,\ r_0 = 147 \}$$. The next step is to continue the sequence to find $$r_1$$ by finding integers $$q_1$$ and $$r_1 < r_0$$ such that:

 * $$462 = q_1 \cdot 147 + r_1$$.

This is the quotient $$q_1 = 3$$ since $$462 = 3 \cdot 147 + 21$$. This determines $$r_1 = 21$$ and so the sequence is now $$\{1071,\ 462,\ 147,\ r_1 = 21 \}$$. The next step is to continue the sequence to find $$r_2$$ by finding integers $$q_2$$ and $$r_2 < r_1$$ such that:

 * $$147 = q_2 \cdot 21 + r_2$$.

This is the quotient $$q_2 = 7$$ since $$147 = 7 \cdot 21 + 0$$. This determines $$r_2 = 0$$ and so the sequence is completed as $$\{1071,\ 462,\ 147,\ 21,\ r_2 = 0 \}$$ as no further non-negative integer smaller than $$0$$ can be found. The penultimate remainder $$21$$ is therefore the requested GCD:

 * $$\text{gcd}(1071,\ 462) = 21.$$

We can generalize slightly by dropping any ordering requirement on the initial two values $$a$$ and $$b$$. If $$a = b$$, the algorithm may continue and trivially find that $$\text{gcd}(a,\ a) = a$$ as the sequence of remainders will be $$\{a,\ a,\ 0\}$$. If $$a < b$$, then we can also continue since $$a \equiv 0 \cdot b + a$$, suggesting the next remainder should be $$a$$ itself, and the sequence is $$\{a,\ b,\ a,\ \cdots \}$$. Normally, this would be invalid because it breaks the requirement $$r_0 < r_{-1}$$ but now we have $$a < b$$ by construction, so the requirement is automatically satisfied and the Euclidean algorithm can continue as normal. Therefore, dropping any ordering between the first two integers does not affect the conclusion that the sequence must eventually terminate because the next remainder will always satisfy $$r_0 < b$$ and everything continues as above. The only modifications that need to be made are that $$r_{k} < r_{k-1}$$ only for $$k \ge 0$$, and that the sub-sequence of non-negative integers $$\{ r_{k-1} \}$$ for $$k \ge 0$$ is strictly decreasing, therefore excluding $$a = r_{-2}$$ from both statements.

Proof of validity
The validity of the Euclidean algorithm can be proven by a two-step argument. In the first step, the final nonzero remainder rN−1 is shown to divide both a and b. Since it is a common divisor, it must be less than or equal to the greatest common divisor g. In the second step, it is shown that any common divisor of a and b, including g, must divide rN−1; therefore, g must be less than or equal to rN−1. These two opposite inequalities imply rN−1 = g.

To demonstrate that rN−1 divides both a and b (the first step), rN−1 divides its predecessor rN−2

since the final remainder rN is zero. rN−1 also divides its next predecessor rN−3

because it divides both terms on the right-hand side of the equation. Iterating the same argument, rN−1 divides all the preceding remainders, including a and b. None of the preceding remainders rN−2, rN−3, etc. divide a and b, since they leave a remainder. Since rN−1 is a common divisor of a and b, rN−1 ≤ g.

In the second step, any natural number c that divides both a and b (in other words, any common divisor of a and b) divides the remainders rk. By definition, a and b can be written as multiples of c : a = mc and b = nc, where m and n are natural numbers. Therefore, c divides the initial remainder r0, since r0 = a − q0b = mc − q0nc = (m − q0n)c. An analogous argument shows that c also divides the subsequent remainders r1, r2, etc. Therefore, the greatest common divisor g must divide rN−1, which implies that g ≤ rN−1. Since the first part of the argument showed the reverse (rN−1 ≤ g), it follows that g = rN−1. Thus, g is the greatest common divisor of all the succeeding pairs:

Worked example

For illustration, the Euclidean algorithm can be used to find the greatest common divisor of a = 1071 and b = 462. To begin, multiples of 462 are subtracted from 1071 until the remainder is less than 462. Two such multiples can be subtracted (q0 = 2), leaving a remainder of 147:

Then multiples of 147 are subtracted from 462 until the remainder is less than 147. Three multiples can be subtracted (q1 = 3), leaving a remainder of 21:

Then multiples of 21 are subtracted from 147 until the remainder is less than 21. Seven multiples can be subtracted (q2 = 7), leaving no remainder:

Since the last remainder is zero, the algorithm ends with 21 as the greatest common divisor of 1071 and 462. This agrees with the gcd(1071, 462) found by prime factorization above. In tabular form, the steps are:

Visualization
The Euclidean algorithm can be visualized in terms of the tiling analogy given above for the greatest common divisor. Assume that we wish to cover an a×b rectangle with square tiles exactly, where a is the larger of the two numbers. We first attempt to tile the rectangle using b×b square tiles; however, this leaves an r0×b residual rectangle untiled, where r0 < b. We then attempt to tile the residual rectangle with r0×r0 square tiles. This leaves a second residual rectangle r1×r0, which we attempt to tile using r1×r1 square tiles, and so on. The sequence ends when there is no residual rectangle, i.e., when the square tiles cover the previous residual rectangle exactly. The length of the sides of the smallest square tile is the GCD of the dimensions of the original rectangle. For example, the smallest square tile in the adjacent figure is 21×21 (shown in red), and 21 is the GCD of 1071 and 462, the dimensions of the original rectangle (shown in green).

Euclidean division
At every step k, the Euclidean algorithm computes a quotient qk and remainder rk from two numbers rk−1 and rk−2

where the rk is non-negative and is strictly less than the absolute value of rk−1. The theorem which underlies the definition of the Euclidean division ensures that such a quotient and remainder always exist and are unique.

In Euclid's original version of the algorithm, the quotient and remainder are found by repeated subtraction; that is, rk−1 is subtracted from rk−2 repeatedly until the remainder rk is smaller than rk−1. After that rk and rk−1 are exchanged and the process is iterated. Euclidean division reduces all the steps between two exchanges into a single step, which is thus more efficient. Moreover, the quotients are not needed, thus one may replace Euclidean division by the modulo operation, which gives only the remainder. Thus the iteration of the Euclidean algorithm becomes simply

Implementations
Implementations of the algorithm may be expressed in pseudocode. For example, the division-based version may be programmed as

function gcd(a, b)    while b ≠ 0 t := b        b := a mod b         a := t     return a

At the beginning of the kth iteration, the variable b holds the latest remainder rk−1, whereas the variable a holds its predecessor, rk−2. The step b := a mod b is equivalent to the above recursion formula rk ≡ rk−2 mod rk−1. The temporary variable t holds the value of rk−1 while the next remainder rk is being calculated. At the end of the loop iteration, the variable b holds the remainder rk, whereas the variable a holds its predecessor, rk−1.

(If negative inputs are allowed, or if the mod function may return negative values, the last line must be changed into return abs(a).)

In the subtraction-based version, which was Euclid's original version, the remainder calculation is replaced by repeated subtraction. Contrary to the division-based version, which works with arbitrary integers as input, the subtraction-based version supposes that the input consists of positive integers and stops when a = b:

function gcd(a, b)    while a ≠ b          if a > b             a := a − b         else b := b − a    return a

The variables a and b alternate holding the previous remainders rk−1 and rk−2. Assume that a is larger than b at the beginning of an iteration; then a equals rk−2, since rk−2 > rk−1. During the loop iteration, a is reduced by multiples of the previous remainder b until a is smaller than b. Then a is the next remainder rk. Then b is reduced by multiples of a until it is again smaller than a, giving the next remainder rk+1, and so on.

The recursive version is based on the equality of the GCDs of successive remainders and the stopping condition gcd(rN−1, 0) = rN−1.

function gcd(a, b)    if b = 0 return a    else return gcd(b, a mod b)

(As above, if negative inputs are allowed, or if the mod function may return negative values, the instruction "return a" must be changed into "return max(a, −a)".)

For illustration, the gcd(1071, 462) is calculated from the equivalent gcd(462, 1071 mod 462) = gcd(462, 147). The latter GCD is calculated from the gcd(147, 462 mod 147) = gcd(147, 21), which in turn is calculated from the gcd(21, 147 mod 21) = gcd(21, 0) = 21.

Method of least absolute remainders
In another version of Euclid's algorithm, the quotient at each step is increased by one if the resulting negative remainder is smaller in magnitude than the typical positive remainder. Previously, the equation

assumed that $ua + vb$. However, an alternative negative remainder $gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b).$ can be computed:

if $r_{N−2} = q_{N} r_{N−1}$ or

if $r_{N−3} = q_{N−1} r_{N−2} + r_{N−1}$.

If $g = gcd(a, b) = gcd(b, r_{0}) = gcd(r_{0}, r_{1}) = … = gcd(r_{N−2}, r_{N−1}) = r_{N−1}.$ is replaced by $1071 = 2 × 462 + 147.$ when $462 = 3 × 147 + 21.$, then one gets a variant of Euclidean algorithm such that

at each step.

Leopold Kronecker has shown that this version requires the fewest steps of any version of Euclid's algorithm. More generally, it has been proven that, for every input numbers a and b, the number of steps is minimal if and only if $147 = 7 × 21 + 0.$ is chosen in order that $$\left |\frac{r_{k+1}}{r_k}\right |<\frac{1}{\varphi}\sim 0.618,$$ where $$\varphi$$ is the golden ratio.

Historical development

The Euclidean algorithm is one of the oldest algorithms in common use. It appears in Euclid's Elements (c. 300 BC), specifically in Book 7 (Propositions 1–2) and Book 10 (Propositions 2–3). In Book 7, the algorithm is formulated for integers, whereas in Book 10, it is formulated for lengths of line segments. (In modern usage, one would say it was formulated there for real numbers. But lengths, areas, and volumes, represented as real numbers in modern usage, are not measured in the same units and there is no natural unit of length, area, or volume; the concept of real numbers was unknown at that time.) The latter algorithm is geometrical. The GCD of two lengths a and b corresponds to the greatest length g that measures a and b evenly; in other words, the lengths a and b are both integer multiples of the length g.

The algorithm was probably not discovered by Euclid, who compiled results from earlier mathematicians in his Elements. The mathematician and historian B. L. van der Waerden suggests that Book VII derives from a textbook on number theory written by mathematicians in the school of Pythagoras. The algorithm was probably known by Eudoxus of Cnidus (about 375 BC). The algorithm may even pre-date Eudoxus, judging from the use of the technical term ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction) in works by Euclid and Aristotle.

Centuries later, Euclid's algorithm was discovered independently both in India and in China, primarily to solve Diophantine equations that arose in astronomy and making accurate calendars. In the late 5th century, the Indian mathematician and astronomer Aryabhata described the algorithm as the "pulverizer", perhaps because of its effectiveness in solving Diophantine equations. Although a special case of the Chinese remainder theorem had already been described in the Chinese book Sunzi Suanjing, the general solution was published by Qin Jiushao in his 1247 book Shushu Jiuzhang (數書九章 Mathematical Treatise in Nine Sections). The Euclidean algorithm was first described numerically and popularized in Europe in the second edition of Bachet's Problèmes plaisants et délectables (Pleasant and enjoyable problems, 1624). In Europe, it was likewise used to solve Diophantine equations and in developing continued fractions. The extended Euclidean algorithm was published by the English mathematician Nicholas Saunderson, who attributed it to Roger Cotes as a method for computing continued fractions efficiently.

In the 19th century, the Euclidean algorithm led to the development of new number systems, such as Gaussian integers and Eisenstein integers. In 1815, Carl Gauss used the Euclidean algorithm to demonstrate unique factorization of Gaussian integers, although his work was first published in 1832. Gauss mentioned the algorithm in his Disquisitiones Arithmeticae (published 1801), but only as a method for continued fractions. Peter Gustav Lejeune Dirichlet seems to have been the first to describe the Euclidean algorithm as the basis for much of number theory. Lejeune Dirichlet noted that many results of number theory, such as unique factorization, would hold true for any other system of numbers to which the Euclidean algorithm could be applied. Lejeune Dirichlet's lectures on number theory were edited and extended by Richard Dedekind, who used Euclid's algorithm to study algebraic integers, a new general type of number. For example, Dedekind was the first to prove Fermat's two-square theorem using the unique factorization of Gaussian integers. Dedekind also defined the concept of a Euclidean domain, a number system in which a generalized version of the Euclidean algorithm can be defined (as described below). In the closing decades of the 19th century, the Euclidean algorithm gradually became eclipsed by Dedekind's more general theory of ideals.

Other applications of Euclid's algorithm were developed in the 19th century. In 1829, Charles Sturm showed that the algorithm was useful in the Sturm chain method for counting the real roots of polynomials in any given interval.

The Euclidean algorithm was the first integer relation algorithm, which is a method for finding integer relations between commensurate real numbers. Several novel integer relation algorithms have been developed, such as the algorithm of Helaman Ferguson and R.W. Forcade (1979) and the LLL algorithm.

In 1969, Cole and Davie developed a two-player game based on the Euclidean algorithm, called The Game of Euclid, which has an optimal strategy. The players begin with two piles of a and b stones. The players take turns removing m multiples of the smaller pile from the larger. Thus, if the two piles consist of x and y stones, where x is larger than y, the next player can reduce the larger pile from x stones to x − my stones, as long as the latter is a nonnegative integer. The winner is the first player to reduce one pile to zero stones.

Bézout's identity
Bézout's identity states that the greatest common divisor g of two integers a and b can be represented as a linear sum of the original two numbers a and b. In other words, it is always possible to find integers s and t such that g = sa + tb.

The integers s and t can be calculated from the quotients q0, q1, etc. by reversing the order of equations in Euclid's algorithm. Beginning with the next-to-last equation, g can be expressed in terms of the quotient qN−1 and the two preceding remainders, rN−2 and rN−3:

Those two remainders can be likewise expressed in terms of their quotients and preceding remainders,

 * $1071 = q_{0} 462 + r_{0}$ and

Substituting these formulae for rN−2 and rN−3 into the first equation yields g as a linear sum of the remainders rN−4 and rN−5. The process of substituting remainders by formulae involving their predecessors can be continued until the original numbers a and b are reached:

After all the remainders r0, r1, etc. have been substituted, the final equation expresses g as a linear sum of a and b, so that g = sa + tb.

The Euclidean algorithm, and thus Bezout's identity, can be generalized to the context of Euclidean domains.

Principal ideals and related problems
Bézout's identity provides yet another definition of the greatest common divisor g of two numbers a and b. Consider the set of all numbers ua + vb, where u and v are any two integers. Since a and b are both divisible by g, every number in the set is divisible by g. In other words, every number of the set is an integer multiple of g. This is true for every common divisor of a and b. However, unlike other common divisors, the greatest common divisor is a member of the set; by Bézout's identity, choosing u = s and v = t gives g. A smaller common divisor cannot be a member of the set, since every member of the set must be divisible by g. Conversely, any multiple m of g can be obtained by choosing u = ms and v = mt, where s and t are the integers of Bézout's identity. This may be seen by multiplying Bézout's identity by m,

Therefore, the set of all numbers ua + vb is equivalent to the set of multiples m of g. In other words, the set of all possible sums of integer multiples of two numbers (a and b) is equivalent to the set of multiples of gcd(a, b). The GCD is said to be the generator of the ideal of a and b. This GCD definition led to the modern abstract algebraic concepts of a principal ideal (an ideal generated by a single element) and a principal ideal domain (a domain in which every ideal is a principal ideal).

Certain problems can be solved using this result. For example, consider two measuring cups of volume a and b. By adding/subtracting u multiples of the first cup and v multiples of the second cup, any volume ua + vb can be measured out. These volumes are all multiples of g = gcd(a, b).

Extended Euclidean algorithm
The integers s and t of Bézout's identity can be computed efficiently using the extended Euclidean algorithm. This extension adds two recursive equations to Euclid's algorithm

with the starting values

Using this recursion, Bézout's integers s and t are given by s = sN and t = tN, where N+1 is the step on which the algorithm terminates with rN+1 = 0.

The validity of this approach can be shown by induction. Assume that the recursion formula is correct up to step k − 1 of the algorithm; in other words, assume that

for all j less than k. The kth step of the algorithm gives the equation

Since the recursion formula has been assumed to be correct for rk−2 and rk−1, they may be expressed in terms of the corresponding s and t variables

Rearranging this equation yields the recursion formula for step k, as required

Matrix method
The integers s and t can also be found using an equivalent matrix method. The sequence of equations of Euclid's algorithm

\begin{align} a & = q_0 b + r_0 \\ b & = q_1 r_0 + r_1 \\ & \,\,\,\vdots \\ r_{N-2} & = q_N r_{N-1} + 0 \end{align} $$

can be written as a product of 2×2 quotient matrices multiplying a two-dimensional remainder vector

\begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} b \\ r_0 \end{pmatrix} = \begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_0 \\ r_1 \end{pmatrix} = \cdots = \prod_{i=0}^N \begin{pmatrix} q_i & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix} \,. $$

Let M represent the product of all the quotient matrices

\mathbf{M} = \begin{pmatrix} m_{11} & m_{12} \\ m_{21} & m_{22} \end{pmatrix} = \prod_{i=0}^N \begin{pmatrix} q_i & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_1 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} q_{N} & 1 \\ 1 & 0 \end{pmatrix} \,. $$

This simplifies the Euclidean algorithm to the form

\begin{pmatrix} a \\ b \end{pmatrix} = \mathbf{M} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix} = \mathbf{M} \begin{pmatrix} g \\ 0 \end{pmatrix} \,. $$

To express g as a linear sum of a and b, both sides of this equation can be multiplied by the inverse of the matrix M. The determinant of M equals (−1)N+1, since it equals the product of the determinants of the quotient matrices, each of which is negative one. Since the determinant of M is never zero, the vector of the final remainders can be solved using the inverse of M

\begin{pmatrix} g \\ 0 \end{pmatrix} = \mathbf{M}^{-1} \begin{pmatrix} a \\ b \end{pmatrix} = (-1)^{N+1} \begin{pmatrix} m_{22} & -m_{12} \\ -m_{21} & m_{11} \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} \,. $$

Since the top equation gives

the two integers of Bézout's identity are s = (−1)N+1m22 and t = (−1)Nm12. The matrix method is as efficient as the equivalent recursion, with two multiplications and two additions per step of the Euclidean algorithm.

Euclid's lemma and unique factorization
Bézout's identity is essential to many applications of Euclid's algorithm, such as demonstrating the unique factorization of numbers into prime factors. To illustrate this, suppose that a number L can be written as a product of two factors u and v, that is, L = uv. If another number w also divides L but is coprime with u, then w must divide v, by the following argument: If the greatest common divisor of u and w is 1, then integers s and t can be found such that

by Bézout's identity. Multiplying both sides by v gives the relation:

Since w divides both terms on the right-hand side, it must also divide the left-hand side, v. This result is known as Euclid's lemma. Specifically, if a prime number divides L, then it must divide at least one factor of L. Conversely, if a number w is coprime to each of a series of numbers a1, a2, ..., an, then w is also coprime to their product, a1 × a2 × ... × an.

Euclid's lemma suffices to prove that every number has a unique factorization into prime numbers. To see this, assume the contrary, that there are two independent factorizations of L into m and n prime factors, respectively

Since each prime p divides L by assumption, it must also divide one of the q factors; since each q is prime as well, it must be that p = q. Iteratively dividing by the p factors shows that each p has an equal counterpart q; the two prime factorizations are identical except for their order. The unique factorization of numbers into primes has many applications in mathematical proofs, as shown below.

Linear Diophantine equations

Diophantine equations are equations in which the solutions are restricted to integers; they are named after the 3rd-century Alexandrian mathematician Diophantus. A typical linear Diophantine equation seeks integers x and y such that

where a, b and c are given integers. This can be written as an equation for x in modular arithmetic:

Let g be the greatest common divisor of a and b. Both terms in ax + by are divisible by g; therefore, c must also be divisible by g, or the equation has no solutions. By dividing both sides by c/g, the equation can be reduced to Bezout's identity

where s and t can be found by the extended Euclidean algorithm. This provides one solution to the Diophantine equation, x1 = s (c/g) and y1 = t (c/g).

In general, a linear Diophantine equation has no solutions, or an infinite number of solutions. To find the latter, consider two solutions, (x1, y1) and (x2, y2), where

or equivalently

Therefore, the smallest difference between two x solutions is b/g, whereas the smallest difference between two y solutions is a/g. Thus, the solutions may be expressed as

By allowing u to vary over all possible integers, an infinite family of solutions can be generated from a single solution (x1, y1). If the solutions are required to be positive integers (x > 0, y > 0), only a finite number of solutions may be possible. This restriction on the acceptable solutions allows some systems of Diophantine equations with more unknowns than equations to have a finite number of solutions; this is impossible for a system of linear equations when the solutions can be any real number (see Underdetermined system).

Multiplicative inverses and the RSA algorithm
A finite field is a set of numbers with four generalized operations. The operations are called addition, subtraction, multiplication and division and have their usual properties, such as commutativity, associativity and distributivity. An example of a finite field is the set of 13 numbers {0, 1, 2, ..., 12} using modular arithmetic. In this field, the results of any mathematical operation (addition, subtraction, multiplication, or division) is reduced modulo 13; that is, multiples of 13 are added or subtracted until the result is brought within the range 0–12. For example, the result of 5 × 7 = 35 mod 13 = 9. Such finite fields can be defined for any prime p; using more sophisticated definitions, they can also be defined for any power m of a prime pm. Finite fields are often called Galois fields, and are abbreviated as GF(p) or GF(pm).

In such a field with m numbers, every nonzero element a has a unique modular multiplicative inverse, a−1 such that aa−1 = a−1a ≡ 1 mod m. This inverse can be found by solving the congruence equation ax ≡ 1 mod m, or the equivalent linear Diophantine equation

This equation can be solved by the Euclidean algorithm, as described above. Finding multiplicative inverses is an essential step in the RSA algorithm, which is widely used in electronic commerce; specifically, the equation determines the integer used to decrypt the message. Although the RSA algorithm uses rings rather than fields, the Euclidean algorithm can still be used to find a multiplicative inverse where one exists. The Euclidean algorithm also has other applications in error-correcting codes; for example, it can be used as an alternative to the Berlekamp–Massey algorithm for decoding BCH and Reed–Solomon codes, which are based on Galois fields.

Chinese remainder theorem
Euclid's algorithm can also be used to solve multiple linear Diophantine equations. Such equations arise in the Chinese remainder theorem, which describes a novel method to represent an integer x. Instead of representing an integer by its digits, it may be represented by its remainders xi modulo a set of N coprime numbers mi:

\begin{align} x_1 & \equiv x \pmod {m_1} \\ x_2 & \equiv x \pmod {m_2} \\ & \,\,\,\vdots \\ x_N & \equiv x \pmod {m_N} \,. \end{align} $$

The goal is to determine x from its N remainders xi. The solution is to combine the multiple equations into a single linear Diophantine equation with a much larger modulus M that is the product of all the individual moduli mi, and define Mi as

 * $$ M_i = \frac M {m_i}. $$

Thus, each Mi is the product of all the moduli except mi. The solution depends on finding N new numbers hi such that

 * $$ M_i h_i \equiv 1 \pmod {m_i} \,. $$

With these numbers hi, any integer x can be reconstructed from its remainders xi by the equation

 * $$ x \equiv (x_1 M_1 h_1 + x_2 M_2 h_2 + \cdots + x_N M_N h_N) \pmod M \,.$$

Since these numbers hi are the multiplicative inverses of the Mi, they may be found using Euclid's algorithm as described in the previous subsection.

Stern–Brocot tree
The Euclidean algorithm can be used to arrange the set of all positive rational numbers into an infinite binary search tree, called the Stern–Brocot tree. The number 1 (expressed as a fraction 1/1) is placed at the root of the tree, and the location of any other number a/b can be found by computing gcd(a,b) using the original form of the Euclidean algorithm, in which each step replaces the larger of the two given numbers by its difference with the smaller number (not its remainder), stopping when two equal numbers are reached. A step of the Euclidean algorithm that replaces the first of the two numbers corresponds to a step in the tree from a node to its right child, and a step that replaces the second of the two numbers corresponds to a step in the tree from a node to its left child. The sequence of steps constructed in this way does not depend on whether a/b is given in lowest terms, and forms a path from the root to a node containing the number a/b. This fact can be used to prove that each positive rational number appears exactly once in this tree.

For example, 3/4 can be found by starting at the root, going to the left once, then to the right twice:

\begin{align} & \gcd(3,4) & \leftarrow \\ = {} & \gcd(3,1) & \rightarrow \\ = {} & \gcd(2,1) & \rightarrow \\ = {} & \gcd(1,1). \end{align} $$

The Euclidean algorithm has almost the same relationship to another binary tree on the rational numbers called the Calkin–Wilf tree. The difference is that the path is reversed: instead of producing a path from the root of the tree to a target,  it produces a path from the target to the root.

Continued fractions
The Euclidean algorithm has a close relationship with continued fractions. The sequence of equations can be written in the form

\begin{align} \frac a b &= q_0 + \frac{r_0} b \\ \frac b {r_0} &= q_1 + \frac{r_1}{r_0} \\ \frac{r_0}{r_1} &= q_2 + \frac{r_2}{r_1} \\ & \,\,\, \vdots \\ \frac{r_{k-2}}{r_{k-1}} &= q_k + \frac{r_k}{r_{k-1}} \\ & \,\,\, \vdots \\ \frac{r_{N-2}}{r_{N-1}} &= q_N\,. \end{align} $$

The last term on the right-hand side always equals the inverse of the left-hand side of the next equation. Thus, the first two equations may be combined to form

 * $$\frac a b = q_0 + \cfrac 1 {q_1 + \cfrac{r_1}{r_0}} \,.$$

The third equation may be used to substitute the denominator term r1/r0, yielding

 * $$\frac a b = q_0 + \cfrac 1 {q_1 + \cfrac 1 {q_2 + \cfrac{r_2}{r_1}}}\,. $$

The final ratio of remainders rk/rk−1 can always be replaced using the next equation in the series, up to the final equation. The result is a continued fraction

 * $$\frac a b = q_0 + \cfrac 1 {q_1 + \cfrac 1 {q_2 + \cfrac{1}{\ddots + \cfrac 1 {q_N}}}} = [ q_0; q_1, q_2, \ldots, q_N ] \,.$$

In the worked example above, the gcd(1071, 462) was calculated, and the quotients qk were 2, 3 and 7, respectively. Therefore, the fraction 1071/462 may be written

 * $$\frac{1071}{462} = 2 + \cfrac 1 {3 + \cfrac 1 7} = [2; 3, 7]$$

as can be confirmed by calculation.

Factorization algorithms
Calculating a greatest common divisor is an essential step in several integer factorization algorithms, such as Pollard's rho algorithm, Shor's algorithm, Dixon's factorization method and the Lenstra elliptic curve factorization. The Euclidean algorithm may be used to find this GCD efficiently. Continued fraction factorization uses continued fractions, which are determined using Euclid's algorithm.

Algorithmic efficiency

The computational efficiency of Euclid's algorithm has been studied thoroughly. This efficiency can be described by the number of division steps the algorithm requires, multiplied by the computational expense of each step. The first known analysis of Euclid's algorithm is due to A. A. L. Reynaud in 1811, who showed that the number of division steps on input (u, v) is bounded by v; later he improved this to v/2 + 2. Later, in 1841, P. J. E. Finck showed that the number of division steps is at most 2 log2 v + 1, and hence Euclid's algorithm runs in time polynomial in the size of the input. Émile Léger, in 1837, studied the worst case, which is when the inputs are consecutive Fibonacci numbers. Finck's analysis was refined by Gabriel Lamé in 1844, who showed that the number of steps required for completion is never more than five times the number h of base-10 digits of the smaller number b.

In the uniform cost model (suitable for analyzing the complexity of gcd calculation on numbers that fit into a single machine word), each step of the algorithm takes constant time, and Lamé's analysis implies that the total running time is also O(h). However, in a model of computation suitable for computation with larger numbers, the computational expense of a single remainder computation in the algorithm can be as large as O(h2). In this case the total time for all of the steps of the algorithm can be analyzed using a telescoping series, showing that it is also O(h2). Modern algorithmic techniques based on the Schönhage–Strassen algorithm for fast integer multiplication can be used to speed this up, leading to quasilinear algorithms for the GCD.

Number of steps
The number of steps to calculate the GCD of two natural numbers, a and b, may be denoted by T(a, b). If g is the GCD of a and b, then a = mg and b = ng for two coprime numbers m and n. Then

as may be seen by dividing all the steps in the Euclidean algorithm by g. By the same argument, the number of steps remains the same if a and b are multiplied by a common factor w: T(a, b) = T(wa, wb). Therefore, the number of steps T may vary dramatically between neighboring pairs of numbers, such as T(a, b) and T(a, b + 1), depending on the size of the two GCDs.

The recursive nature of the Euclidean algorithm gives another equation

where T(x, 0) = 0 by assumption.

Worst-case
If the Euclidean algorithm requires N steps for a pair of natural numbers a > b > 0, the smallest values of a and b for which this is true are the Fibonacci numbers FN+2 and FN+1, respectively. More precisely, if the Euclidean algorithm requires N steps for the pair a > b, then one has a ≥ FN+2 and b ≥ FN+1. This can be shown by induction. If N = 1, b divides a with no remainder; the smallest natural numbers for which this is true is b = 1 and a = 2, which are F2 and F3, respectively. Now assume that the result holds for all values of N up to M − 1. The first step of the M-step algorithm is a = q0b + r0, and the Euclidean algorithm requires M − 1 steps for the pair b > r0. By induction hypothesis, one has b ≥ FM+1 and r0 ≥ FM. Therefore, a = q0b + r0 ≥ b + r0 ≥ FM+1 + FM = FM+2, which is the desired inequality. This proof, published by Gabriel Lamé in 1844, represents the beginning of computational complexity theory, and also the first practical application of the Fibonacci numbers.

This result suffices to show that the number of steps in Euclid's algorithm can never be more than five times the number of its digits (base 10). For if the algorithm requires N steps, then b is greater than or equal to FN+1 which in turn is greater than or equal to φN−1, where φ is the golden ratio. Since b ≥ φN−1, then N − 1 ≤ logφb. Since log10φ > 1/5, (N − 1)/5 < log10φ logφb = log10b. Thus, N ≤ 5 log10b. Thus, the Euclidean algorithm always needs less than O(h) divisions, where h is the number of digits in the smaller number b.

Average
The average number of steps taken by the Euclidean algorithm has been defined in three different ways. The first definition is the average time T(a) required to calculate the GCD of a given number a and a smaller natural number b chosen with equal probability from the integers 0 to a − 1

 * $$T(a) = \frac 1 a \sum_{0 \leq b<a} T(a, b).

$$

However, since T(a, b) fluctuates dramatically with the GCD of the two numbers, the averaged function T(a) is likewise "noisy".

To reduce this noise, a second average τ(a) is taken over all numbers coprime with a
 * $$\tau(a) = \frac 1 {\varphi(a)} \sum_{\begin{smallmatrix} 0 \leq b<a \\ \gcd(a, b) = 1 \end{smallmatrix}} T(a, b).

$$

There are φ(a) coprime integers less than a, where φ is Euler's totient function. This tau average grows smoothly with a

 * $$\tau(a) = \frac{12}{\pi^2}\ln 2 \ln a + C + O(a^{-1/6-\varepsilon})$$

with the residual error being of order a−(1/6) + ε, where ε is infinitesimal. The constant C in this formula is called Porter's constant and equals
 * $$C= -\frac 1 2 + \frac{6 \ln 2}{\pi^2}\left(4\gamma -\frac{24}{\pi^2}\zeta'(2) + 3\ln 2 - 2\right) \approx 1.467$$

where γ is the Euler–Mascheroni constant and ζ' is the derivative of the Riemann zeta function. The leading coefficient (12/π2) ln 2 was determined by two independent methods.

Since the first average can be calculated from the tau average by summing over the divisors d of a

 * $$ T(a) = \frac 1 a \sum_{d \mid a} \varphi(d) \tau(d)

$$

it can be approximated by the formula

 * $$T(a) \approx C + \frac{12}{\pi^2} \ln 2 \left(\ln a - \sum_{d \mid a} \frac{\Lambda(d)} d\right)$$

where Λ(d) is the Mangoldt function.

A third average Y(n) is defined as the mean number of steps required when both a and b are chosen randomly (with uniform distribution) from 1 to n

 * $$Y(n) = \frac 1 {n^2} \sum_{a=1}^n \sum_{b=1}^n T(a, b) = \frac 1 n \sum_{a=1}^n T(a).

$$

Substituting the approximate formula for T(a) into this equation yields an estimate for Y(n)
 * $$Y(n) \approx \frac{12}{\pi^2} \ln 2 \ln n + 0.06.$$

Computational expense per step
In each step k of the Euclidean algorithm, the quotient qk and remainder rk are computed for a given pair of integers rk−2 and rk−1

The computational expense per step is associated chiefly with finding qk, since the remainder rk can be calculated quickly from rk−2, rk−1, and qk

The computational expense of dividing h-bit numbers scales as $q_{0} = 2$, where $b$ is the length of the quotient.

For comparison, Euclid's original subtraction-based algorithm can be much slower. A single integer division is equivalent to the quotient q number of subtractions. If the ratio of a and b is very large, the quotient is large and many subtractions will be required. On the other hand, it has been shown that the quotients are very likely to be small integers. The probability of a given quotient q is approximately $r_{0} = 147$ where $462 = q_{1} 147 + r_{1}$. For illustration, the probability of a quotient of 1, 2, 3, or 4 is roughly 41.5%, 17.0%, 9.3%, and 5.9%, respectively. Since the operation of subtraction is faster than division, particularly for large numbers, the subtraction-based Euclid's algorithm is competitive with the division-based version. This is exploited in the binary version of Euclid's algorithm.

Combining the estimated number of steps with the estimated computational expense per step shows that the Euclid's algorithm grows quadratically (h2) with the average number of digits h in the initial two numbers a and b. Let $q_{1} = 3$ represent the number of digits in the successive remainders $r_{1} = 21$. Since the number of steps N grows linearly with h, the running time is bounded by

O\Big(\sum_{i<N}h_i(h_i-h_{i+1}+2)\Big)\subseteq O\Big(h\sum_{i<N}(h_i-h_{i+1}+2) \Big) \subseteq O(h(h_0+2N))\subseteq O(h^2).$$

Alternative methods
Euclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity. For comparison, the efficiency of alternatives to Euclid's algorithm may be determined.

One inefficient approach to finding the GCD of two natural numbers a and b is to calculate all their common divisors; the GCD is then the largest common divisor. The common divisors can be found by dividing both numbers by successive integers from 2 to the smaller number b. The number of steps of this approach grows linearly with b, or exponentially in the number of digits. Another inefficient approach is to find the prime factors of one or both numbers. As noted above, the GCD equals the product of the prime factors shared by the two numbers a and b. Present methods for prime factorization are also inefficient; many modern cryptography systems even rely on that inefficiency.

The binary GCD algorithm is an efficient alternative that substitutes division with faster operations by exploiting the binary representation used by computers. However, this alternative also scales like O(h²). It is generally faster than the Euclidean algorithm on real computers, even though it scales in the same way. Additional efficiency can be gleaned by examining only the leading digits of the two numbers a and b. The binary algorithm can be extended to other bases (k-ary algorithms), with up to fivefold increases in speed. Lehmer's GCD algorithm uses the same general principle as the binary algorithm to speed up GCD computations in arbitrary bases.

A recursive approach for very large integers (with more than 25,000 digits) leads to quasilinear integer GCD algorithms, such as those of Schönhage, and Stehlé and Zimmermann. These algorithms exploit the 2×2 matrix form of the Euclidean algorithm given above. These quasilinear methods generally scale as $147 = q_{2} 21 + r_{2}$

Generalizations
Although the Euclidean algorithm is used to find the greatest common divisor of two natural numbers (positive integers), it may be generalized to the real numbers, and to other mathematical objects, such as polynomials, quadratic integers and Hurwitz quaternions. In the latter cases, the Euclidean algorithm is used to demonstrate the crucial property of unique factorization, i.e., that such numbers can be factored uniquely into irreducible elements, the counterparts of prime numbers. Unique factorization is essential to many proofs of number theory.

Rational and real numbers
Euclid's algorithm can be applied to real numbers, as described by Euclid in Book 10 of his Elements. The goal of the algorithm is to identify a real number $g$ such that two given real numbers, $a$ and $b$, are integer multiples of it: $q_{2} = 7$ and $r_{2} = 0$, where $ℓ$ and $g$ are integers. This identification is equivalent to finding an integer relation among the real numbers $a$ and $b$; that is, it determines integers $m$ and $n$ such that $r_{k−2} = q_{k} r_{k−1} + r_{k}$. If such an equation is possible, a and b are called commensurable lengths, otherwise they are incommensurable lengths.

The real-number Euclidean algorithm differs from its integer counterpart in two respects. First, the remainders $r_{k} = r_{k−2} mod r_{k−1}.$ are real numbers, although the quotients $r_{k−2} = q_{k} r_{k−1} + r_{k}$ are integers as before. Second, the algorithm is not guaranteed to end in a finite number $a$ of steps. If it does, the fraction $|r_{k−1}| > r_{k} > 0$ is a rational number, i.e., the ratio of two integers

 * $$\frac{a}{b} = \frac{mg}{ng} = \frac{m}{n},$$

and can be written as a finite continued fraction $e_{k}$. If the algorithm does not stop, the fraction $r_{k−2} = (q_{k} + 1) r_{k−1} + e_{k}$ is an irrational number and can be described by an infinite continued fraction $r_{k−1} > 0$. Examples of infinite continued fractions are the golden ratio $r_{k−2} = (q_{k} − 1) r_{k−1} + e_{k}$ and the square root of two, $r_{k−1} < 0$. The algorithm is unlikely to stop, since almost all ratios $r_{k}$ of two real numbers are irrational.

An infinite continued fraction may be truncated at a step $e_{k}.$ to yield an approximation to $|e_{k}| < |r_{k}|$ that improves as $b$ is increased. The approximation is described by convergents $|r_{k}| ≤ |r_{k−1}| / 2$; the numerator and denominators are coprime and obey the recurrence relation

 * $$\begin{align}

m_k &= q_k m_{k-1} + m_{k-2} \\ n_k &= q_k n_{k-1} + n_{k-2}, \end{align}$$

where $q_{k}$ and $g = r_{N−1} = r_{N−3} − q_{N−1} r_{N−2}.$ are the initial values of the recursion. The convergent $r_{N−2} = r_{N−4} − q_{N−2} r_{N−3}$ is the best rational number approximation to $r_{N−3} = r_{N−5} − q_{N−3} r_{N−4}.$ with denominator $r_{2} = r_{0} − q_{2} r_{1}$:

 * $$ \left|\frac{a}{b} - \frac{m_k}{n_k}\right| < \frac{1}{n_k^2}.$$

Polynomials
Polynomials in a single variable x can be added, multiplied and factored into irreducible polynomials, which are the analogs of the prime numbers for integers. The greatest common divisor polynomial $r_{1} = b − q_{1} r_{0}$ of two polynomials $r_{0} = a − q_{0} b.$ and $mg = msa + mtb.$ is defined as the product of their shared irreducible polynomials, which can be identified using the Euclidean algorithm. The basic procedure is similar to that for integers. At each step $s$, a quotient polynomial $s_{k} = s_{k−2} − q_{k}s_{k−1}$ and a remainder polynomial $t_{k} = t_{k−2} − q_{k}t_{k−1}$ are identified to satisfy the recursive equation

 * $$r_{k-2}(x) = q_k(x)r_{k-1}(x) + r_k(x),$$

where $s_{−2} = 1, t_{−2} = 0$ and $s_{−1} = 0, t_{−1} = 1.$. Each quotient polynomial is chosen such that each remainder is either zero or has a degree that is smaller than the degree of its predecessor: $r_{j} = s_{j} a + t_{j} b$. Since the degree is a nonnegative integer, and since it decreases with every step, the Euclidean algorithm concludes in a finite number of steps. The last nonzero remainder is the greatest common divisor of the original two polynomials, $r_{k} = r_{k−2} − q_{k}r_{k−1}.$ and $r_{k} = (s_{k−2} a + t_{k−2} b) − q_{k}(s_{k−1} a + t_{k−1} b).$.

For example, consider the following two quartic polynomials, which each factor into two quadratic polynomials

 * $$\begin{align}

a(x) &= x^4 - 4x^3 + 4x^2 - 3x + 14 = (x^2 - 5x + 7)(x^2 + x + 2) \qquad \text{and}\\ b(x) &= x^4 + 8x^3 + 12x^2 + 17x + 6 = (x^2 + 7x + 3)(x^2 + x + 2). \end{align}$$

Dividing $r_{k} = s_{k} a + t_{k} b = (s_{k−2} − q_{k}s_{k−1}) a + (t_{k−2} − q_{k}t_{k−1}) b.$ by $g = (−1)^{N+1} ( m_{22} a − m_{12} b),$ yields a remainder $1 = su + tw$. In the next step, $v = suv + twv = sL + twv$ is divided by $L = p_{1}p_{2}…p_{m} = q_{1}q_{2}…q_{n}.$ yielding a remainder $ax + by = c$. Finally, dividing $ax ≡ c mod b.$ by $sa + tb = g$ yields a zero remainder, indicating that $ax_{1} + by_{1} = c = ax_{2} + by_{2}$ is the greatest common divisor polynomial of $a(x_{1} − x_{2}) = b(y_{2} − y_{1}).$ and $x = x_{1} − bu/g$, consistent with their factorization.

Many of the applications described above for integers carry over to polynomials. The Euclidean algorithm can be used to solve linear Diophantine equations and Chinese remainder problems for polynomials; continued fractions of polynomials can also be defined.

The polynomial Euclidean algorithm has other applications, such as Sturm chains, a method for counting the zeros of a polynomial that lie inside a given real interval. This in turn has applications in several areas, such as the Routh–Hurwitz stability criterion in control theory.

Finally, the coefficients of the polynomials need not be drawn from integers, real numbers or even the complex numbers. For example, the coefficients may be drawn from a general field, such as the finite fields $y = y_{1} + au/g$ described above. The corresponding conclusions about the Euclidean algorithm and its applications hold even for such polynomials.

Gaussian integers

The Gaussian integers are complex numbers of the form $ax + my = 1.$, where $t$ and $N$ are ordinary integers and $k$ is the square root of negative one. By defining an analog of the Euclidean algorithm, Gaussian integers can be shown to be uniquely factorizable, by the argument above. This unique factorization is helpful in many applications, such as deriving all Pythagorean triples or proving Fermat's theorem on sums of two squares. In general, the Euclidean algorithm is convenient in such applications, but not essential; for example, the theorems can often be proven by other arguments.

The Euclidean algorithm developed for two Gaussian integers $k$ and $u$ is nearly the same as that for ordinary integers, but differs in two respects. As before, we set $T(a, b) = T(m, n)$ and $T(a, b) = 1 + T(b, r_{0}) = 2 + T(r_{0}, r_{1}) = … = N + T(r_{N−2}, r_{N−1}) = N + 1$, and the task at each step $v$ is to identify a quotient $r_{k−2} = q_{k} r_{k−1} + r_{k}.$ and a remainder $r_{k} = r_{k−2} − q_{k} r_{k−1}.$ such that

 * $$r_k = r_{k-2} - q_k r_{k-1},$$

where every remainder is strictly smaller than its predecessor: $O(h(ℓ+1))$. The first difference is that the quotients and remainders are themselves Gaussian integers, and thus are complex numbers. The quotients $ln |u/(u − 1)|$ are generally found by rounding the real and complex parts of the exact ratio (such as the complex number $u = (q + 1)^{2}$) to the nearest integers. The second difference lies in the necessity of defining how one complex remainder can be "smaller" than another. To do this, a norm function $h_{0}, h_{1}, ..., h_{N−1}$ is defined, which converts every Gaussian integer $r_{0}, r_{1}, ..., r_{N−1}$ into an ordinary integer. After each step $i$ of the Euclidean algorithm, the norm of the remainder $O(h log h2 log log h).$ is smaller than the norm of the preceding remainder, $a = mg$. Since the norm is a nonnegative integer and decreases with every step, the Euclidean algorithm for Gaussian integers ends in a finite number of steps. The final nonzero remainder is $b = ng$, the Gaussian integer of largest norm that divides both $α$ and $β$; it is unique up to multiplication by a unit, $sa + tb = 0$ or $r_{k}$.

Many of the other applications of the Euclidean algorithm carry over to Gaussian integers. For example, it can be used to solve linear Diophantine equations and Chinese remainder problems for Gaussian integers; continued fractions of Gaussian integers can also be defined.

Euclidean domains
A set of elements under two binary operations, denoted as addition and multiplication, is called a Euclidean domain if it forms a commutative ring $k$ and, roughly speaking, if a generalized Euclidean algorithm can be performed on them. The two operations of such a ring need not be the addition and multiplication of ordinary arithmetic; rather, they can be more general, such as the operations of a mathematical group or monoid. Nevertheless, these general operations should respect many of the laws governing ordinary arithmetic, such as commutativity, associativity and distributivity.

The generalized Euclidean algorithm requires a Euclidean function, i.e., a mapping $k$ from $α$ into the set of nonnegative integers such that, for any two nonzero elements $β$ and $R$ in $f$, there exist $R$ and $a$ in $b$ such that $q_{k}$ and $a/b$. Examples of such mappings are the absolute value for integers, the degree for univariate polynomials, and the norm for Gaussian integers above. The basic principle is that each step of the algorithm reduces f inexorably; hence, if $R$ can be reduced only a finite number of times, the algorithm must stop in a finite number of steps. This principle relies on the well-ordering property of the non-negative integers, which asserts that every non-empty set of non-negative integers has a smallest member.

The fundamental theorem of arithmetic applies to any Euclidean domain: Any number from a Euclidean domain can be factored uniquely into irreducible elements. Any Euclidean domain is a unique factorization domain (UFD), although the converse is not true. The Euclidean domains and the UFD's are subclasses of the GCD domains, domains in which a greatest common divisor of two numbers always exists. In other words, a greatest common divisor may exist (for all pairs of elements in a domain), although it may not be possible to find it using a Euclidean algorithm. A Euclidean domain is always a principal ideal domain (PID), an integral domain in which every ideal is a principal ideal. Again, the converse is not true: not every PID is a Euclidean domain.

The unique factorization of Euclidean domains is useful in many applications. For example, the unique factorization of the Gaussian integers is convenient in deriving formulae for all Pythagorean triples and in proving Fermat's theorem on sums of two squares. Unique factorization was also a key element in an attempted proof of Fermat's Last Theorem published in 1847 by Gabriel Lamé, the same mathematician who analyzed the efficiency of Euclid's algorithm, based on a suggestion of Joseph Liouville. Lamé's approach required the unique factorization of numbers of the form $[q_{0}; q_{1}, q_{2}, ..., q_{N}]$, where $q$ and $r$ are integers, and $a/b$ is an $R$th root of 1, that is, $[q_{0}; q_{1}, q_{2}, …]$. Although this approach succeeds for some values of $f$ (such as $φ = [1; 1, 1, ...]$, the Eisenstein integers), in general such numbers do factor uniquely. This failure of unique factorization in some cyclotomic fields led Ernst Kummer to the concept of ideal numbers and, later, Richard Dedekind to ideals.

Unique factorization of quadratic integers

The quadratic integer rings are helpful to illustrate Euclidean domains. Quadratic integers are generalizations of the Gaussian integers in which the imaginary unit i is replaced by a number $x$. Thus, they have the form $√2 = [1; 2, 2, ...]$, where $y$ and $n$ are integers and $n$ has one of two forms, depending on a parameter $ω$. If $ω$ does not equal a multiple of four plus one, then

 * $$\omega = \sqrt D .$$

If, however, D does equal a multiple of four plus one, then

 * $$\omega = \frac{1 + \sqrt{D}}{2} .$$

If the function $u$ corresponds to a norm function, such as that used to order the Gaussian integers above, then the domain is known as norm-Euclidean. The norm-Euclidean rings of quadratic integers are exactly those where $v$ is one of the values −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, or 73. The cases $a/b$ and $k [q_{0}; q_{1}, q_{2}, ..., q_{k}]$ yield the Gaussian integers and Eisenstein integers, respectively.

If $ω$ is allowed to be any Euclidean function, then the list of possible values of $D$ for which the domain is Euclidean is not yet known. The first example of a Euclidean domain that was not norm-Euclidean (with $a/b$) was published in 1994. In 1973, Weinberger proved that a quadratic integer ring with $m_{k}/n_{k}$ is Euclidean if, and only if, it is a principal ideal domain, provided that the generalized Riemann hypothesis holds.

Noncommutative rings
The Euclidean algorithm may be applied to some noncommutative rings such as the set of Hurwitz quaternions. Let $D$ and $f$ represent two elements from such a ring. They have a common right divisor $D$ if $m_{−1} = n_{−2} = 1$ and $m_{−2} = n_{−1} = 0$ for some choice of $f$ and $D$ in the ring. Similarly, they have a common left divisor if $m_{k}/n_{k}$ and $a/b$ for some choice of $α$ and $β$ in the ring. Since multiplication is not commutative, there are two versions of the Euclidean algorithm, one for right divisors and one for left divisors. Choosing the right divisors, the first step in finding the $n_{k}$ by the Euclidean algorithm can be written

 * $$\rho_0 = \alpha - \psi_0\beta = (\xi - \psi_0\eta)\delta,$$

where $g(x)$ represents the quotient and $a(x)$ the remainder. Here the quotent and remainder are chosen so that (if nonzero) the remainder has $b(x)$ for a "Euclidean function" N defined analogously to the Euclidean functions of Euclidean domains in the non-commutative case. This equation shows that any common right divisor of $δ$ and $ξ$ is likewise a common divisor of the remainder $q_{k}(x)$. The analogous equation for the left divisors would be

 * $$\rho_0 = \alpha - \beta\psi_0 = \delta(\xi - \eta\psi_0).$$

With either choice, the process is repeated as above until the greatest common right or left divisor is identified. As in the Euclidean domain, the "size" of the remainder $r_{k}(x)$ (formally, its Euclidean function or "norm") must be strictly smaller than $η$, and there must be only a finite number of possible sizes for $r_{−2}(x) = a(x)$, so that the algorithm is guaranteed to terminate.

Many results for the GCD carry over to noncommutative numbers. For example, Bézout's identity states that the right $r_{−1}(x) = b(x)$ can be expressed as a linear combination of $ξ$ and $η$. In other words, there are numbers $α$ and $β$ such that

 * $$\Gamma_\text{right} = \sigma\alpha + \tau\beta.$$

The analogous identity for the left GCD is nearly the same:

 * $$\Gamma_\text{left} = \alpha\sigma + \beta\tau.$$

Bézout's identity can be used to solve Diophantine equations. For instance, one of the standard proofs of Lagrange's four-square theorem, that every positive integer can be represented as a sum of four squares, is based on quaternion GCDs in this way.

title: Euclidean algorithm


text:
European Centre for Medium-Range Weather Forecasts

The European Centre for Medium-Range Weather Forecasts (ECMWF) is an independent intergovernmental organisation supported by most of the nations of Europe. It is based at three sites: Shinfield Park, Reading, United Kingdom; Bologna, Italy; and Bonn, Germany. It operates one of the largest supercomputer complexes in Europe and the world's largest archive of numerical weather prediction data.

History
ECMWF was established in 1975, in recognition of the need to pool the scientific and technical resources of Europe's meteorological services and institutions for the production of weather forecasts for medium-range timescales (up to approximately two weeks) and of the economic and social benefits expected from it. The Centre employs about 350 staff, mostly appointed from across the member states and co-operating states. In 2017, the centre's member states accepted an offer from the Italian Government to move ECMWF's data centre to Bologna, Italy. The new site, a former tobacco factory, would be redesigned by the architecture firm gmp.

During 2020, the Centre arranged to move its Copernicus operations away from Reading and into European Union territory. Following bids from Toulouse, Italy, Austria, Germany, Spain and Ireland, eventually Bonn (Germany) was chosen. The move has been directly attributed to Brexit.

In August 2023, the centre partnered with Huawei on its cloud, AI-powered Pangu-Weather model for 10-day global weather prediction accuracies.

Objectives
ECMWF aims to provide accurate medium-range global weather forecasts out to 15 days and seasonal forecasts out to 12 months. Its products are provided to the national weather services of its member states and co-operating states as a complement to their national short-range and climatological activities, and those national states use ECMWF's products for their own national duties, in particular to give early warning of potentially damaging severe weather.

ECMWF's core mission is to:
 * Produce numerical weather forecasts and monitor planetary systems that influence weather
 * Carry out scientific and technical research to improve forecast skill
 * Maintain an archive of meteorological data

To deliver this core mission, the Centre provides:
 * Twice-daily global numerical weather forecasts
 * Air quality analysis
 * Atmospheric composition monitoring
 * Climate monitoring
 * Ocean circulation analysis
 * Hydrological prediction

The Centre develops and operates global atmospheric models and data assimilation systems for the dynamics, thermodynamics and composition of the Earth's atmosphere and for interacting parts of the Earth-system. It uses numerical weather prediction methods to prepare forecasts and their initial conditions, and it contributes to monitoring the relevant parts of the Earth system.

Forecasting
Numerical weather prediction (NWP) requires input of meteorological data, collected by satellites and earth observation systems such as automatic and crewed weather stations, aircraft (including commercial flights ), ships and weather balloons. Assimilation of this data is used to produce an initial state of a computer model of the atmosphere, from which an atmospheric model is used to forecast the weather. These forecasts are typically:
 * medium-range forecasts, predicting the weather up to 15 days ahead
 * monthly forecasts, predicting the weather on a weekly basis 30 days ahead
 * seasonal forecasts up to 12 months ahead.

Over the past three decades ECMWF's wide-ranging programme of research has played a major role in developing such assimilation and modelling systems. This improves the accuracy and reliability of weather forecasting by about a day per decade, so that a seven-day forecast now (2015) is as accurate as a three-day forecast was four decades ago (1975).

Monthly and seasonal forecasts
ECMWF's monthly and seasonal forecasts provide early predictions of events such as heat waves, cold spells and droughts, as well as their impacts on sectors such as agriculture, energy and health. Since ECMWF runs a wave model, there are also predictions of coastal waves and storm surges in European waters which can be used to provide warnings.

Early warning of severe weather events
Forecasts of severe weather events allow appropriate mitigating action to be taken and contingency plans to be put into place by the authorities and the public. The increased time gained by issuing accurate warnings can save lives, for instance by evacuating people from a storm surge area. Authorities and businesses can plan to maintain services around threats such as high winds, floods or snow.

In October 2012 the ECMWF model suggested seven days in advance that Hurricane Sandy was likely to make landfall on the East Coast of the United States. It also predicted the intensity and track of the November 2012 nor'easter, which impacted the east coast a week after Sandy.

ECMWF's Extreme Forecast Index (EFI) was developed as a tool to identify where the EPS (Ensemble Prediction System) forecast distribution differs substantially from that of the model climate. It contains information regarding variability of weather parameters, in location and time and can highlight an abnormality of a weather situation without having to define specific space- and time-dependent thresholds.

Satellite data
ECMWF, through its partnerships with EUMETSAT, ESA, the EU and others, exploits satellite data for operational numerical weather prediction and operational seasonal forecasting with coupled atmosphere–ocean–land models. The increasing amount of satellite data and the development of more sophisticated ways of extracting information from that data have made a major contribution to improving the accuracy and utility of NWP forecasts. ECMWF continuously endeavours to improve the use of satellite observations for NWP.

Reanalysis
ECMWF supports research on climate variability using an approach known as reanalysis. This involves feeding weather observations collected over decades into a NWP system to recreate past atmospheric, sea- and land-surface conditions over specific time periods to obtain a clearer picture of how the climate has changed. Reanalysis provides a four-dimensional picture of the atmosphere and effectively allows monitoring of the variability and change of global climate, thereby contributing also to the understanding and attribution of climate change.

To date, and with support from Europe's National Meteorological Services and the European Commission, ECMWF has conducted several major reanalyses of the global atmosphere: the first ECMWF re-analysis (ERA-15) project generated reanalyses from December 1978 to February 1994; the ERA-40 project generated reanalyses from September 1957 to August 2002. The ERA-Interim reanalysis covered the period from 1979 onwards. A reanalysis product (ERA5) with higher spatial resolution (31 km) was released by ECMWF in 2019 as part of the Copernicus Climate Change Service.

Operational forecast model
ECMWF's operational forecasts are produced from its "Integrated Forecast System" (sometimes informally known in the United States as the "European model") which is run every twelve hours and forecasts out to ten days.

It includes both a "deterministic forecast" mode and an ensemble. The deterministic forecast is a single model run that is relatively high in resolution as well as in computational expense. The ensemble is relatively low (about half that of the deterministic) in resolution (and in computational expense), so less accurate. But it is run 51 times in parallel, from slightly different initial conditions to give a spread of likelihood over the range of the forecast.

As of 2021, the ECMWF's weather model is generally considered to be the most accurate weather forecasting model.

Copernicus
The centre currently serves as the Entrusted Entity responsible for delivery of two of the Services of the EU's Copernicus Programme. The two services are the Copernicus Atmosphere Monitoring Service (CAMS) and the Copernicus Climate Change Service (C3S).

The Centre arranged to move its Copernicus operations away from Reading and into Bonn (Germany). The move has been directly attributed to Brexit.

Member and co-operating states
ECMWF comprises 23 European countries:
 * the eighteen founding states of 1975: Austria, Belgium, Denmark, Finland, France, Germany, Greece, Republic of Ireland, Italy, Luxembourg, Netherlands, Norway, Portugal, Spain, Sweden, Switzerland, Turkey, United Kingdom.
 * five states that joined since 2010: Iceland (April 2011), Slovenia (December 2012), Serbia (January 2015), Croatia (January 2016), Estonia (December 2020).

It also has co-operation agreements with other states: Bulgaria, Czech Republic, Georgia, Hungary, Israel, Latvia, Lithuania, North Macedonia, Montenegro, Morocco, Romania and Slovakia.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Talk:Evangelicalism

Criticism
Hello. I noticed that you have removed criticism of the financial abuses by religious leaders. However, it has been there for many years. This section being neutral and very well referenced, this action looks like to Vandalism. Also, as Criticism explains, “For topics about a particular point of view – such as philosophies (Idealism, Naturalism, Existentialism), political outlooks (Capitalism, Marxism), or religion (Islam, Christianity, Atheism) – it will usually be appropriate to have a "Criticism" section”. See also Christianity. Finally, it is an academic, encyclopedic and social responsibility, to denounce financial abuses by religious leaders in order to help people to identify them and specially to avoid new victims. This is what Jesus Christ has done many times in his ministry, including denouncing the love of money (Mammon) and the hypocrisy of religious leaders who devour the house of widows (Luke 20:47). Thanks for your help. My best wishes of peace and love (WikiLove).--Nathan B2 (talk) 18:29, 6 June 2023 (UTC)

 * Not sure of vandalism, but definitely not adhering to a neutral point of view. I appreciate the revert. —Confession0791 talk 03:22, 7 June 2023 (UTC)

I completely disagree with the massive "criticism" section in this article, which violates WP:UNDUE, WP:NPOV, and WP:CSECTION. I'm not aware of any other religion-related article with a criticism section, let alone one as large as this article. Also, much of the content relates to Pentecostals, when in reality, evangelicalism includes other denominations or traditions of Christianity, including Baptists, Methodists, Reformed, etc. The section should be trimmed, with some of its content potentially trimmed and moved into other sections. --1990'sguy (talk) 04:39, 12 August 2023 (UTC)

 * Hmmm...looking at the context, the removal was definitely not vandalism. And certainly the criticism section looks like a dumping ground for isolated incidents that are WP:COATRACK rather than comprehensive criticisms about evangelicalism as a movement. I agree that much of it, currently, deals with Pentecostals, which proves the point that the section needs to trimmed downed to actual criticisms of evangelicalism as a movement or moved to more appropriate articles like criticism of religion. Evangelicalism is a broad spectrum of denominations, and the little mismanagement or failings of any one denomination is not really reflective of evangelicalism as a whole - any more than the failings of any one government is a criticism of "government" as a whole. Better sources should be selected for this section. Ramos1990 (talk) 17:25, 12 August 2023 (UTC)

I agree that the large section is WP:COATRACK. These criticisms aren't against evangelicalism as a whole, but against individual churches and denominations that happen to arguably fall within the "evangelicalism" category. Let's remove every criticism that isn't actually about evangelicalism as a whole. NishantXavier (talk) 02:13, 16 August 2023 (UTC)

Evangelicals who don't go to church
There seems to be an increasing phenomenon of people self-identifying as "evangelical", but in actuality they only go to church a few times a year or not at all. This could represent as much as 40% of those who think of themselves as evangelicals. I think the article should eventually incorporate this phenomenon. There are sources such as https://www.christianitytoday.com/ct/2022/august-web-only/church-attendance-sbc-southern-evangelicals-now-lapsed.html and https://relevantmagazine.com/faith/church/new-data-suggests-over-40-percent-of-self-identified-evangelicals-attend-church-once-a-year-or-less/ --Westwind273 (talk) 06:58, 5 December 2023 (UTC)

It is questionable as to whether unchurched evangelicals are really evangelical Christians in the common sense of the expression. An evangelical belief in biblical inerrancy would seem to require church attendance, since that is the model that Paul set out in the New Testament. In this sense, evangelical may have become just a synonym for Republican. https://www.nytimes.com/2021/10/26/opinion/evangelical-republican.html --Westwind273 (talk) 22:25, 17 January 2024 (UTC)

Sentence fragments
"In 1882, in the American Baptist Churches USA. In the Assemblies of God of the United States, since 1927. In 1965, in the National Baptist Convention, USA. In 1969, in the Progressive National Baptist Convention. In 1975, in The Foursquare Church." Just putting this here so I remember it when I'm back on it computer. Dgndenver (talk) 05:58, 15 January 2024 (UTC)

Adjective-noun reversal
From the "Beliefs" section:

"a gift from God and a component of a Christian marriage harmonious"

Christian marriage harmonious or harmonious Christian marriage. Is this normally expressed in the in reverse (like spanish)? 70.89.80.221 (talk) 19:14, 16 May 2024 (UTC)

title: Talk:Evangelicalism


text:
European Broadcasting Union

The European Broadcasting Union (EBU; Union européenne de radio-télévision, UER) is an alliance of public service media organisations whose countries are within the European Broadcasting Area or who are members of the Council of Europe. , it is made up of 123 member organisations from 56 countries, and 31 associate members from a further 20 countries. It was established in 1950, and has its administrative headquarters in Geneva.

The EBU owns and operates the Eurovision and Euroradio telecommunications networks on which major television and radio broadcasts are distributed live to its members. It also operates the daily Eurovision news exchange in which members share breaking news footage. In 2017, the EBU launched the Eurovision Social Newswire, an eyewitness and video verification service. Led by Head of Social Newsgathering, Derek Bowler, the service provides members of the EBU with verified and cleared-for-use newsworthy eyewitness media emerging on social media.

The EBU, in co-operation with its members, produces programmes and organises events in which its members can participate, such as the Eurovision Song Contest, its best known production, or the Eurovision Debates between candidates for president of the European Commission for the 2014, 2019 and 2024 parliamentary elections. The Director-General is Noel Curran since 2017.

General description
EBU members are public service media (PSM) broadcasters established by law but are non-partisan, independent and run for the benefit of society as a whole.

EBU members come from as far north as Iceland and as far south as Egypt, from Ireland in the west and Azerbaijan in the east, and almost every nation from geographical Europe in between. Associate members from the United States include ABC, CBS, NBC, CPB, NPR, APM and the only individual station, Chicago-based classical music radio WFMT.

Membership is for media organisations whose countries are within the European Broadcasting Area, as defined by the International Telecommunication Union, or who are members of the Council of Europe.

Members benefit from:
 * Access to content ranging from exclusive sports rights to exchanges for news, music and children's programs.
 * Representatives in Brussels, and in other international arenas, lobbying for PSM and ensuring the optimal legal and technical framework for broadcasters.
 * Opportunities for sharing, learning and collaborating through conferences, working groups, training, and dedicated advice and guidance.
 * A centre for learning and sharing new technology and innovation with a team of experts providing strategic advice and guidance.

The EBU's highest-profile production is the Eurovision Song Contest. The EBU also organises the Eurovision Dance Contest, the Junior Eurovision Song Contest, the Eurovision Young Dancers competition, and other competitions which are modeled along similar lines.

Radio collaborations include Euroclassic Notturno—an overnight classical music stream, produced by BBC Radio 3 and broadcast in the United Kingdom as Through the Night—and special theme days, such as the annual Christmas music relays from around Europe. The EBU is a member of the International Music Council.

Most EBU broadcasters have group deals to carry major sporting events including the FIFA World Cup and the inaugural European Championships. Another annually recurring event which is broadcast across Europe through the EBU is the Vienna New Year's Concert.

Eurovision Media Services is the business arm of the EBU and provides media services for many media organisations and sports federations around the world.

Ident
The theme music played before and after every EBU broadcast is Marc-Antoine Charpentier's Prelude to Te Deum. It is played before and after the Eurovision Song Contest and other important events.

History
The EBU was a successor to the International Broadcasting Union (IBU) that was founded in 1925 and had its administrative headquarters in Geneva and technical office in Brussels. It fostered programming exchanges between members and mediated technical disputes between members that were mostly concerned with frequency and interference issues. It was in effect taken over by Nazi Germany during the Second World War, and thereafter the Allies viewed it as a compromised organisation that they could not trust.

In the spring of 1946, representatives of the Soviet radio committee proposed forming a new organisation; however, at the same time preparations were being made for an inter-governmental "European Broadcasting Conference" in Copenhagen in 1948 to draw up a new plan for frequency use in the European Broadcasting Area. It was considered necessary to have an organisation that could implement the "Copenhagen Wavelength Plan" but there was disagreement among broadcasters and particularly a fear expressed by the BBC that a new association might be dominated by the USSR and its proposal to give each of its constituent states one vote. France proposed that it would have four votes with the inclusion of its North African colonies. The United Kingdom felt it would have little influence with just one vote.

On 27 June 1946, the alternative International Broadcasting Organisation (IBO) was founded with 26 members and without British participation. The following day the IBU met in General Assembly and an attempt was made to dissolve it but failed; though 18 of its 28 members left to join the IBO. For a period of time in the late 1940s both the IBU and IBO vied for the role of organising frequencies but Britain decided to be in involved in neither. The BBC attempted but failed to find suitable working arrangements with them. However, for practical purposes, the IBO rented the IBU technical centre in Brussels and employed its staff. The BBC then proposed a new solution based on the IBO changing its constitution so there will be only one member per International Telecommunication Union (ITU) country, thus ensuring a Western majority over the USSR and its satellite states. In August 1949 a meeting took place in Stresa, Italy but it resulted in disagreement between delegates on how to resolve the problems. One proposal was for the European Broadcasting Area to be replaced by one that would exclude Eastern Europe, the Levant and North Africa.

After Stresa, a consensus emerged among the Western Europeans to form a new organisation and the BBC proposed it be based in London. Meetings in Paris on 31 October and 1 November 1949 sealed the fate of the IBU and IBO, but it was decided not to allow West Germany to be a founder of the new organisation. On 13 February 1950 the European Broadcasting Union had its first meeting with 23 members from the ITU defined European Broadcasting Area at the Imperial Hotel in Torquay, England, United Kingdom. The first president was Ian Jacob of the BBC who remained at the helm for 10 years while its operation was largely dominated by the BBC due to its financial, technical and staff input. The most important difference between the EBU and its predecessors was that EBU membership was for broadcasters and not governments. Early delegates said EBU meetings were cordial and professional and very different from the abrupt tone of its predecessors. West Germany was admitted in 1951 and a working relationship forged with the USSR's Organisation for International Radio and TV (OIRT) which existed in parallel with the EBU until its merger on 1 January 1993.

In 1967, the first concert in the International Concert Season of the European Broadcasting Union was broadcast from the Queen Elizabeth Hall in London.

Technical activities
The objective of the EBU's technical activities is simply to assist EBU Members (see below) in this period of unprecedented technological changes. This includes the provision of technical information to Members via conferences and workshops, as well as in written form (such as the EBU Technical Review, and the EBU tech-i magazine).

The EBU also encourages active collaboration between its Members on the basis that they can freely share their knowledge and experience, thus achieving considerably more than individual Members could achieve by themselves. Much of this collaboration is achieved through Project Groups which study specific technical issues of common interest: for example, EBU Members have long been preparing for the revision of the 1961 Stockholm Plan.

The EBU places great emphasis on the use of open standards. Widespread use of open standards (such as MPEG-2, DAB, DVB, etc.) ensures interoperability between products from different vendors, as well as facilitating the exchange of programme material between EBU Members and promoting "horizontal markets" for the benefit of all consumers.

EBU Members and the EBU Technical Department have long played an important role in the development of many systems used in radio and television broadcasting, such as:
 * The AES/EBU digital audio interface, formally known as AES3;
 * Serial and parallel interfaces for digital video (ITU-R Recommendations 601 and 656);
 * RDS – the radio data system used on FM broadcasting.
 * The EBU Loudness Recommendation R 128 and 'EBU Mode' meters (EBU Tech 3341)

The EBU has also actively encouraged the development and implementation of:

 * Digital radio (DAB) through Eureka Project 147 and the WorldDAB Forum.
 * DVB (Digital Video Broadcasting) through the DVB Project and DigiTAG.
 * Digital radio in the bands currently used for AM broadcasting through Digital Radio Mondiale (DRM).
 * Standardisation of PVR systems through the TV-Anytime Forum.
 * Development of other content distribution networks on the internet through P2PTV; EBU Project Group D/P2P, from November 2007 to April 2008, with a trial of selected member channels, thanks to Octoshape's distribution platform. The EBU is also part of the European P2P-Next project.

Greek state broadcaster (2013)
On 11 June 2013, the Greek government shut down the state broadcaster Hellenic Broadcasting Corporation (ERT) on short notice, citing government spending concerns related to the European debt crisis. In response, the EBU set up a makeshift studio the same day near the former ERT offices in Athens in order to continue providing EBU members with the news-gathering and broadcast relay services which had formerly been provided by ERT. The EBU put out a statement expressing its "profound dismay" at the shutdown, urging the Greek Prime Minister "to use all his powers to immediately reverse this decision" and offered the "advice, assistance and expertise necessary for ERT to be preserved". Starting on 4 May 2014, the new state broadcaster New Hellenic Radio, Internet and Television (NERIT) began nationwide transmissions, taking over ERT's vacant active membership slot in the EBU. On 11 June 2015, two years after ERT's closure, NERIT was renamed as Hellenic Broadcasting Corporation (ERT), which reopened with a comprehensive program in all radio stations (with nineteen regional, two world-range and five pan-Hellenic range radio stations) and three TV channels ERT1, ERT2 and ERT3.

Belarusian state broadcaster (2021)
The Belarusian Television and Radio Company (BTRC) has been accused of repressing its own employees, having fired more than 100 people since a wave of anti-Lukashenko protests in 2020 following alleged election fraud. Many of them have also been jailed. Many voices have been raised against the participation of Belarus and the BTRC in the otherwise unpolitical Eurovision Song Contest in 2021, the argument being that the EBU would make a political statement if it did endorse Belarus by essentially and silently saying that democracy is unimportant and so are basic human rights such as freedom of speech.

On 28 May 2021, the EBU suspended the BTRC's membership as they had been "particularly alarmed by the broadcast of interviews apparently obtained under duress". BTRC was given two weeks to respond before the suspension came into effect, but did not do so publicly. The suspension of the broadcaster was made effective on 1 July 2021. Although initial reports mentioned that it would expire after three years, in April 2024 the EBU confirmed that the suspension had been made indefinite.

Russian state broadcasters (2022)
The three Russian members of the EBU, Channel One Russia, VGTRK, and Radio Dom Ostankino are all controlled by the Russian government. On 21 February 2022, the Russian government recognized the independence of the Donetsk and Luhansk People's Republics, disputed territories that are internationally recognized as part of Ukraine. Ukraine's public broadcaster Suspilne called on the EBU to terminate the membership of Channel One Russia and VGTRK, and to consider preventing Russia from participating in the Eurovision Song Contest 2022, citing the Russian government's use of both outlets to spread disinformation surrounding the Russo-Ukrainian war. Following the Russian invasion of Ukraine, several other public broadcasters joined UA:PBC in calling for Russia's exclusion from the 2022 Contest; Finland's Yle and Estonia's ERR stated that they would not send a representative if Russia was allowed to participate. After initially stating that both Russia and Ukraine would be allowed to compete, the EBU announced on 25 February 2022 that it would ban Russia from participating in the Contest.

The three Russian broadcasters announced, via a statement released by Russian state media, that they would withdraw from the EBU on 26 February, citing increased politicization of the organization. The EBU released a statement saying that it was aware of the reports, but that it had not received any formal confirmation. On 1 March, a further statement from the EBU announced that it had suspended its Russian members from its governance structures. On 26 May, the EBU made effective the suspension of its Russian members indefinitely.

In 2023, an extensive investigation by the EBU Investigative Journalism Network uncovered evidence of a Kremlin-sponsored initiative to take Ukrainian children from the war-torn country to Russia, a war crime under international law.

Members

, the list of EBU members comprises the following 77 broadcasting companies from 56 countries.

Associate members
Any group or organisation from an International Telecommunication Union (ITU) member country, which provides a radio or television service outside of the European Broadcasting Area, is permitted to submit applications to the EBU for Associate Membership.

It is also noted by the EBU that any country that is granted Associate Member status does not gain access into Eurovision events with the notable exceptions of Australia, who have participated in the Eurovision Song Contest and the Junior Eurovision Song Contest since 2015, Canada in Eurovision Young Dancers between 1987 and 1989 and Kazakhstan, who have participated in Junior Eurovision since 2018, all of which were individually invited.

The list of Associate Members of EBU comprised the following 31 broadcasting companies from 20 countries.

Past associate members
The list of past associate members of EBU comprises the following 94 broadcasting companies from 55 countries and 1 autonomous territory.

Approved participant members
Any groups or organisations from a country with International Telecommunication Union (ITU) membership, which does not qualify for either the EBU's Active or Associate memberships, but still provide a broadcasting activity for the EBU, are granted a unique Approved Participants membership, which lasts approximately five years. An application for this status may be submitted to the EBU at any given time, providing an annual fee is paid.

The following seven EBU broadcast members had status as Approved Participants in June 2024.

The following members previously had status as Approved Participants.

Organised events
The EBU in co-operation with the respective host broadcaster organises competitions and events in which its members can participate if they wish to do so. These include:

Eurovision Song Contest

The Eurovision Song Contest is an annual international song competition between EBU members, that was first held in Lugano, Switzerland, on 24 May 1956. Seven countries participated – each submitting two songs, for a total of 14. This was the only contest in which more than one song per country was performed: since 1957, all contests have allowed one entry per country. The was won by the host nation, Switzerland. The most recent host city was Malmö, Sweden, where Switzerland won.

Let the Peoples Sing
Let the Peoples Sing is a biennial choir competition, the participants of which are chosen from radio recordings entered by EBU radio members. The final, encompassing three categories and around ten choirs, is offered as a live broadcast to all EBU members. The overall winner is awarded the Silver Rose Bowl.

Jeux sans frontières
Jeux sans frontières (Games without frontiers, or Games Without Borders) was a Europe-wide television game show. In its original conception, it was broadcast from 1965 to 1999 under the auspices of the EBU. The original series' run ended in 1982, but was revived in 1988 with a different composition of nations and was hosted by smaller broadcasters.

Eurovision Young Musicians
Eurovision Young Musicians is a competition for European musicians that are between the ages of 12 and 21 years old. It is organised by the EBU and is a member of EMCY. The first competition was held in Manchester, United Kingdom on 11 May 1982.

The televised competition is held every two years, with some countries holding national heats. Since its inaugural edition in 1982, it has become one of the most important music competitions on an international level.

Eurovision Young Dancers
Eurovision Young Dancers was a biennial dance showcase broadcast on television throughout Europe. The first competition was held in Reggio Emilia, Italy on 16 June 1985.

It uses a format similar to the Eurovision Song Contest. Every participating country has the opportunity to send a dance act to compete for the title of "Eurovision Young Dancer". The competition is for solo dancers, and all contestants must be between the ages of 16 and 21, and not professionally engaged.

Euroclassic Notturno
Euroclassic Notturno is a six-hour sequence of classical music recordings, assembled by BBC Radio from material supplied by EBU members and streamed back to those broadcasters by satellite for use in their overnight classical-music schedules. The recordings used are taken not from commercial CDs, but from earlier (usually live) radio broadcasts.

Junior Eurovision Song Contest
The Junior Eurovision Song Contest is an annual international song competition that was first held in Copenhagen, Denmark, on 15 November 2003. Sixteen countries participated in the inaugural edition, with each submitting one song, for a total of 16 entries. The inaugural contest was won by Croatia. The winner of the most recent contest, which took place in Nice, France, is France.

Eurovision Dance Contest
The Eurovision Dance Contest (not to be confused with the Eurovision Young Dancers Competition) was an international dancing competition that was held for the first time in London, United Kingdom, on 1 September 2007. The competition was repeated in 2008 when it was held in Glasgow, United Kingdom, but has not been held since.

Eurovision Magic Circus Show
The Eurovision Magic Circus Show was an entertainment show organised by the EBU, which took place in 2010, 2011 and 2012 in Geneva. Children aged between 7–14 representing eight countries within the EBU membership area performed a variety of circus acts at the Geneva Christmas Circus (Cirque de Noël Genève). The main show was also accompanied by the Magic Circus Show Orchestra.

Eurovision Choir
The inaugural Eurovision Choir, featuring non-professional choirs selected by EBU members, took place on 22 July 2017 in Riga, hosted by the Latvian broadcaster Latvijas Televīzija (LTV). Nine countries took part in the first edition. Carmen Manet from Slovenia was the first winner.

European Sports Championships
The European Sports Championships is a multi-sport event involving some of the leading sports in Europe. The European Governing Bodies for athletics, aquatics, cycling, rowing, golf, gymnastics and triathlon, coordinated their individual championships as part of the first edition in the summer of 2018, hosted by the cities of Berlin (already chosen as the host for the 2018 European Athletics Championships) and Glasgow (already chosen as the host for the 2018 European Aquatics Championships, and which concurrently also hosted the events of the other sports).

title: European Broadcasting Union