Informal Formulation of The Algorithm
| Dividend | Divisor | Quotient | Remainder |
|---|---|---|---|
| 120 | 23 | 5 | 5 |
| 23 | 5 | 4 | 3 |
| 5 | 3 | 1 | 2 |
| 3 | 2 | 1 | 1 |
| 2 | 1 | 2 | 0 |
To illustrate the extension of Euclid's algorithm, consider the computation of gcd(120, 23), which is shown on the table on the left. Notice that the quotient in each division is recorded as well alongside the remainder.
In this case, the remainder in the fourth line (which is equal to 1) indicates that the gcd is 1; that is, 120 and 23 are coprime (also called relatively prime). For the sake of simplicity, the example chosen is a coprime pair; but the more general case of gcd other than 1 also works similarly.
There are two methods to proceed, both using an integer division algorithm as a subprocedure, which will be discussed separately.
Read more about this topic: Extended Euclidean Algorithm
Famous quotes containing the words informal and/or formulation:
“We as a nation need to be reeducated about the necessary and sufficient conditions for making human beings human. We need to be reeducated not as parents—but as workers, neighbors, and friends; and as members of the organizations, committees, boards—and, especially, the informal networks that control our social institutions and thereby determine the conditions of life for our families and their children.”
—Urie Bronfenbrenner (b. 1917)
“In necessary things, unity; in disputed things, liberty; in all things, charity.”
—Variously Ascribed.
The formulation was used as a motto by the English Nonconformist clergyman Richard Baxter (1615-1691)