Given any positive integer d and any integer a, there exist unique integers q and r such that:
(A) a = qd + r and
(B) 0 ≤ r < d
----------------------------------------------------------------------------------------------------------------------------------------------
Proof
Prove existence of q, r:
Rearranging (A): and substituting in (B)
(1) 0 ≤ a - qd < d
(2) Let S be the set S = {a - nd : n ∈ ℤ} (ℤ is the set of all integers)
(2a) S = { ... a - 3d, a - 2d, a - d, a, a + d, a + 2d, a + 3d ...}
(3) If a is non-negative, then if n = 0 : a-nd = a ≥ 0, and S contains at least 1 integer ≥ 0
(4) If a is negative, then if n = a : a-nd = a - ad ≥ 0, and S contains at least 1 integer ≥ 0
The existence of q and of r ≥ 0 has been proven
(5) Since at least 1 member of S is non-negative, by observing (2a) it can be noted that there is a member of S, a-qd, which is the least non-negative integer. (Well-ordering Principle)
(5a) a - (q + 1)d < 0, a - qd ≥ 0
(6) a - qd must be < d, because, if not:
(7) a - qd ≥ d,
(8) a - (q + 1)d ≥ 0, and a-qd is not the smallest member of S
The existence of 0 ≤ r < d has been proven
----------------------------------------------------------------------------------------------------------------------------------------------
Prove uniqueness of q, r:
Since r is uniquely determined by q or vice-versa by (A), the uniqueness of only one of them requires proof
(9) Assume there exist 2 sets of solutions for (A) and (B), (q, r) and (q', r')
(10) Then (a - qd) - (a - q'd) = (q' - q)d
(11) Applying limits in (B), -d < (q' - q)d < +d
(12) Dividing by d, -1 < (q' - q) < +1
(13) Since q - q' is an integer, and the only integer in the solution range is 0, q = q' (all solutions are the same, i.e., the solution is unique)
(14) It follows automatically that r = a - qd is unique.

Given a, d as in the Division Theorem, if r is found to be 0, then the following equivalent statements can be made:
d is a divisor of a
d divides a
d is a factor of a
a is divisible by d
Symbolic representation: d|a
Definition: d|a ⇔ a = d*q for some q ∈ ℤ
Axiom: ∀a (a ∈ ℤ, a ≠ 0): ±1|a
Axiom: ∀a (a∈ ℤ): 0∤a
Corollary: d ≤ |a|.

Definition: If s|p and s|q, then s is a common divisor of p, q.
Proposition: for p, q∈ ℤ, not both 0, there is a greatest common divisor of p, q, gcd(p,q) ≥ 1.
Proof:
Without loss of generality, let p ≠ 0
Let S be the set of all common divisors of p, q.
1|p and 1|q, so 1 ∈ S and S ≠ ∅.
Let s|p, then p=s*k for some k ∈ ℤ. Then s ≤ |p| and S has an upper bound of |p|.
Since 1 ∈ S and S has an upper bound, ∃gcd(p,q) : gcd(p,q) ≥ 1.
Definition: A pair of integers are coprime, or relatively prime if their greatest common denominator is 1.

0.	a = q0d + r0	q0 = floor[a/d]
1.	d = q1r0 + r1	q1 = floor[d/r0]
2.	r0 = q2r1 + r2	q2 = floor[r0/r1]
3.	r1 = q3r2 + r3	q3 = floor[r1/r2]
⋮	⋮	⋮
n-1.	rn-3 = qn-1rn-2 + rn-1	qn-1 = floor[rn-3/rn-2]
n.	rn-2 = qnrn-1 + 0	qn = floor[rn-2/rn-1]

Consider the following sequence of divisions:
By the Division Theorem, for every k, q_k and r_k exist and are unique.
Also by the Division Theorem, from the left hand side of the divisions, r₀ < d, r₁ < r₀, r₂ < r₁, ..., r_n-2 < r_n-1
Since each r_k+1 < r_k, eventually one of them will be 0. (they form a decreasing sequence of nonnegative integers). It follows that the algorithm must terminate.
Let r_n-2 be the last nonzero r.
In the last equation, r_n-2|r_n-1
In the prior equation, since r_n-2 divides both terms of the right hand side, r_n-2|r_n-3
Proceeding by induction, r_n-2|d and r_n-2|a.
Therefore, r_n-2 is a common divisor of a, d.
----------------------------------------------------------------------------------------------------------------------------------------------
To show r_n-2 is the greatest common divisor of a, d, let R be an arbitrary common divisor of a, d.
Rewrite the terms of the division sequence as a-q₀d = r₀, d-q₁r₀ = r₁, r₀-q₂r₁ = r₂, ... , r_n-2-q_nr_n-1 = 0
Since R divides both left hand terms of the first equation of the rearranged sequence (a and -q₀d), R|r₀
Then, since R divides both left terms of the second equation of the rearranged sequence (d and -q₁r₀), R|r₁
Proceeding by induction, R divides r_n-2 and -q_nr_n-1, so R|r_n-2
But if R|r_n-2, then r_n-2 ≥ R and r_n-2 is the greatest common divisor.

Definition: A linear combination of integers p, q is any integer of the form mp + nq where m, n∈ ℤ
If s|p and s|q, then s|(mp + nq) for every p, q ∈ ℤ
Proof:
From the Divisibility Relation, ∃k ∈ ℤ : p = s * k, ∃k' ∈ ℤ : q = s * k'.
Then mp + nq = msk + nsk' = s * (mk + nk').
Since (mk + nk') ∈ ℤ, s|(mp + nq).
Any common divisor of 2 integers divides any linear combination of the integers

For any integers p, q ∈ ℤ, not both 0, the least positive linear combination of p, q is their greatest common denominator.
∃m, n ∈ ℤ : mp + nq = gcd(p, q)
Proof:
Let S be the set of all positive linear combinations of p and q:
S = {x ∈ ℤ; x > 0 : x = mp + nq; m, n ∈ ℤ}
Lemma 1: Establish S ≠ ∅:
p>0: 1*p + 0*q > 0
p<0: (-1)*p + 0*q > 0
q>0: 0*p + 1*q > 0
q<0: 0*p + (-1)*q > 0
Since both p and q cannot both be 0, 1 of the above 4 conditions is true and S ≠ ∅.
Lemma 2: Establish S has a least positive member:
By definition, S is bounded below by 0 and by Lemma 1, S ≠ ∅.

Let s be the least positive linear combination of p, q.
Then, by CDLC, gcd(p,q)|s.
By the Divisibility Relation, gcd(p,q) ≤ s.
But, by definition, s is the least positive linear combination of p, q.
Therefore, gcd(p,q) = s.

Definition: The residue, r of an integer is the result of a modulo operation, (r = a mod m)
The residue, r, of a, modulo m, is that value of r such that:
(a) a = q * m + r for some q, and
(b) 0 ≤ r < m
Definition: 2 integers, d, e, are congruent modulo a if a|(d-e); that is, (d - e) = k * a for some k ∈ ℤ (Divisibility Relationship)
Symbolically, d ≡ e (mod a)
Integers are congruent if their residues are equal. (d mod a) = (e mod a)
d ≡ e (mod a) ⇔ d, e, belong to the same congruence class (mod a).
The congruence classes mod a are the members of the set {0, 1, 2, ..., a-1}
Corollary: d ≡ 0 (mod a) if and only if d|a, since (d - 0 = d = a * k and a|a*k)

Theorem: If d ≡ p (mod a) and e ≡ q (mod a) then d + e ≡ p + q (mod a)
Proof:
By the definition of congruence, a|(d - p) and a|(e - q)
Therefore, by CLDC, a|(d - p + e - q)
Rearranging terms, a|((d + e) - (p + q))
And (d + e) ≡ (p + q) (mod a)
The additive identity for modular arithmetic is any member of the congruence class 0 (mod a):
d + 0 ≡ d (mod a)
Corollary: if d ≡ 0 (mod a) and e ≡ q (mod a) then (d * k + e) ≡ q (mod a) for all k ∈ ℤ

Theorem: If d ≡ p (mod a) and e ≡ q (mod a) then d * e ≡ p * q (mod a)
Proof:
By the definition of congruence, a|(d - p) and a|(e - q)
And (d - p) = j*a, (e - q) = k*a for some j, k ∈ ℤ
Therefore, d = p + j*a and e = q + k*a
Multiplying, d*e = p*q + p*k*a +q*j*a + j*k*a
d*e - p*q = a*(p*k + q*j + j*k*a)
Since a divides the right side of the equation, it divides the left side.
a|(d*e - p*q), therefore, d * e ≡ p * q (mod a)

Definition: The modular (multiplicative) inverse of d (mod a) is that integer e such that d*e ≡ 1 (mod a)
Theorem: d has a modular inverse mod a if and only if gcd(a,d) = 1
Proof:
Let e be a modular inverse of d (mod a). Then d*e ≡ 1 (mod a)
From a property of congruence, a*k ≡ 0 (mod a) for all k ∈ ℤ
Performing modular addition on the above 2 terms, d*e + a*k ≡ 1 (mod a) for all k ∈ ℤ
From the definition of congruence, d*e + k*a - 1 = k'*a for some k' ∈ ℤ
Rearranging terms, d*e + (k-k')*a = 1
d*e + (k-k')*a, equalling 1, is the least linear combination of a and d, and thus is gcd(a,d) (Bezout identity).
And the existence of e, which can thus be calculated from the above, has been proven.
Conversely, let gcd(a,d) = 1
Then k*a + d*e = 1 for some k, e ∈ ℤ (Bezout identity).
Reducing by mod a, 0 + d*e ≡ 1 (mod a)
And d has a modular inverse e (mod a)

Step	rstep =	a * xstep + d * ystep
0.	r0 = a - d * q0	= a * (1) + d * (-q0)
1.	r1 = d - r0 * q1 = d - a - dq0q1	= a * (-q1) + b * (1 +q0q1)
2.	r2 = r0 - r1 * q2 = a - dq0 + aq1q2 - dq2(1 +q0q1)	= a * (1 + q1q2) + d *[(-q0) - q2(1 + q0q1)]
⋮	⋮	⋮
n-1	rn-1 = rn-3 - rn-2qn-1	= a * xn-1 + d * yn-1
n	0 = rn-2 - rn-1qn

Rewrite the terms of the Euclidean Algorithm as to the right:
Note that all terms can all be written as a linear combination of a and d.
Regard these linear combinations as linear Diophantine equations of the form ax_k + dy_k = r_k,
where k refers to the step (0, 1, 2, 3...) of the algorithm.
By inspection:
x₂ = 1 + q₁q₂ = x₀ - x₁ * q₂
y₂ = -q₀ - q₂(1 + q₀q₁) = y₀ - y₁ * q₂
By the rules of the algorithm, r_k = r_k-2 - r_k-1 * q_k .
Sustituting from the right-hand column, r_k = ax_k-2 + dy_k-2 - ax_k-1q_k - dy_k-1q_k
= a(x_k-2-x_k-1q_k) + d(y_k-2-y_k-1q_k)
r₂ = r₀ - r₁ * q₂ = ax₀ + dy₀ - ax₁q₂ - dy₁q₂ = a(x₀ - x₁q₂) + d(y₀ - y₁q₂) by direct substitution,
and the algorithm is satisfied for step 2.
It follows by induction that, for any k ≥ 2, x_k = x_k-2 - x_k-1q_k, y_k = y_k-2 - y_k-1q_k for any algorithm step.
Since r_n-1 is the least positive r, it is the least positive linear combination of a, d and thus gcd(a,d) (Bezout identity).
By the properties of modular addition, r_n-1 = d * y_n-1 + a * x_n-1 and d * y_n-1 are congruent modulo a.
Therefore, r_n-1 ≡ dy_n-1 (mod a)
If r_n-1 = 1, then a and d are coprime.
And y_n-1 is the modular inverse of d (mod a)