title: Euclidean algorithm

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


title: Euclidean algorithm

text: The greatest common divisor of two numbers "a" and "b" is the product of the prime factors shared by the two numbers, where each prime factor can be repeated as many times as divides both "a" and "b". For example, since 1386 can be factored into 2 × 3 × 3 × 7 × 11, and 3213 can be factored into 3 × 3 × 3 × 7 × 17, the GCD of 1386 and 3213 equals 63 = 3 × 3 × 7, the product of their shared prime factors (with 3 repeated since 3 × 3 divides both). If two numbers have no common prime factors, their GCD is 1 (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.


title: Euclidean algorithm

text: Another definition of the GCD is helpful in advanced mathematics, particularly ring theory. The greatest common divisor "g"  of two nonzero numbers "a" and "b" is also their smallest positive integral linear combination, that is, the smallest positive number of the form "ua" + "vb" where "u" and "v" are integers. The set of all integral linear combinations of "a" and "b" is actually the same as the set of all multiples of "g" ("mg", where "m" is an integer). In modern mathematical language, the ideal generated by "a" and "b" is the ideal generated by "g" 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 "a" and "b" also divides the GCD (it divides both terms of "ua" + "vb"). The equivalence of this GCD definition with the other definitions is described below.


title: Euclidean algorithm

text: 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,


title: Euclidean algorithm

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


title: Euclidean algorithm

text: The Euclidean algorithm proceeds in a series of steps, with the output of each step used as the input for the next. Track the steps using an integer counter "k", so the initial step corresponds to "k" = 0, the next step to "k" = 1, and so on.


title: Euclidean algorithm

text: Each step begins with two nonnegative remainders "r" and "r", with "r" > "r". The "k"th step performs division-with-remainder to find the quotient "q" and remainder "r" so that:


title: Euclidean algorithm

text: That is, multiples of the smaller number "r" are subtracted from the larger number "r" until the remainder "r" is smaller than "r". Then the algorithm proceeds to the ("k"+1)th step starting with "r" and "r""."


title: Euclidean algorithm

text: In the initial step "k" = 0, the remainders are set to "r" = "a" and "r" = "b", the numbers for which the GCD is sought. In the next step "k" = 1, the remainders are "r = b" and the remainder "r" of the initial step, and so on. The algorithm proceeds in a sequence of equations


title: Euclidean algorithm

text: The algorithm need not be modified if "a" < "b": in that case, the initial quotient is "q" = 0, the first remainder is "r" = "a", and henceforth "r" > "r" for all "k" ≥ 1.


title: Euclidean algorithm

text: Since the remainders are non-negative integers that decrease with every step, the sequence formula_3 cannot be infinite, so the algorithm must eventually fail to produce the next step; but the division algorithm can always proceed to the ("N"+1)th step provided "r" > 0. Thus the algorithm must eventually produce a zero remainder "r" = 0. The final nonzero remainder is the greatest common divisor of "a" and "b":formula_4


title: Euclidean algorithm

text: The validity of the Euclidean algorithm can be proven by a two-step argument. In the first step, the final nonzero remainder "r" 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 "r"; therefore, "g" must be less than or equal to "r". These two opposite inequalities imply "r" = "g".


title: Euclidean algorithm

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


title: Euclidean algorithm

text: 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 "r". 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 "r", since "r" = "a" − "q""b" = "mc" − "q""nc" = ("m" − "q""n")"c". An analogous argument shows that "c" also divides the subsequent remainders "r", "r", etc. Therefore, the greatest common divisor "g" must divide "r", which implies that "g" ≤ "r". Since the first part of the argument showed the reverse ("r" ≤ "g"), it follows that "g" = "r". Thus, "g" is the greatest common divisor of all the succeeding pairs:


title: Euclidean algorithm

text: 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 ("q" = 2), leaving a remainder of 147:


title: Euclidean algorithm

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


title: Euclidean algorithm

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


title: Euclidean algorithm

text: 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 . In tabular form, the steps are:


title: Euclidean algorithm

text: 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"-by-"b" rectangle with square tiles exactly, where "a" is the larger of the two numbers. We first attempt to tile the rectangle using "b"-by-"b" square tiles; however, this leaves an "r"-by-"b" residual rectangle untiled, where "r" < "b". We then attempt to tile the residual rectangle with "r"-by-"r" square tiles. This leaves a second residual rectangle "r"-by-"r", which we attempt to tile using "r"-by-"r" 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-by-21 (shown in red), and 21 is the GCD of 1071 and 462, the dimensions of the original rectangle (shown in green).


title: Euclidean algorithm

text: At every step "k", the Euclidean algorithm computes a quotient "q" and remainder "r" from two numbers "r" and "r"


title: Euclidean algorithm

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


title: Euclidean algorithm

text: In Euclid's original version of the algorithm, the quotient and remainder are found by repeated subtraction; that is, "r" is subtracted from "r" repeatedly until the remainder "r" is smaller than "r". After that "r" and "r" 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


title: Euclidean algorithm

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


title: Euclidean algorithm

text: At the beginning of the "k"th iteration, the variable "b" holds the latest remainder "r", whereas the variable "a" holds its predecessor, "r". The step "b" := "a" mod "b" is equivalent to the above recursion formula "r" ≡ "r" mod "r". The temporary variable "t" holds the value of "r" while the next remainder "r" is being calculated. At the end of the loop iteration, the variable "b" holds the remainder "r", whereas the variable "a" holds its predecessor, "r".


title: Euclidean algorithm

text: In the subtraction-based version, which was Euclid's original version, the remainder calculation (codice_1) 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":


title: Euclidean algorithm

text: The variables "a" and "b" alternate holding the previous remainders "r" and "r". Assume that "a" is larger than "b" at the beginning of an iteration; then "a" equals "r", since "r" > "r". 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 "r". Then "b" is reduced by multiples of "a" until it is again smaller than "a", giving the next remainder "r", and so on.


title: Euclidean algorithm

text: The recursive version is based on the equality of the GCDs of successive remainders and the stopping condition gcd("r", 0) = "r".


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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


title: Euclidean algorithm

text: 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 is chosen in order that formula_5 where formula_6 is the golden ratio.


title: Euclidean algorithm

text: 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".


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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".


title: Euclidean algorithm

text: The integers "s" and "t" can be calculated from the quotients "q", "q", 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 "q" and the two preceding remainders, "r" and "r":


title: Euclidean algorithm

text: Substituting these formulae for "r" and "r" into the first equation yields "g" as a linear sum of the remainders "r" and "r". The process of substituting remainders by formulae involving their predecessors can be continued until the original numbers "a" and "b" are reached:


title: Euclidean algorithm

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


title: Euclidean algorithm

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


title: Euclidean algorithm

text: 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",


title: Euclidean algorithm

text: 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).


title: Euclidean algorithm

text: 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").


title: Euclidean algorithm

text: 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


title: Euclidean algorithm

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


title: Euclidean algorithm

text: 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


title: Euclidean algorithm

text: Since the recursion formula has been assumed to be correct for "r" and "r", they may be expressed in terms of the corresponding "s" and "t" variables


title: Euclidean algorithm

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


title: Euclidean algorithm

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


title: Euclidean algorithm

text: 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), 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


title: Euclidean algorithm

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


title: Euclidean algorithm

text: 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


title: Euclidean algorithm

text: 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 "a", "a", ..., "a", then "w" is also coprime to their product, "a" × "a" × ... × "a".


title: Euclidean algorithm

text: 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


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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


title: Euclidean algorithm

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


title: Euclidean algorithm

text: 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


title: Euclidean algorithm

text: where "s" and "t" can be found by the extended Euclidean algorithm. This provides one solution to the Diophantine equation, "x" = "s" ("c"/"g") and "y" = "t" ("c"/"g").


title: Euclidean algorithm

text: In general, a linear Diophantine equation has no solutions, or an infinite number of solutions. To find the latter, consider two solutions, ("x", "y") and ("x", "y"), where


title: Euclidean algorithm

text: 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


title: Euclidean algorithm

text: By allowing "u" to vary over all possible integers, an infinite family of solutions can be generated from a single solution ("x", "y"). 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).


title: Euclidean algorithm

text: 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 "p". Finite fields are often called Galois fields, and are abbreviated as GF("p") or GF("p").


title: Euclidean algorithm

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


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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 "x" modulo a set of "N" coprime numbers "m":


title: Euclidean algorithm

text: The goal is to determine "x" from its "N" remainders "x". 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 "m", and define "M" as


title: Euclidean algorithm

text: Thus, each "M" is the product of all the moduli "except" "m". The solution depends on finding "N" new numbers "h" such that


title: Euclidean algorithm

text: Since these numbers "h" are the multiplicative inverses of the "M", they may be found using Euclid's algorithm as described in the previous subsection.


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

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


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

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


title: Euclidean algorithm

text: 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


title: Euclidean algorithm

text: The final ratio of remainders "r"/"r" can always be replaced using the next equation in the series, up to the final equation. The result is a continued fraction


title: Euclidean algorithm

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


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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 log "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".


title: Euclidean algorithm

text: 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"("h"). 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"("h"). 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.


title: Euclidean algorithm

text: 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


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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 "F" and "F", respectively. More precisely, if the Euclidean algorithm requires "N" steps for the pair "a" > "b", then one has "a" ≥ "F" and "b" ≥ "F". 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 "F" and "F", 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" = "q""b" + "r", and the Euclidean algorithm requires "M" − 1 steps for the pair "b" > "r". By induction hypothesis, one has "b" ≥ "F" and "r" ≥ "F". Therefore, "a" = "q""b" + "r" ≥ "b" + "r" ≥ "F" + "F" = "F",


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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 "F" which in turn is greater than or equal to "φ", where "φ" is the golden ratio. Since "b" ≥ "φ", then "N" − 1 ≤ log"b". Since log"φ" > 1/5, ("N" − 1)/5 < log"φ" log"b" = log"b". Thus, "N" ≤ 5 log"b". Thus, the Euclidean algorithm always needs less than "O"("h") divisions, where "h" is the number of digits in the smaller number "b".


title: Euclidean algorithm

text: 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


title: Euclidean algorithm

text: with the residual error being of order "a", where "ε" is infinitesimal. The constant "C" in this formula is called Porter's constant and equals


title: Euclidean algorithm

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


title: Euclidean algorithm

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


title: Euclidean algorithm

text: 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"


title: Euclidean algorithm

text: In each step "k" of the Euclidean algorithm, the quotient "q" and remainder "r" are computed for a given pair of integers "r" and "r"


title: Euclidean algorithm

text: The computational expense per step is associated chiefly with finding "q", since the remainder "r" can be calculated quickly from "r", "r", and "q"


title: Euclidean algorithm

text: The computational expense of dividing "h"-bit numbers scales as "O"("h"("ℓ"+1)), where "ℓ" is the length of the quotient.


title: Euclidean algorithm

text: 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 ln|"u"/("u" − 1)| where "u" = ("q" + 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.


title: Euclidean algorithm

text: Combining the estimated number of steps with the estimated computational expense per step shows that the Euclid's algorithm grows quadratically ("h") with the average number of digits "h" in the initial two numbers "a" and "b". Let "h", "h", ..., "h" represent the number of digits in the successive remainders "r", "r", ..., "r". Since the number of steps "N" grows linearly with "h", the running time is bounded by


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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 such that two given real numbers, and , are integer multiples of it: and , where and are integers. This identification is equivalent to finding an integer relation among the real numbers and ; that is, it determines integers and such that . If such an equation is possible, "a" and "b" are called commensurable lengths, otherwise they are incommensurable lengths.


title: Euclidean algorithm

text: The real-number Euclidean algorithm differs from its integer counterpart in two respects. First, the remainders are real numbers, although the quotients are integers as before. Second, the algorithm is not guaranteed to end in a finite number of steps. If it does, the fraction is a rational number, i.e., the ratio of two integers


title: Euclidean algorithm

text: and can be written as a finite continued fraction . If the algorithm does not stop, the fraction is an irrational number and can be described by an infinite continued fraction . Examples of infinite continued fractions are the golden ratio and the square root of two, . The algorithm is unlikely to stop, since almost all ratios of two real numbers are irrational.


title: Euclidean algorithm

text: An infinite continued fraction may be truncated at a step to yield an approximation to that improves as is increased. The approximation is described by convergents ; the numerator and denominators are coprime and obey the recurrence relation


title: Euclidean algorithm

text: where and are the initial values of the recursion. The convergent is the best rational number approximation to with denominator :


title: Euclidean algorithm

text: 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 of two polynomials and 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 , a quotient polynomial and a remainder polynomial are identified to satisfy the recursive equation


title: Euclidean algorithm

text: where and . 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: . 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, and .


title: Euclidean algorithm

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


title: Euclidean algorithm

text: Dividing by yields a remainder . In the next step, is divided by yielding a remainder . Finally, dividing by yields a zero remainder, indicating that is the greatest common divisor polynomial of and , consistent with their factorization.


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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 described above. The corresponding conclusions about the Euclidean algorithm and its applications hold even for such polynomials.


title: Euclidean algorithm

text: The Gaussian integers are complex numbers of the form , where and are ordinary integers and 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.


title: Euclidean algorithm

text: The Euclidean algorithm developed for two Gaussian integers and is nearly the same as that for ordinary integers, but differs in two respects. As before, we set and , and the task at each step is to identify a quotient and a remainder such that


title: Euclidean algorithm

text: where every remainder is strictly smaller than its predecessor: . The first difference is that the quotients and remainders are themselves Gaussian integers, and thus are complex numbers. The quotients are generally found by rounding the real and complex parts of the exact ratio (such as the complex number ) 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 is defined, which converts every Gaussian integer into an ordinary integer. After each step of the Euclidean algorithm, the norm of the remainder is smaller than the norm of the preceding remainder, . 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 , the Gaussian integer of largest norm that divides both and ; it is unique up to multiplication by a unit, or .


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: A set of elements under two binary operations, denoted as addition and multiplication, is called a Euclidean domain if it forms a commutative ring 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.


title: Euclidean algorithm

text: The generalized Euclidean algorithm requires a "Euclidean function", i.e., a mapping from into the set of nonnegative integers such that, for any two nonzero elements and in , there exist and in such that and . 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 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.


title: Euclidean algorithm

text: 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.


title: Euclidean algorithm

text: 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 , where and are integers, and is an th root of 1, that is, . Although this approach succeeds for some values of (such as , 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.


title: Euclidean algorithm

text: 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 . Thus, they have the form , where and are integers and has one of two forms, depending on a parameter . If does not equal a multiple of four plus one, then


title: Euclidean algorithm

text: If the function 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 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 and yield the Gaussian integers and Eisenstein integers, respectively.


title: Euclidean algorithm

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


title: Euclidean algorithm

text: The Euclidean algorithm may be applied to some noncommutative rings such as the set of Hurwitz quaternions. Let and represent two elements from such a ring. They have a common right divisor if and for some choice of and in the ring. Similarly, they have a common left divisor if and 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 by the Euclidean algorithm can be written


title: Euclidean algorithm

text: where represents the quotient and the remainder. This equation shows that any common right divisor of and is likewise a common divisor of the remainder . The analogous equation for the left divisors would be


title: Euclidean algorithm

text: 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 (formally, its norm) must be strictly smaller than , and there must be only a finite number of possible sizes for , so that the algorithm is guaranteed to terminate.


title: Euclidean algorithm

text: Most of the results for the GCD carry over to noncommutative numbers. For example, Bézout's identity states that the right can be expressed as a linear combination of and . In other words, there are numbers and such that


title: Euclidean algorithm

text: 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: Cambodian Civil War

text: The Cambodian Civil War (, UNGEGN: ) was a civil war in Cambodia fought between the forces of the Communist Party of Kampuchea (known as the Khmer Rouge, supported by North Vietnam and the Viet Cong) against the government forces of the Kingdom of Cambodia and, after October 1970, the Khmer Republic, which had succeeded the kingdom (both supported by the United States and South Vietnam).


title: Cambodian Civil War

text: The struggle was complicated by the influence and actions of the allies of the two warring sides. North Vietnam's People's Army of Vietnam (PAVN) involvement was designed to protect its Base Areas and sanctuaries in eastern Cambodia, without which it would have been harder to pursue its military effort in South Vietnam. Their presence was at first tolerated by Prince Sihanouk, the Cambodian head of state, but domestic resistance combined with China and North Vietnam continuing to provide aid to the anti-government Khmer Rouge alarmed Sihanouk and caused him to go to Moscow to request the Soviets rein in the behavior of North Vietnam. The deposition of Sihanouk by the Cambodian National Assembly in March 1970, following wide scale protests in the capital against the presence of PAVN troops in the country, put a pro-American government in power (later declared the Khmer Republic) which demanded that the PAVN leave Cambodia. The PAVN refused and, at the request of the Khmer Rouge, promptly invaded Cambodia in force.


title: Cambodian Civil War

text: Between March and June 1970, the North Vietnamese captured most of the northeastern third of the country in engagements with the Cambodian army. The North Vietnamese turned over some of their conquests and provided other assistance to the Khmer Rouge, thus empowering what was at the time a small guerrilla movement. The Cambodian government hastened to expand its army to combat the North Vietnamese and the growing power of the Khmer Rouge.


title: Cambodian Civil War

text: The U.S. was motivated by the desire to buy time for its withdrawal from Southeast Asia, to protect its ally in South Vietnam, and to prevent the spread of communism to Cambodia. American and both South and North Vietnamese forces directly participated (at one time or another) in the fighting. The U.S. assisted the central government with massive U.S. aerial bombing campaigns and direct material and financial aid, while the North Vietnamese kept soldiers on the lands that they had previously occupied and occasionally engaged the Khmer Republic army in ground combat.


title: Cambodian Civil War

text: After five years of savage fighting, the Republican government was defeated on 17 April 1975 when the victorious Khmer Rouge proclaimed the establishment of Democratic Kampuchea. The war caused a refugee crisis in Cambodia with two million people—more than 25 percent of the population—displaced from rural areas into the cities, especially Phnom Penh which grew from about 600,000 in 1970 to an estimated population of nearly 2 million by 1975.


title: Cambodian Civil War

text: Children were widely used during and after the war, often being persuaded or forced to commit atrocities. The Cambodian government estimated that more than 20 percent of the property in the country had been destroyed during the war. In total, an estimated 275,000–310,000 people were killed as a result of the war.


title: Cambodian Civil War

text: The conflict was part of the Second Indochina War (1955–1975) which also consumed the neighboring Laos, South Vietnam, and North Vietnam individually referred to as the Laotian Civil War and the Vietnam War respectively. The Cambodian civil war led to the Cambodian genocide, one of the bloodiest in history.


title: Cambodian Civil War

text: During the early-to-mid-1960s, Prince Norodom Sihanouk's policies had protected his nation from the turmoil that engulfed Laos and South Vietnam. Neither the People's Republic of China (PRC) nor North Vietnam disputed Sihanouk's claim to represent "progressive" political policies and the leadership of the prince's domestic leftist opposition, the "Pracheachon" Party, had been integrated into the government. On 3 May 1965, Sihanouk broke diplomatic relations with the U.S., ended the flow of American aid, and turned to the PRC and the Soviet Union for economic and military assistance.


title: Cambodian Civil War

text: By the late 1960s, Sihanouk's delicate domestic and foreign policy balancing act was beginning to go awry. In 1966, an agreement was struck between the prince and the Chinese, allowing the presence of large-scale PAVN and Viet Cong troop deployments and logistical bases in the eastern border regions. He had also agreed to allow the use of the port of Sihanoukville by communist-flagged vessels delivering supplies and material to support the PAVN/Viet Cong military effort in South Vietnam. These concessions made questionable Cambodia's neutrality, which had been guaranteed by the Geneva Conference of 1954.


title: Cambodian Civil War

text: Sihanouk was convinced that the PRC, not the U.S., would eventually control the Indochinese Peninsula and that "our interests are best served by dealing with the camp that one day will dominate the whole of Asia – and coming to terms before its victory – in order to obtain the best terms possible."


title: Cambodian Civil War

text: During the same year, however, he allowed his pro-American minister of defense, General Lon Nol, to crack down on leftist activities, crushing the "Pracheachon" by accusing its members of subversion and subservience to Hanoi. Simultaneously, Sihanouk lost the support of Cambodia's conservatives as a result of his failure to come to grips with the deteriorating economic situation (exacerbated by the loss of rice exports, most of which went to the PAVN/Viet Cong) and with the growing communist military presence.


title: Cambodian Civil War

text: On 11 September 1966, Cambodia held its first open election. Through manipulation and harassment (and to Sihanouk's surprise) the conservatives won 75 percent of the seats in the National Assembly. Lon Nol was chosen by the right as prime minister and, as his deputy, they named Prince Sirik Matak; an ultraconservative member of the Sisowath branch of the royal clan and long-time enemy of Sihanouk. In addition to these developments and the clash of interests among Phnom Penh's politicized elite, social tensions created a favorable environment for the growth of a domestic communist insurgency in the rural areas.


title: Cambodian Civil War

text: The prince then found himself in a political dilemma. To maintain the balance against the rising tide of the conservatives, he named the leaders of the very group he had been oppressing as members of a "counter-government" that was meant to monitor and criticize Lon Nol's administration. One of Lon Nol's first priorities was to fix the ailing economy by halting the illegal sale of rice to the communists. Soldiers were dispatched to the rice-growing areas to forcibly collect the harvests at gunpoint, and they paid only the low government price. There was widespread unrest, especially in rice-rich Battambang Province, an area long-noted for the presence of large landowners, great disparity in wealth, and where the communists still had some influence.


title: Cambodian Civil War

text: On 11 March 1967, while Sihanouk was out of the country in France, a rebellion broke out in the area around Samlaut in Battambang, when enraged villagers attacked a tax collection brigade. With the probable encouragement of local communist cadres, the insurrection quickly spread throughout the whole region. Lon Nol, acting in the prince's absence (but with his approval), responded by declaring martial law. Hundreds of peasants were killed and whole villages were laid waste during the repression. After returning home in March, Sihanouk abandoned his centrist position and personally ordered the arrest of Khieu Samphan, Hou Yuon, and Hu Nim, the leaders of the "counter government", all of whom escaped into the northeast.


title: Cambodian Civil War

text: Simultaneously, Sihanouk ordered the arrest of Chinese middlemen involved in the illegal rice trade, thereby raising government revenues and placating the conservatives. Lon Nol was forced to resign, and, in a typical move, the prince named new leftists to the government to balance the conservatives. The immediate crisis had passed, but it engendered two tragic consequences. First, it drove thousands of new recruits into the arms of the hard-line "maquis" of the Cambodian Communist Party (which Sihanouk labelled the "Khmers rouges" ("Red Khmers")). Second, for the peasantry, the name of Lon Nol became associated with ruthless repression throughout Cambodia.


title: Cambodian Civil War

text: While the 1967 insurgency had been unplanned, the Khmer Rouge tried, without much success, to organize a more serious revolt during the following year. The prince's decimation of the Prachea Chon and the urban communists had, however, cleared the field of competition for Saloth Sar (also known as Pol Pot), Ieng Sary, and Son Sen—the Maoist leadership of the "maquisards". They led their followers into the highlands of the northeast and into the lands of the Khmer Loeu, a primitive people who were hostile to both the lowland Khmers and the central government. For the Khmer Rouge, who still lacked assistance from the North Vietnamese, it was a period of regroupment, organization, and training. Hanoi basically ignored its Chinese-sponsored allies, and the indifference of their "fraternal comrades" to their insurgency between 1967 and 1969 would make an indelible impression on the Khmer Rouge leadership.


title: Cambodian Civil War

text: On 17 January 1968, the Khmer Rouge launched their first offensive. It was aimed more at gathering weapons and spreading propaganda than in seizing territory since, at that time, the adherents of the insurgency numbered no more than 4000–5,000. During the same month, the communists established the Revolutionary Army of Kampuchea as the military wing of the party. As early as the end of the Battambang revolt, Sihanouk had begun to reevaluate his relationship with the communists. His earlier agreement with the Chinese had availed him nothing. They had not only failed to restrain the North Vietnamese, but they had actually involved themselves (through the Khmer Rouge) in active subversion within his country.


title: Cambodian Civil War

text: At the suggestion of Lon Nol (who had returned to the cabinet as defense minister in November 1968) and other conservative politicians, on 11 May 1969, the prince welcomed the restoration of normal diplomatic relations with the U.S. and created a new Government of National Salvation with Lon Nol as his prime minister. He did so "in order to play a new card, since the Asian communists are already attacking us before the end of the Vietnam War." Besides, PAVN and the Viet Cong would make very convenient scapegoats for Cambodia's ills, much more so than the minuscule Khmer Rouge, and ridding Cambodia of their presence would solve many problems simultaneously.


title: Cambodian Civil War

text: Although the U.S. had been aware of the PAVN/Viet Cong sanctuaries in Cambodia since 1966, President Lyndon B. Johnson had chosen not to attack them due to possible international repercussions and his belief that Sihanouk could be convinced to alter his policies. Johnson did, however, authorize the reconnaissance teams of the highly classified Military Assistance Command, Vietnam Studies and Observations Group (SOG) to enter Cambodia and gather intelligence on the Base Areas in 1967. The election of Richard Nixon in 1968 and the introduction of his policies of gradual U.S. withdrawal from South Vietnam and the Vietnamization of the conflict there, changed everything.


title: Cambodian Civil War

text: On 18 March 1969, on secret orders from Nixon and Henry Kissinger, the U.S. Air Force carried out the bombing of Base Area 353 (in the Fishhook region opposite South Vietnam's Tây Ninh Province) by 59 B-52 Stratofortress bombers. This strike was the first in a series of attacks on the sanctuaries that lasted until May 1970. During Operation Menu, the Air Force conducted 3,875 sorties and dropped more than 108,000 tons of ordnance on the eastern border areas. Only five high-ranking Congressional officials were informed of the bombing.


title: Cambodian Civil War

text: After the event, it was claimed by Nixon and Kissinger that Sihanouk had given his tacit approval for the raids, but this is dubious. Sihanouk told U.S. diplomat Chester Bowles on 10 January 1968, that he would not oppose American "hot pursuit" of retreating North Vietnamese troops "in remote areas [of Cambodia]," provided that Cambodians were unharmed. Kenton Clymer notes that this statement "cannot reasonably be construed to mean that Sihanouk approved of the intensive, ongoing B-52 bombing raids ... In any event, no one asked him. ... Sihanouk was never asked to approve the B-52 bombings, and he never gave his approval." During the course of the Menu bombings, Sihanouk's government formally protested "American violation[s] of Cambodian territory and airspace" at the United Nations on over 100 occasions, although it "specifically protested the use of B-52s" only once, following an attack on Bu Chric in November 1969.


title: Cambodian Civil War

text: Operation Freedom Deal followed Operation Menu. Under Freedom Deal, from 19 May 1970 to 15 August 1973, U.S. bombing of Cambodia extended over the entire eastern one-half of the country and was especially intense in the heavily populated southeastern one-quarter of the country, including a wide ring surrounding the largest city of Phnom Penh. In large areas, according to maps of U.S. bombing sites, it appears that nearly every square mile of land was hit by bombs.


title: Cambodian Civil War

text: The effectiveness of the U.S. bombing on the Khmer Rouge and the death toll of Cambodian civilians is disputed. With limited data, the range of Cambodian deaths caused by U.S. bombing may be between 30,000 and 150,000 Cambodian civilians and Khmer Rouge fighters. Another impact of the U.S. bombing and the Cambodian civil war was to destroy the homes and livelihood of many people. This was a heavy contributor to the refugee crisis in Cambodia.


title: Cambodian Civil War

text: It has been argued that the U.S. intervention in Cambodia contributed to the eventual seizure of power by the Khmer Rouge, that grew from 4,000 in number in 1970 to 70,000 in 1975. This view has been disputed, with documents uncovered from the Soviet archives revealing that the North Vietnamese offensive in Cambodia in 1970 was launched at the explicit request of the Khmer Rouge following negotiations with Nuon Chea. It has also been argued that U.S. bombing was decisive in delaying a Khmer Rouge victory. "Victory in Vietnam", the official war history of the People's Army of Vietnam, candidly states that the communist insurgency in Cambodia had already increased from "ten guerrilla teams" to several tens of thousands of fighters only two months after the North Vietnamese invasion in April 1970, as a direct result of the PAVN seizing 40% of the country, handing it over to the communist insurgents, and then actively supplying and training the insurgents.


title: Cambodian Civil War

text: While Sihanouk was out of the country on a trip to France, anti-Vietnamese rioting (which was semi-sponsored by the government) took place in Phnom Penh, during which the North Vietnamese and Viet Cong embassies were sacked. In the prince's absence, Lon Nol did nothing to halt these activities. On 12 March, the prime minister closed the port of Sihanoukville to the North Vietnamese and issued an impossible ultimatum to them. All PAVN/Viet Cong forces were to withdraw from Cambodian soil within 72 hours (on 15 March) or face military action.


title: Cambodian Civil War

text: Sihanouk, hearing of the turmoil, headed for Moscow and Beijing in order to demand that the patrons of PAVN and the Viet Cong exert more control over their clients. On 18 March 1970, Lon Nol requested that the National Assembly vote on the future of the prince's leadership of the nation. Sihanouk was ousted from power by a vote of 86–3. Cheng Heng became president of the National Assembly, while Prime Minister Lon Nol was granted emergency powers. Sirik Matak retained his post as deputy prime minister. The new government emphasized that the transfer of power had been totally legal and constitutional and it received the recognition of most foreign governments. There have been, and continue to be, accusations that the U.S. government played some role in the overthrow of Sihanouk, but conclusive evidence has never been found to support them.


title: Cambodian Civil War

text: The majority of middle-class and educated Khmers had grown weary of the prince and welcomed the change of government. They were joined by the military, for whom the prospect of the return of American military and financial aid was a cause for celebration. Within days of his deposition, Sihanouk, now in Beijing, broadcast an appeal to the people to resist the usurpers. Demonstrations and riots occurred (mainly in areas contiguous to PAVN/Viet Cong controlled areas), but no nationwide groundswell threatened the government. In one incident at Kampong Cham on 29 March, however, an enraged crowd killed Lon Nol's brother, Lon Nil, tore out his liver, and cooked and ate it. An estimated 40,000 peasants then began to march on the capital to demand Sihanouk's reinstatement. They were dispersed, with many casualties, by contingents of the armed forces.


title: Cambodian Civil War

text: Most of the population, urban and rural, took out their anger and frustrations on the nation's Vietnamese population. Lon Nol's call for 10,000 volunteers to boost the manpower of Cambodia's poorly equipped, 30,000-man army, managed to swamp the military with over 70,000 recruits. Rumours abounded concerning a possible PAVN offensive aimed at Phnom Penh itself. Paranoia flourished and this set off a violent reaction against the nation's 400,000 ethnic Vietnamese.


title: Cambodian Civil War

text: Lon Nol hoped to use the Vietnamese as hostages against PAVN/Viet Cong activities, and the military set about rounding them up into detention camps. That was when the killing began. In towns and villages all over Cambodia, soldiers and civilians sought out their Vietnamese neighbors in order to murder them. On 15 April, the bodies of 800 Vietnamese floated down the Mekong River and into South Vietnam.


title: Cambodian Civil War

text: The South Vietnamese, North Vietnamese, and the Viet Cong all harshly denounced these actions. Significantly, no Cambodians—including the Buddhist community—condemned the killings. In his apology to the Saigon government, Lon Nol stated that "it was difficult to distinguish between Vietnamese citizens who were Viet Cong and those who were not. So it is quite normal that the reaction of Cambodian troops, who feel themselves betrayed, is difficult to control."


title: Cambodian Civil War

text: From Beijing, Sihanouk proclaimed that the government in Phnom Penh was dissolved and his intention to create the "Front uni national du Kampuchéa" (National United Front of Kampuchea) or FUNK. Sihanouk later said "I had chosen not to be with either the Americans or the communists, because I considered that there were two dangers, American imperialism and Asian communism. It was Lon Nol who obliged me to choose between them."


title: Cambodian Civil War

text: The North Vietnamese reacted to the political changes in Cambodia by sending Premier Phạm Văn Đồng to meet Sihanouk in China and recruit him into an alliance with the Khmer Rouge. Pol Pot was also contacted by the Vietnamese who now offered him whatever resources he wanted for his insurgency against the Cambodian government. Pol Pot and Sihanouk were actually in Beijing at the same time, but the Vietnamese and Chinese leaders never informed Sihanouk of the presence of Pol Pot or allowed the two men to meet.


title: Cambodian Civil War

text: Shortly after, Sihanouk issued an appeal by radio to the people of Cambodia to rise up against the government and support the Khmer Rouge. In doing so, Sihanouk lent his name and popularity in the rural areas of Cambodia to a movement over which he had little control. In May 1970, Pol Pot finally returned to Cambodia and the pace of the insurgency greatly increased. After Sihanouk showed his support for the Khmer Rouge by visiting them in the field, their ranks swelled from 6,000 to 50,000 fighters.


title: Cambodian Civil War

text: The prince then allied himself with the Khmer Rouge, the North Vietnamese, the Laotian Pathet Lao and the Viet Cong, throwing his personal prestige behind the communists. On 5 May, the actual establishment of FUNK and of the "Gouvernement royal d'union nationale du Kampuchéa" or GRUNK (Royal Government of National Union of Kampuchea), was proclaimed. Sihanouk assumed the post of head of state, appointing Penn Nouth, one of his most loyal supporters, as prime minister.


title: Cambodian Civil War

text: Khieu Samphan was designated deputy prime minister, minister of defense, and commander in chief of the GRUNK armed forces (though actual military operations were directed by Pol Pot). Hu Nim became minister of information, and Hou Yuon assumed multiple responsibilities as minister of the interior, communal reforms, and cooperatives. GRUNK claimed that it was not a government-in-exile since Khieu Samphan and the insurgents remained inside Cambodia. Sihanouk and his loyalists remained in China, although the prince did make a visit to the "liberated areas" of Cambodia, including Angkor Wat, in March 1973. These visits were used mainly for propaganda purposes and had no real influence on political affairs.


title: Cambodian Civil War

text: For Sihanouk, this proved to be a marriage of convenience that was spurred on by his thirst for revenge against those who had betrayed him. For the Khmer Rouge, it was a means to greatly expand the appeal of their movement. Peasants, motivated by loyalty to the monarchy, gradually rallied to the GRUNK cause. The personal appeal of Sihanouk and widespread U.S. aerial bombardment helped recruitment. This task was made even easier for the communists after 9 October 1970, when Lon Nol abolished the loosely federalist monarchy and proclaimed the establishment of a centralized Khmer Republic.


title: Cambodian Civil War

text: The GRUNK was soon caught between the competing Communist powers: North Vietnam, China and the Soviet Union. During the visits that Chinese Premier Zhou Enlai and Sihanouk paid to North Korea in April and June 1970, respectively, they called for the establishment of a "united front of the five revolutionary Asian countries" (China, North Korea, North Vietnam, Laos, and Cambodia, the last being represented by the GRUNK). While the North Korean leaders enthusiastically welcomed the plan, it soon foundered on Hanoi's opposition. Having realized that such a front would exclude the Soviet Union and implicitly challenge the hegemonic role that the DRV had arrogated to itself in Indochina, the North Vietnamese leaders declared that all communist states should join forces against "American imperialism."


title: Cambodian Civil War

text: Indeed, the issue of Vietnamese versus Chinese hegemony over Indochina greatly influenced the attitude Hanoi adopted towards Moscow in the early and mid-1970s. During the Cambodian civil war, the Soviet leaders, ready to acquiesce in Hanoi's dominance over Laos and Cambodia, actually insisted on sending their aid shipments to the Khmer Rouge through the DRV, whereas China firmly rebuffed Hanoi's proposal that Chinese aid to Cambodia be sent via North Vietnam. Facing Chinese competition and Soviet acquiescence, the North Vietnamese leaders found the Soviet option more advantageous to their interests, a calculation that played a major role in the gradual pro-Soviet shift in Hanoi's foreign policies.


title: Cambodian Civil War

text: In the wake of the coup, Lon Nol did not immediately launch Cambodia into war. He appealed to the international community and to the United Nations in an attempt to gain support for the new government and condemned violations of Cambodia's neutrality "by foreign forces, whatever camp they come from." His hope for continued neutralism availed him no more than it had Sihanouk.


title: Cambodian Civil War

text: On 29 April 1970, the North Vietnamese had taken matters into their own hands and launched an offensive against the now renamed "Forces Armées Nationales Khmères" or FANK (Khmer National Armed Forces) with documents uncovered from the Soviet archives revealing that the offensive was launched at the explicit request of the Khmer Rouge following negotiations with Nuon Chea. The North Vietnamese overran most of northeastern Cambodia by June 1970.


title: Cambodian Civil War

text: The North Vietnamese invasion completely changed the course of the civil war. Cambodia's army was mauled, lands containing nearly half of the Cambodian population were conquered and handed over to the Khmer Rouge and North Vietnam now took an active role in supplying and training the Khmer Rouge. All of this resulted in the Cambodian government being greatly weakened and the insurgents multiplying several fold in size over the course of a few weeks. As noted in the official Vietnamese war history, "our troops helped our Cambodian friends to completely liberate five provinces with a total population of three million people... our troops also helped our Cambodian friends train cadre and expand their armed forces. In just two months the armed forces of our Cambodian allies grew from ten guerrilla teams to nine battalions and 80 companies of full-time troops with a total strength of 20,000 soldiers, plus hundreds of guerrilla squads and platoons in the villages."


title: Cambodian Civil War

text: On 29 April 1970, South Vietnamese and U.S. units unleashed a limited, multi-pronged Cambodian Campaign that Washington hoped would solve three problems: First, it would provide a shield for the American withdrawal from Vietnam (by destroying the PAVN logistical system and killing enemy troops) in Cambodia; second, it would provide a test for the policy of Vietnamization; third, it would serve as a signal to Hanoi that Nixon meant business. Despite Nixon's appreciation of Lon Nol's position, the Cambodian leader was not even informed in advance of the decision to send troops into his country. He learned about it only after it had begun from the head of the U.S. mission, who had himself learned about it from a radio broadcast.


title: Cambodian Civil War

text: Extensive logistical installations and large amounts of supplies were found and destroyed, but as reporting from the American command in Saigon disclosed, still larger amounts of military material had already been moved further from the border to shelter it from the incursion into Cambodia by the U.S. and South Vietnam.


title: Cambodian Civil War

text: On the day the incursion was launched, the North Vietnamese launched an offensive (Campaign "X") of its own against FANK forces at the request of the Khmer Rouge and in order to protect and expand their Base Areas and logistical system. By June, three months after the removal of Sihanouk, they had swept government forces from the entire northeastern third of the country. After defeating those forces, the North Vietnamese turned the newly won territories over to the local insurgents. The Khmer Rouge also established "liberated" areas in the south and the southwestern parts of the country, where they operated independently of the North Vietnamese.


title: Cambodian Civil War

text: As combat operations quickly revealed, the two sides were badly mismatched. FANK, whose ranks had been increased by thousands of young urban Cambodians who had flocked to join it in the months following the removal of Sihanouk, had expanded well beyond its capacity to absorb the new men. Later, given the press of tactical operations and the need to replace combat casualties, there was insufficient time to impart needed skills to individuals or to units, and lack of training remained the bane of FANK's existence until its collapse.


title: Cambodian Civil War

text: During the period 1974–1975, FANK forces officially grew from 100,000 to approximately 250,000 men, but probably only numbered around 180,000 due to payroll padding by their officers and due to desertions.


title: Cambodian Civil War

text: U.S. military aid (ammunition, supplies, and equipment) was funneled to FANK through the Military Equipment Delivery Team, Cambodia (MEDTC). Authorized a total of 113 officers and men, the team arrived in Phnom Penh in 1971, under the overall command of CINCPAC Admiral John S. McCain Jr. The attitude of the Nixon administration could be summed up by the advice given by Henry Kissinger to the first head of the liaison team, Colonel Jonathan Ladd: "Don't think of victory; just keep it alive." Nevertheless, McCain constantly petitioned the Pentagon for more arms, equipment, and staff for what he proprietarily viewed as "my war".


title: Cambodian Civil War

text: There were other problems. The officer corps of FANK was generally corrupt and greedy. The inclusion of "ghost" soldiers allowed massive payroll padding; ration allowances were kept by the officers while their men starved; and the sale of arms and ammunition on the black market (or to the enemy) was commonplace. Worse, the tactical ineptitude among FANK officers was as common as their greed. Lon Nol frequently bypassed the general staff and directed operations down to battalion-level while also forbidding any real coordination between the army, navy and air force.


title: Cambodian Civil War

text: The common soldiers fought bravely at first, but they were saddled with low pay (with which they had to purchase their own food and medical care), ammunition shortages, and mixed equipment. Due to the pay system, there were no allotments for their families, who were, therefore, forced to follow their husbands/sons into the battle zones. These problems (exacerbated by continuously declining morale) only increased over time.


title: Cambodian Civil War

text: At the beginning of 1974, the Cambodian army inventory included 241,630 rifles, 7,079 machine guns, 2,726 mortars, 20,481 grenade launchers, 304 recoilless rifles, 289 howitzers, 202 APCs, and 4,316 trucks. The Khmer Navy had 171 vessels; the Khmer Air Force had 211 aircraft, including 64 North American T-28s, 14 Douglas AC-47 gunships and 44 helicopters. American Embassy military personnel – who were only supposed to coordinate the arms aid program – sometimes found themselves involved in prohibited advisory and combat tasks.


title: Cambodian Civil War

text: When PAVN forces were supplanted, it was by the tough, rigidly indoctrinated peasant army of the Khmer Rouge with its core of seasoned leaders, who now received the full support of Hanoi. Khmer Rouge forces, which had been reorganized at an Indochinese summit held in Guangzhou, China in April 1970, would grow from 12 to 15,000 in 1970 to 35–40,000 by 1972, when the so-called "Khmerization" of the conflict took place and combat operations against the Republic were handed over completely to the insurgents.


title: Cambodian Civil War

text: The development of these forces took place in three stages. 1970 to 1972 was a period of organization and recruitment, during which Khmer Rouge units served as auxiliaries to the PAVN. From 1972 to mid-1974, the insurgents formed units of battalion and regimental size. It was during this period that the Khmer Rouge began to break away from Sihanouk and his supporters and the collectivization of agriculture was begun in the "liberated" areas. Division-sized units were being fielded by 1974–1975, when the party was on its own and began the radical transformation of the country.


title: Cambodian Civil War

text: With the fall of Sihanouk, Hanoi became alarmed at the prospect of a pro-Western regime that might allow the Americans to establish a military presence on their western flank. To prevent that from happening, they began transferring their military installations away from the border regions to locations deeper within Cambodian territory. A new command center was established at the city of Kratié and the timing of the move was propitious. President Nixon was of the opinion that:


title: Cambodian Civil War

text: During the night of 21 January 1971, a force of 100 PAVN/Viet Cong commandos attacked Pochentong airfield, the main base of the Khmer Air Force. In this one action, the raiders destroyed almost the entire inventory of government aircraft, including all of its fighter planes. This may have been a blessing in disguise, however, since the air force was largely composed of old (even obsolete) Soviet aircraft. The Americans soon replaced the airplanes with more advanced models. The attack did, however, stall a proposed FANK offensive. Two weeks later, Lon Nol had a stroke and was evacuated to Hawaii for treatment. It had been a mild stroke, however, and the general recovered quickly, returning to Cambodia after only two months.


title: Cambodian Civil War

text: It was not until 20 August that FANK launched Operation Chenla II, its first offensive of the year. The objective of the campaign was to clear Route 6 of enemy forces and thereby reopen communications with Kompong Thom, the Republic's second largest city, which had been isolated from the capital for more than a year. The operation was initially successful, and the city was relieved. The PAVN and Khmer Rouge counterattacked in November and December, annihilating government forces in the process. There was never an accurate count of the losses, but the estimate was "on the order of ten battalions of personnel and equipment lost plus the equipment of an additional ten battalions." The strategic result of the failure of "Chenla II" was that the offensive initiative passed completely into the hands of PAVN and the Khmer Rouge.


title: Cambodian Civil War

text: From 1972 through 1974, the war was conducted along FANK's lines of communications north and south of the capital. Limited offensives were launched to maintain contact with the rice-growing regions of the northwest and along the Mekong River and Route 5, the Republic's overland connections to South Vietnam. The strategy of the Khmer Rouge was to gradually cut those lines of communication and squeeze Phnom Penh. As a result, FANK forces became fragmented, isolated, and unable to lend one another mutual support.


title: Cambodian Civil War

text: The main U.S. contribution to the FANK effort came in the form of the bombers and tactical aircraft of the U.S. Air Force. When President Nixon launched the incursion in 1970, American and South Vietnamese troops operated under an umbrella of air cover that was designated Operation Freedom Deal. When those troops were withdrawn, the air operation continued, ostensibly to interdict PAVN/Viet Cong troop movements and logistics. In reality (and unknown to the U.S. Congress and American public), they were utilized to provide tactical air support to FANK. As a former U.S. military officer in Phnom Penh reported, "the areas around the Mekong River were so full of bomb craters from B-52 strikes that, by 1973, they looked like the valleys of the moon."


title: Cambodian Civil War

text: On 10 March 1972, just before the newly renamed Constituent Assembly was to approve a revised constitution, Lon Nol suspended the deliberations. He then forced Cheng Heng, the head of state since Sihanouk's deposition, to surrender his authority to him. On the second anniversary of the coup, Lon Nol relinquished his authority as head of state, but retained his position as prime minister and defense minister.


title: Cambodian Civil War

text: On 4 June, Lon Nol was elected as the first president of the Khmer Republic in a blatantly rigged election. As per the new constitution (ratified on 30 April), political parties formed in the new nation, quickly becoming a source of political factionalism. General Sutsakhan stated: "the seeds of democratization, which had been thrown into the wind with such goodwill by the Khmer leaders, returned for the Khmer Republic nothing but a poor harvest."


title: Cambodian Civil War

text: In January 1973, hope was renewed when the Paris Peace Accords were signed, ending the conflict (for the time being) in South Vietnam and Laos. On 29 January, Lon Nol proclaimed a unilateral cease-fire throughout the nation. All U.S. bombing operations were halted in hopes of securing a chance for peace. It was not to be. The Khmer Rouge simply ignored the proclamation and carried on fighting. By March, heavy casualties, desertions, and low recruitment had forced Lon Nol to introduce conscription, and in April insurgent forces launched an offensive that pushed into the suburbs of the capital. The U.S. Air Force responded by launching an intense bombing operation that forced the communists back into the countryside after being decimated by the air strikes. The U.S. Seventh Air Force argued that the bombing prevented the fall of Phnom Penh in 1973 by killing 16,000 of 25,500 Khmer Rouge fighters besieging the city.


title: Cambodian Civil War

text: By the last day of Operation Freedom Deal (15 August 1973), 250,000 tons of bombs had been dropped on the Khmer Republic, 82,000 tons of which had been released in the last 45 days of the operation. Since the inception of Operation Menu in 1969, the U.S. Air Force had dropped 539,129 tons of ordnance on Cambodia/Khmer Republic.


title: Cambodian Civil War

text: As late as 1972–1973, it was a commonly held belief, both within and outside Cambodia, that the war was essentially a foreign conflict that had not fundamentally altered the nature of the Khmer people. By late 1973, there was a growing awareness among the government and population of Cambodia that the extremism, total lack of concern over casualties, and complete rejection of any offer of peace talks "began to suggest that Khmer Rouge fanaticism and capacity for violence were deeper than anyone had suspected."


title: Cambodian Civil War

text: Reports of the brutal policies of the organization soon made their way to Phnom Penh and into the population foretelling the violence that was about to consume the nation. There were tales of the forced relocations of entire villages, of the summary execution of any who disobeyed or even asked questions, the forbidding of religious practices, of monks who were defrocked or murdered, and where traditional sexual and marital habits were foresworn. War was one thing; the offhand manner in which the Khmer Rouge dealt out death, so contrary to the Khmer character, was quite another. Reports of these atrocities began to surface during the same period in which North Vietnamese troops were withdrawing from the Cambodian battlefields. This was no coincidence. The concentration of the PAVN effort on South Vietnam allowed the Khmer Rouge to apply their doctrine and policies without restraint for the first time.


title: Cambodian Civil War

text: The Khmer Rouge leadership was almost completely unknown by the public. They were referred to by their fellow countrymen as "peap prey" – the forest army. Previously, the very existence of the communist party as a component of GRUNK had been hidden. Within the "liberated zones" it was simply referred to as "Angka" – the organization. During 1973, the communist party fell under the control of its most fanatical members, Pol Pot and Son Sen, who believed that "Cambodia was to go through a total social revolution and that everything that had preceded it was anathema and must be destroyed."


title: Cambodian Civil War

text: Also hidden from scrutiny was the growing antagonism between the Khmer Rouge and their North Vietnamese allies. The radical leadership of the party could never escape the suspicion that Hanoi had designs on building an Indochinese federation with the North Vietnamese as its master. The Khmer Rouge were ideologically tied to the Chinese, while North Vietnam's chief supporters, the Soviet Union, still recognized the Lon Nol government as legitimate.


title: Cambodian Civil War

text: After the signing of the Paris Peace Accords, PAVN cut off the supply of arms to the Khmer Rouge, hoping to force them into a cease-fire. When the Americans were freed by the signing of the accords to turn their air power completely on the Khmer Rouge, this too was blamed on Hanoi. During the year, these suspicions and attitudes led the party leadership to carry out purges within their ranks. Most of the Hanoi-trained members were then executed on the orders of Pol Pot.


title: Cambodian Civil War

text: As time passed, the need of the Khmer Rouge for the support of Prince Sihanouk lessened. The organization demonstrated to the people of the 'liberated' areas in no uncertain terms that open expressions of support for Sihanouk would result in their liquidation. Although the prince still enjoyed the protection of the Chinese, when he made public appearances overseas to publicize the GRUNK cause, he was treated with almost open contempt by Ministers Ieng Sary and Khieu Samphan. In June, the prince told Italian journalist Oriana Fallaci that when "they [the Khmer Rouge] have sucked me dry, they will spit me out like a cherry stone."


title: Cambodian Civil War

text: By the end of 1973, Sihanouk loyalists had been purged from all of GRUNK's ministries, and all of the prince's supporters within the insurgent ranks were also eliminated. Shortly after Christmas, as the insurgents were gearing up for their final offensive, Sihanouk spoke with the French diplomat Etienne Manac'h. He said that his hopes for a moderate socialism akin to Yugoslavia's must now be totally dismissed. Hoxha's Albania, he said, would be the model.


title: Cambodian Civil War

text: By the time the Khmer Rouge initiated their dry-season offensive to capture the beleaguered Cambodian capital on 1 January 1975, the Republic was in chaos. The economy had been gutted, the transportation network had been reduced to air and waterways, the rice harvest had fallen by one-quarter, and the supply of freshwater fish (the chief source of protein for the country) had declined drastically. The cost of food was 20 times greater than pre-war levels, while unemployment was not even measured anymore.


title: Cambodian Civil War

text: Phnom Penh, which had a pre-war population of around 600,000, was overwhelmed by refugees (who continued to flood in from the steadily collapsing defense perimeter), growing to a size of around two million. These helpless and desperate civilians had no jobs and little in the way of food, shelter, or medical care. Their condition (and the government's) only worsened when Khmer Rouge forces gradually gained control of the banks of the Mekong. From the riverbanks, their mines and gunfire steadily reduced the river convoys through which 90 percent of the Republic's supplies moved, bringing relief supplies of food, fuel, and ammunition to the slowly starving city from South Vietnam.


title: Cambodian Civil War

text: After the river was effectively blocked in early February, the U.S. began an airlift of supplies into Pochentong Airport. This became increasingly risky, however, due to communist rocket and artillery fire, which constantly rained down on the airfield and city. The Khmer Rouge cut off overland supplies to the city for more than a year before it fell on 17 April 1975. Reports from journalists stated that the Khmer Rouge shelling "tortured the capital almost continuously," inflicting "random death and mutilation" on millions of trapped civilians.


title: Cambodian Civil War

text: Desperate but determined units of FANK soldiers, many of whom had run out of ammunition, dug in around the capital and fought until they were overrun as the Khmer Rouge advanced. By the last week of March 1975, approximately 40,000 communist troops had surrounded the capital and began preparing to deliver the "coup de grace" to about half as many FANK forces.


title: Cambodian Civil War

text: Lon Nol resigned and left the country on 1 April, hoping that a negotiated settlement might still be possible if he was absent from the political scene. Saukam Khoy became acting president of a government that had less than three weeks to live. Last-minute efforts on the part of the U.S. to arrange a peace agreement involving Sihanouk ended in failure. When a vote in the U.S. Congress for a resumption of American air support failed, panic and a sense of doom pervaded the capital. The situation was best described by General Sak Sutsakhan (now FANK chief of staff):


title: Cambodian Civil War

text: On 12 April, concluding that all was lost, the U.S. evacuated its embassy personnel by helicopter during Operation Eagle Pull. The 276 evacuees included U.S. Ambassador John Gunther Dean, other American diplomatic personnel, Acting President Saukam Khoy, senior Khmer Republic government officials and their families, and members of the news media. In all, 82 U.S., 159 Cambodian, and 35 third-country nationals were evacuated. Although invited by Ambassador Dean to join the evacuation (and much to the Americans' surprise), Prince Sisowath Sirik Matak, Long Boret, Lon Non (Lon Nol's brother), and most members of Lon Nol's cabinet declined the offer. All of them chose to share the fate of their people. Their names were not published on the death lists and many trusted the Khmer Rouge's assertions that former government officials would not be murdered, but would be welcome in helping to rebuild a new Cambodia.