## Wednesday, April 16, 2014

### Lattice Rationals, 3 of 10

GCF, LCM, compensators and the Euclidean Algorithm

Here are some rules uniting addition with gcf, lcm, and the compensator:
gcf(a,b)  =  gcf(a-b, b)  =  gcf(a+b, b)  =  gcf(a+nb, b)  for any integer n.
Define (a mod b) to be the remainder of a when divided by b. (A mod B)  equals A+nB for some n; therefore:
gcf(a, b) = gcf( a mod b, b)  =  gcf(a, b mod a)
This, along with the rule:
gcf(a,0)  =  gcf(0,a)  =  a
implies the Euclidean algorithm. For instance:
gcf(52,20)  =  gcf(12,20)  =  gcf(12,8)  =  gcf(4,8)  =  gcf(4,0)  =  4
Modulation ping-pongs across gcf until resolution. From these rules:
Lcm(a,b)   =    a*b/gcf(a,b)
(a;b)          =    a / gcf(a,b)
we can derive these Euclidean-algorithm-like rules:
lcm(a,b)    =     (a/(a mod b)) * lcm(a mod b, b)       =     (b/(b mod a)) * lcm(a, b mod a)
lcm(ab,a)    =    lcm(a,ab)    =    ab
(a;b)            =     (a ; b mod a)   =   (a/(a mod b)) * (a mod b ; b)
(a;ab)          =     1
(ab;b)          =    a
Therefore, for instance:
Lcm(52,20) = (52/12)*lcm(12,20) = (52/12)*(20/8)*lcm(12,8) = (52/12)*(20/8)*(12/4)*lcm(4,8)  =   (52/12)*(20/8)*(12/4)*8  =   260
(52;20)  =  (52/12)*(12;20) =  (52/12)*(12;8) =  (52/12)*(12/4)*(4;8) =  (52/12)*(12/4)*1  =  13
(20;52)  =  (20;12)  =  (20/8)*(8;12) =  (20/8)*(8;4) = (20/8)*2   =  5