nyuuzyou/wikis huggingface dataset:
Euclid's Theorem/Corollary 1/Proof 1

== Corollary to Euclid's Theorem ==
== Proof ==
Assume that there are only finitely many prime numbers, and that there is a grand total of $n$ primes.
Then it is possible to define the set of all primes:
: $\mathbb P = \set {p_1, p_2, \ldots, p_n}$
From Euclid's Theorem, however, we can always create a prime which is not in $\mathbb P$.
So we can never create a finite list of all the primes, because we can guarantee to construct a number which has prime factors that are not in this list.
Thus, there are infinitely many prime numbers.
== Historical Note ==
== Sources ==
* : Chapter $3$: The Integers: $\S 13$. Unique Factorisation: Theorem $23$
* : Chapter $2$: Some Properties of $\Z$: Exercise $2.15$
* : Chapter $2$: Integers and natural numbers: $\S 2.2$: Divisibility and factorization in $\mathbf Z$: Theorem $5$
Category:Euclid's Theorem
Euclid's Theorem/Corollary 1/Proof 2

== Corollary to Euclid's Theorem ==
There are infinitely many prime numbers.
== Proof ==
Assume that there are only finitely many prime numbers.
Let $p$ be the largest of these.
Then from Existence of Prime between Prime and Factorial there exists a prime number $q$ such that:
:$p < q \le p! + 1$
So there cannot be such a $p$.
== Sources ==
* : Appendix $1$: Some Results from the Elementary Theory of Numbers: Theorem $4$
Category:Euclid's Theorem
Euclid's Theorem/Corollary 2/Proof 1

== Corollary to Euclid's Theorem ==
== Proof ==
Let $\mathbb P$ be the set of all prime numbers.
 there exists a largest prime number $p_m$.
Then:
:$\mathbb P \subseteq \closedint 1 {p_m} = \set {1, 2, \ldots, p_m}$
and so $\mathbb P$ is a finite set.
By Euclid's Theorem, there exists a prime number $q$ such that $q \notin \mathbb P$.
But that means $q \notin \closedint 1 {p_m}$.
That is, $q > p_m$.
So $p_m$ is not the largest prime number after all.
Hence the result, by Proof by Contradiction.
Category:Euclid's Theorem
Euclid's Theorem/Corollary 2/Proof 2

== Corollary to Euclid's Theorem ==
== Proof ==
 there exists a largest prime number $p$.
Let $b = p! + 1$.
Let $q$ be a prime number that divides $b$.
Since $p$ is the largest prime number, $q \le p$.
However, no positive integer $d \le p$ is a divisor of $b$.
Hence $q \not \le p$.
Hence the result, by Proof by Contradiction.
== Sources ==
* : $\S 1.12$: Valid Arguments: Proposition $1.12.2$
Category:Euclid's Theorem
Euclid's Theorem/Fallacy

== Fallacy ==
There is a fallacy associated with Euclid's Theorem.
It is often seen to be stated that: the number made by multiplying all the primes together and adding $1$ is not divisible by any members of that set.
So it is not divisible by any primes and is therefore itself prime.
That is, sometimes readers think that if $P$ is the product of the first $n$ primes then $P + 1$ is itself prime.
This is not the case.
For example:
:$\left({2 \times 3 \times 5 \times 7 \times 11 \times 13}\right) + 1 = 30\ 031 = 59 \times 509$
both of which are prime, but, take note, not in that list of six primes that were multiplied together to get $30\ 030$ in the first place.
Category:Euclid's Theorem
Category:Fallacies
Euclidean Algorithm

== Algorithm ==
The Euclidean algorithm is a method for finding the greatest common divisor (GCD) of two integers $a$ and $b$.
Let $a, b \in \Z$ and $a \ne 0 \lor b \ne 0$.
The steps are:
:$(1): \quad$ Start with $\tuple {a, b}$ such that $\size a \ge \size b$. If $b = 0$ then the task is complete and the GCD is $a$.
:$(2): \quad$ If $b \ne 0$ then you take the remainder $r$ of $\dfrac a b$.
:$(3): \quad$ Set $a \gets b, b \gets r$ (and thus $\size a \ge \size b$ again).
:$(4): \quad$ Repeat these steps until $b = 0$.
Thus the GCD of $a$ and $b$ is the value of the variable $a$ after the termination of the algorithm.
=== Variant: Least Absolute Remainder ===
== Proof 1 ==
== Proof 2 ==
== Euclid's Proof ==
== Demonstration ==
== Algorithmic Nature ==
== Formal Implementation ==
== Constructing an Integer Combination ==
== Also known as ==
== Examples ==
== Also see ==
* Rational Numbers and Simple Finite Continued Fractions are Equivalent‎ for an application of the Euclidean algorithm in a slightly different context.
== Historical Note ==
== Sources ==
* : $\S 3.11$
* : $\text {2-2}$ Divisibility: Theorem $\text {2-2}$
* : Chapter $1$: Properties of the Natural Numbers: $\S 23 \zeta$
* : $\S 12$: Highest common factors and Euclid's algorithm
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm
* : $5$
* 
* 
* : $\text{A}.1$: Number theory
* : $\S 1.1$: Algorithms: Algorithm $\text{E}$
* : $5$
* 
* 
* 
* 
* 
Category:Euclidean Algorithm
Category:Number Theory
Category:Greatest Common Divisor
Category:Euclid Book VII
Euclidean Algorithm/Algorithmic Nature

== Algorithm ==
It can be seen from the definition that the Euclidean Algorithm is indeed an algorithm:
* Finiteness: As has been seen, the algorithm always terminates after a finite number of steps.
* Definiteness: Each of the steps is precisely defined.
* The inputs are $a$ and $b$.
* The output is $\gcd \left\{{a, b}\right\}$.
* Effectiveness: Each operation is finite in extent and can be effectively performed.
Category:Euclidean Algorithm
Euclidean Algorithm/Construction of Integer Combination

== Construction of Integer Combination from Euclidean Algorithm ==
Having determined the GCD of $a$ and $b$ using the Euclidean Algorithm, we are now in a position to find a solution to $\gcd \set {a, b} = x a + y b$ for $x$ and $y$.
By Bézout's Identity it is always possible to find such an $x, y \in \Z$.
Working back through the equations generated during the course of working the Euclidean Algorithm, we get:
... and so on. The algebra gets messier the further up the tree you go, and is not immediately enlightening.
Thus eventually we arrive at $\gcd \set {a, b} = x a + y b$ where $x$ and $y$ are numbers made up from some algebraic cocktail of the coefficients of the terms involving the remainders from the various applications of the Division Theorem.
Note that $a \divides b \implies \gcd \set {a, b} = a$, from GCD of Integer and Divisor.
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm
Category:Euclidean Algorithm
Euclidean Algorithm/Demonstration

== Example of use of Euclidean Algorithm ==
Using the Euclidean Algorithm, we can investigate in detail what happens when we apply the Division Theorem repeatedly to $a$ and $b$.
From the Division Theorem, we know that the remainder is always strictly less than the divisor.
That is, in $a = q b + r$:
:$0 \le r < \size b$
So we know that:
:$b > r_1 > r_2 > \ldots > r_{n - 2} > r_{n - 1} > r_n > 0$
So the algorithm has to terminate.
== Sources ==
* : $\text {2-2}$ Divisibility: Theorem $\text {2-2}$
* : $\S 12$: Highest common factors and Euclid's algorithm
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm
* : $\text{A}.1$: Number theory
Category:Euclidean Algorithm
Euclidean Algorithm/Euclid's Proof

== Theorem ==
== Proof ==
Let $AB, CD$ be the two given (natural) numbers which are not coprime.
We need to find the greatest common divisor of $AB$ and $CD$.
:
 that $CD \le AB$.
We have that $CD$ is a divisor of itself.
If $CD$ is a divisor of $AB$ then $CD$ is a common divisor of $CD$ and $AB$.
It is clearly the greatest, because no number greater than $CD$ can be a divisor of $CD$.
Now, suppose $CD$ does not divide $AB$.
Then the less of the numbers $AB, CD$ being continually subtracted from the greater, some number will be left which will be a divisor of the one before it.
From Coprimality Criterion, this number will not be a unit, otherwise $AB$ and $CD$ will be coprime.
So some number will be left which is a divisor of the one before it.
Now let $CD$, dividing $BE$, leave $EA$ less than itself.
Let $EA$, dividing $DF$, leave $FC$ less than itself.
Let $CF$ divide $AE$.
Since then $CF$ divides $AE$, and $AE$ divides $DF$, then $CF$ will also divide $DF$.
But it also divides itself.
Therefore it will also divide the whole $CD$.
But $CD$ divides $BE$, therefore $CF$ divides $BE$.
But it also divides $EA$, therefore it will also divide the whole $BA$.
So $CF$ is a common divisor of $CD$ and $AB$.
Suppose $CF$ is not the greatest common divisor of $CD$ and $AB$.
Let $G > CF$ also be a common divisor of $CD$ and $AB$.
Since $G$ divides $CD$, while $CD$ divides $BE$, it follows that $G$ divides $BE$.
But $G$ also divides the whole $BA$, and so it also divides the remainder $AE$.
But $AE$ divides $DF$.
Therefore $G$ divides $DF$.
But $G$ also divides the whole $DC$.
Therefore it will also divide the remainder $CF$.
But $G$ is greater than $CF$, which is impossible.
Therefore no number greater than $CF$ divides the numbers $AB$ and $CD$.
Therefore $CF$ is the greatest common divisor of $AB$ and $CD$.
== Porism ==
== Sources ==
* : Book $\text{VII}$. Propositions
* : Chapter $1$: Properties of the Natural Numbers: $\S 23 \zeta$
* : Chapter $\text {A}.4$: Euclid (flourished ca. $300$ B.C.)
Category:Euclidean Algorithm
Euclidean Algorithm/Examples

== Examples of Use of Euclidean Algorithm ==
=== GCD of $341$ and $527$ ===
=== GCD of $2190$ and $465$ ===
=== GCD of $9 n + 8$ and $6 n + 5$ ===
=== Solution of $31 x \equiv 1 \pmod {56}$ ===
=== GCD of $24$ and $138$ ===
=== GCD of $34$ and $102$ ===
=== GCD of $52$ and $273$ ===
=== GCD of $56$ and $72$ ===
=== GCD of $108$ and $243$ ===
=== GCD of $119$ and $272$ ===
=== GCD of $129$ and $301$ ===
=== GCD of $132$ and $473$ ===
=== GCD of $143$ and $227$ ===
=== GCD of $156$ and $1740$ ===
=== GCD of $272$ and $1479$ ===
=== GCD of $299$ and $481$ ===
=== GCD of $306$ and $657$ ===
=== GCD of $361$ and $1178$ ===
=== GCD of $527$ and $765$ ===
=== GCD of $595$ and $721$ ===
=== GCD of $1769$ and $2378$ ===
=== GCD of $2145$ and $1274$ ===
=== GCD of $12321$ and $8658$ ===
=== GCD of $12378$ and $3054$ ===
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/108 and 243

== Examples of Use of Euclidean Algorithm ==
The GCD of $108$ and $243$ is:
:$\gcd \set {108, 243} = 27$
== Proof ==
Thus:
:$\gcd \set {108, 243} = 27$
== Sources ==
* : $\text {2-2}$ Divisibility: Exercise $1 \ \text{(d)}$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/119 and 272/Integer Combination

== Examples of Use of Euclidean Algorithm ==
$6$ can be expressed as an integer combination of $119$ and $272$:
:$17 = 7 \times 119 - 3 \times 272$
== Proof ==
From Euclidean Algorithm: $119$ and $272$ we have:
and so:
:$\gcd \set {119, 272} = 17$
Then we have:
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm: Problems $2.3$: $2 \ \text{(c)}$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/12321 and 8658

== Examples of Use of Euclidean Algorithm ==
The GCD of $12321$ and $8658$ is:
:$\gcd \set {12321, 8658} = 333$
== Proof ==
Thus:
:$\gcd \set {12321, 8658} = 333$
== Sources ==
* : $\text {2-2}$ Divisibility: Exercise $1 \ \text{(c)}$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/12378 and 3054

== Examples of Use of Euclidean Algorithm ==
The GCD of $12378$ and $3054$ is:
:$\gcd \set {12378, 3054} = 6$
=== Integer Combination ===
== Proof ==
Thus:
:$\gcd \set {12378, 3054} = 6$
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/12378 and 3054/Integer Combination

== Examples of Use of Euclidean Algorithm ==
$6$ can be expressed as an integer combination of $12378$ and $3054$:
:$6 = 132 \times 12378 - 535 \times 3054$
Note also that:
:$6 = 3186 \times 12378 - 12913 \times 3054$
by adding $3054 \times 12378$ to both sides.
== Proof ==
From Euclidean Algorithm: $12378$ and $3054$ we have:
:$\gcd \set {12378, 3054} = 6$
Then we have:
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/129 and 301

== Examples of Use of Euclidean Algorithm ==
The GCD of $129$ and $301$ is found to be:
:$\gcd \set {129, 301} = 43$
Hence $43$ can be expressed as an integer combination of $129$ and $301$:
:$43 = 1 \times 301 - 2 \times 129$
== Proof ==
Thus:
:$\gcd \set {129, 301} = 43$
Then we have:
== Sources ==
* : $\text {2-2}$ Divisibility: Exercise $3$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/132 and 473

== Examples of Use of Euclidean Algorithm ==
The GCD of $132$ and $473$ is:
:$\gcd \set {132, 473} = 11$
== Proof ==
Thus:
:$\gcd \set {132, 473} = 11$
== Sources ==
* : $\text {2-2}$ Divisibility: Exercise $1 \ \text{(e)}$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/143 and 227

== Examples of Use of Euclidean Algorithm ==
The GCD of $143$ and $227$ is:
:$\gcd \set {143, 227} = 1$
== Proof ==
Thus:
:$\gcd \set {143, 227} = 1$
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm: Problems $2.3$: $1$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/156 and 1740

== Examples of Use of Euclidean Algorithm ==
The GCD of $156$ and $1740$ is:
:$\gcd \set {156, 1740} = 12$
== Proof ==
Thus:
:$\gcd \set {156, 1740} = 12$
== Sources ==
* : $\text {2-2}$ Divisibility: Exercise $1 \ \text{(f)}$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/1769 and 2378/Integer Combination

== Examples of Use of Euclidean Algorithm ==
$6$ can be expressed as an integer combination of $1769$ and $2378$:
:$29 = 39 \times 1769 - 29 \times 2378$
== Proof ==
From Euclidean Algorithm: $1769$ and $2378$ we have:
and so:
:$\gcd \set {1769, 2378} = 29$
Then we have:
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm: Problems $2.3$: $2 \ \text{(d)}$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/2145 and 1274

== Examples of Use of Euclidean Algorithm ==
The GCD of $2145$ and $1274$ is:
:$\gcd \set {2145, 1274} = 13$
Hence $13$ can be expressed as an integer combination of $2190$ and $465$:
:$13 = 32 \times 1274 - 19 \times 2145$
== Proof ==
Thus:
:$\gcd \set {2145, 1274} = 13$
Then we have:
== Sources ==
* : Chapter $3$: The Integers: $\S 11$. Highest Common Factor
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/2190 and 465

== Examples of Use of Euclidean Algorithm ==
The GCD of $2190$ and $465$ is found to be:
:$\gcd \set {2190, 465} = 15$
Hence $15$ can be expressed as an integer combination of $2190$ and $465$:
:$15 = 33 \times 465 - 7 \times 2190$
== Proof ==
Thus:
:$\gcd \set {2190, 465} = 15$
Then we have:
== Sources ==
* : $\S 12$: Highest common factors and Euclid's algorithm
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/24 and 138/Integer Combination

== Examples of Use of Euclidean Algorithm ==
$6$ can be expressed as an integer combination of $24$ and $138$:
:$6 = 6 \times 24 - 1 \times 138$
== Proof ==
From Euclidean Algorithm: $24$ and $138$ we have:
and so:
:$\gcd \set {24, 138} = 6$
Then we have:
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm: Problems $2.3$: $2 \ \text{(b)}$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/272 and 1479

== Examples of Use of Euclidean Algorithm ==
The GCD of $272$ and $1479$ is:
:$\gcd \set {272, 1479} = 17$
== Proof ==
Thus:
:$\gcd \set {272, 1479} = 17$
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm: Problems $2.3$: $1$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/299 and 481

== Examples of Use of Euclidean Algorithm ==
The GCD of $299$ and $481$ is found to be:
:$\gcd \set {299, 481} = 13$
Hence $13$ can be expressed as an integer combination of $299$ and $481$:
:$13 = 5 \times 481 - 8 \times 299$
== Proof ==
Thus:
:$\gcd \set {299, 481} = 13$
Then we have:
== Sources ==
* : $\text {2-2}$ Divisibility: Exercise $2$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/306 and 657

== Examples of Use of Euclidean Algorithm ==
The GCD of $306$ and $657$ is:
:$\gcd \set {306, 657} = 9$
== Proof ==
Thus:
:$\gcd \set {306, 657} = 9$
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm: Problems $2.3$: $1$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/31x = 1 mod 56

== Example of Use of Euclidean Algorithm ==
Let $x \in \Z$ be an integer such that:
:$31 x \equiv 1 \pmod {56}$
Then by using the Euclidean Algorithm:
:$x = -9$
is one such $x$.
== Proof ==
Then:
So:
:$-9 \times 31 + 5 \times 56 = 1$
and so:
:$-9 \times 31 \equiv 1 \pmod {56}$
as required.
== Sources ==
* : Chapter $2$: Some Properties of $\Z$: Exercise $2.11$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/341 and 527

== Examples of Use of Euclidean Algorithm ==
The GCD of $341$ and $527$ is found to be:
:$\gcd \set {341, 527} = 31$
=== Integer Combination ===
== Proof ==
== Sources ==
* : $\text {2-2}$ Divisibility: Example $\text {2-7}$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/341 and 527/Integer Combination

== Examples of Use of Euclidean Algorithm ==
$31$ can be expressed as an integer combination of $341$ and $527$:
:$31 = 2 \times 527 - 3 \times 341$
Note also that:
:$31 = 14 \times 341 - 9 \times 527$
and:
:$31 = 13 \times 527 - 20 \times 341$
== Proof ==
From Euclidean Algorithm: $341$ and $527$ we have:
and so:
:$\gcd \set {341, 527} = 31$
Then we have:
== Sources ==
* : $\text {2-2}$ Divisibility: Example $\text {2-8}$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/34 and 102

== Examples of Use of Euclidean Algorithm ==
The GCD of $34$ and $102$ is found to be:
:$\gcd \set {34, 102} = 34$
== Proof ==
Thus:
:$\gcd \set {34, 102} = 34$
== Sources ==
* 
* 
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/361 and 1178

== Examples of Use of Euclidean Algorithm ==
The GCD of $361$ and $1178$ is:
:$\gcd \set {361, 1178} = 19$
== Proof ==
Thus:
:$\gcd \set {361, 1178} = 19$
== Sources ==
* : $\text {2-2}$ Divisibility: Exercise $1 \ \text{(b)}$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/527 and 765

== Examples of Use of Euclidean Algorithm ==
The GCD of $527$ and $765$ is:
:$\gcd \set {527, 765} = 17$
== Proof ==
Thus:
:$\gcd \set {527, 765} = 17$
== Sources ==
* : $\text {2-2}$ Divisibility: Exercise $1 \ \text{(a)}$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/52 and 273

== Examples of Use of Euclidean Algorithm ==
The GCD of $52$ and $273$ is found to be:
:$\gcd \set {52, 273} = 13$
== Proof ==
Thus:
:$\gcd \set {52, 273} = 13$
== Sources ==
* 
* 
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/56 and 72/Integer Combination

== Examples of Use of Euclidean Algorithm ==
$8$ can be expressed as an integer combination of $56$ and $72$:
:$8 = 4 \times 56 - 3 \times 72$
== Proof ==
From Euclidean Algorithm: $56$ and $72$ we have:
and so:
:$\gcd \set {56, 72} = 8$
Then we have:
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm: Problems $2.3$: $2 \ \text{(a)}$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/595 and 721

== Examples of Use of Euclidean Algorithm ==
The GCD of $595$ and $721$ is found to be:
:$\gcd \set {595, 721} = 7$
== Proof ==
Thus:
:$\gcd \set {595, 721} = 7$
== Sources ==
* 
* 
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Examples/9n+8 and 6n+5

== Examples of Use of Euclidean Algorithm ==
The GCD of $9 n + 8$ and $6 n + 5$ is found to be:
:$\gcd \set {9 n + 8, 6 n + 5} = 1$
Hence:
:$2 \paren {9 n + 8} - 3 \paren {6 n + 5} = 1$
== Proof ==
Thus:
:$\gcd \set {9 n + 8, 6 n + 5} = 1$
Then we have:
== Sources ==
* : Chapter $2$: Some Properties of $\Z$: Exercise $2.3$
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Formal Implementation

== Implementation ==
The Euclidean algorithm can be implemented as a computational method $\struct {Q, I, \Omega, f}$ as follows:
Let $Q$ be the set of:
:all singletons $\tuple n$
:all ordered pairs $\tuple {m, n}$
:all ordered quadruples:
::$\tuple {m, n, r, 1}$
::$\tuple {m, n, r, 2}$
::$\tuple {m, n, p, 3}$
where $m, n, p \in \Z_{> 0}$ and $r \in \Z_{\ge 0}$.
Let $I \subseteq Q$ be the set of all ordered pairs $\tuple {m, n}$.
Let $\Omega$ be the set of all singletons $\tuple n$.
Let $f: Q \to Q$ be defined as follows:
where $\map \rem {m, n}$ denotes the remainder of $m$ on division by $n$.
== Sources ==
* : $\S 1.1$: Algorithms
Category:Euclidean Algorithm
Euclidean Algorithm/Historical Note

== Historical Note on Euclidean Algorithm ==
This proof is Proposition $2$ of Book $\text {VII}$ of .
According to , in his of $1980$, there exists historical evidence that the Euclidean Algorithm actually predates .
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm
Category:Historical Notes
Euclidean Algorithm/Least Absolute Remainder

== Algorithm ==
The Euclidean algorithm is a method for finding the greatest common divisor (GCD) of two integers $a$ and $b$.
Let $a, b \in \Z$ and $a \ne 0 \lor b \ne 0$.
The steps are:
:$(1): \quad$ Start with $\tuple {a, b}$ such that $\size a \ge \size b$. If $b = 0$ then the task is complete and the GCD is $a$.
:$(2): \quad$ If $b \ne 0$ then you take the least absolute residue $r$ such that:
::::$a = q b + r: -\dfrac b 2 < r \le \dfrac b 2$
:$(3): \quad$ Set $a \gets b, b \gets r$ (and thus $\size a \ge \size b$ again).
:$(4): \quad$ Repeat these steps until $b = 0$.
Thus the GCD of $a$ and $b$ is the value of the variable $a$ after the termination of the algorithm.
== Also known as ==
== Examples ==
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm
* 
* 
Category:Euclidean Algorithm
Euclidean Algorithm/Least Absolute Remainder/Examples/12378 and 3054

== Examples of Use of Euclidean Algorithm: Least Absolute Remainder Variant ==
The GCD of $12378$ and $3054$ is:
:$\gcd \set {12378, 3054} = 6$
and takes $4$ division operations to get there.
=== Integer Combination ===
== Proof ==
Thus:
:$\gcd \set {12378, 3054} = 6$
As can be seen, it takes $4$ division operations.
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm
Category:Examples of Euclidean Algorithm
Euclidean Algorithm/Proof 1

== Algorithm ==
== Proof ==
Suppose $a, b \in \Z$ and $a \lor b \ne 0$.
From the Division Theorem, $a = q b + r$ where $0 \le r < \size b$.
From GCD with Remainder, the GCD of $a$ and $b$ is also the GCD of $b$ and $r$.
Therefore, we may search instead for $\gcd \set {b, r}$.
Since $\size r < \size b$ and $b \in \Z$, we will reach $r = 0$ after finitely many steps.
At this point, $\gcd \set {r, 0} = r$ from GCD with Zero.
== Sources ==
* : Chapter $3$: The Integers: $\S 11$. Highest Common Factor
Category:Euclidean Algorithm
Euclidean Algorithm/Proof 2

== Algorithm ==
== Proof ==
Suppose $a, b \in \Z$ and $a \lor b \ne 0$.
Let $d = \gcd \set {a, b}$.
By definition of common divisor:
:$d \divides a$
and:
:$d \divides b$
Hence from Common Divisor Divides Integer Combination:
:$d \divides \paren {a - q b}$
That is:
:$d \divides r$
Thus $d$ is a common divisor of $b$ and $r$.
Let $c$ be an arbitrary common divisor of $b$ and $r$.
Then:
:$c \divides \paren {q b + r}$
That is:
:$c \divides a$
Thus $c$ is a common divisor of $a$ and $b$.
Hence by definition of GCD:
:$c \le d$
Hence, again by definition of GCD:
$d = \gcd \set {b, r}$
Then we work down the system of equations:
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm
Category:Euclidean Algorithm