the_euclidean_algorithm

introduction

The euclidean algorithm helps find the gcd in a way that is a lot easier than using other methods, like the factor tree method, or the common divisor method, it is also more “economical” that is to say, it doesn’t require much computational power, for both humans and computers. The exact time-complexity, of the algorithm is actually unknown, see big_o_notation_cs

intuition

Bezouts_lemma

This is simply a fancy way of saying, the gcd(a, b) is in the form au + by u,v being (non-unique) integers.

Steps

as seen in taocp

  1. [Find remainder.] Divide m by n and let r be the remainder. (We will have 0 ≤ r < n
  2. [Is it zero?] If r = 0, the algorithm terminates; n is the gcd
  3. [Interchange] Set m ← n, n ← r and go back to step 1.

rigour

Using computational_method Let Q be the set of all singletons (n), all ordered pairs (m, n) and all quadruples (m, n, r, 1), (m, n, r, 2) and (m, n, p, 3), where m, n and p are positive integers and r is a nonnegative integer. Let I be the subset of all pairs (m, n) and let Ω be the subset of all singletons (n). Let f be defined as follows.

f(m, n) = (m, n, 0, 1); f(n) = (n)

f(m, n, r, 1) = (m, n,  remainder of m divided by n, 2);

f(m, n, r, 2) = (n) if r = 0, (m, n, r) otherwise :~ check if r = 0 and if we are done

f(m, n, p, 3) = (n, p, p, 1) :~ replace n with the remainder r (or in this case p)

Worked example using rigour

  1. find gcd(52, 21) using the rigourous definition of the euclidean algorithm. $m `:=` 52$ and $n `:=` 21$. f((52, 21)) = (52, 21, 0, 1) f((52, 21, 0, 1)) = (52, 21, 10, 2) f((52, 21, 10, 2)) = (52, 21, 10, 3)

f((52, 21, 10, 3)) = (21, 10, 10, 1) f((21, 10, 10, 1)) = (21, 10, 1, 2) f((21, 10, 1, 2)) = (21, 10, 1, 3) f((21, 10, 1, 3)) = (21, 1, 1, 3) f((21, 1, 1, 3)) = (21, 1, 0, 3) f((21, 1, 0, 3)) = (1)

We also need the restriction of finiteness, we need restrictions on the [[computational_method___20241013_184605|quadruple]]. Let A be a finite et of letters, and let A* be the set of all strings on A, meaning the set of all ordered sequences, or combinations of letters x1x2…xn, with n ≥ 0 and xj ∈ A for all 1 ≤ j ≤ n. We want to encode the states of computation above so that they are represented by strings of A TODO

exam clinic

See “Find gcd(132, 84).” in [[gcd]]

resources

tags :math:introduction_to_number_theory:introduction_to_abstract_algebra:taocp:

extended_euclidean_algorithm

backlinks