Tuesday 17 May 2011

LCM and GCD analysis

Recall:
Fundamental theorem of arithemetics:
Every positive integers > 1 can be written in unique product of primes.

Starting from the fundamental:
Assume:
x = p_1 ^ (x_1) * p_2 ^ (x_2) *... p_n ^ (x_n)
y = p_k ^ (y_k) * p_(k+1) ^ (y_(k+1)) * ... p_z ^ (y_z)

This is the prime factorization to two positive integers x and y, where 1 =< k =< n+1 =< z.

Define sequence a_r = max(x_r, y_r) and b_r = min (x_r, y_r),
Now we say the greatest common divisor gcd(x,y), or simply (x,y), is given by:
(x,y) = p_k^(b_k) * .... * p_n ^(b_k)
If k = n+1, i.e., they don't have common prime divisors, (x,y) = 1, we can x and y is co-prime to each other.

Define the least common multiple lcm[x,y], or simply [x,y], given by
[x,y] = p_1 ^ (a_1) * ... * p_z ^(a_z).

Now we make some notation:
x = w_x * k_xy
y = w_y * k_xy
w_i are co-prime each other.
[x,y] = w_x * w_y * k_xy
(x,y) = k_xy
You can find that xy = [x,y](x,y).

Simplify this once more: when we prime factorize all elements into co-prime factors, the lcm and gcd function have made it as cyclic function.
Denote the product of all w_i = k_1
The product of all k_ab (gcd between two elements) = k_2
The product of all k_abc (gcd between three elements) = k_3, etc.

Then we can generalize that the lcm all n elements = product of all k_i while the gcd = k_n.

Now let's generalize our result to 3 elements.

Lemma : (b,c) / (a,b,c) = k_bc, it can be solved by set theory.
(b,c) = b ∩ c, (a,b,c) = a ∩ b ∩ c
Then (b,c)/(a,b,c) = (b∩c) / (a∩b∩c) = (b∩c)/a, which is "common factor of b and c but NOT a".

Is the identities xy = [x,y](x,y) applicable to 3 elements? Let see:
Using the notation {a_1, a_2, ...a_n} = k_1 ^(a_1) * k_2^(a_2) *... * k_n^(a_n)
abc = {1,2,3}
[a,b,c] = {1,1,1}
(a,b,c) = {0,0,1}
cyclic product of [a,b] = {2,3,3}
cyclic product of (a,b) = {0,1,3}
abc is certainly unequal to [a,b,c](a,b,c)
However we can see the identity that abc[a,b,c] = [a,b][b,c][c,a](a,b,c).

Let's have a classical NT problem:
Prove the identity [a,b,c]^2(a,b)(b,c)(c,a) = (a,b,c)^2[a,b][b,c][c,a]

It can be proved very easily by degree analysis:
Power to the notation = multiply the number in the notation
LHS = {1,1,1}^2{0,1,3} = {2,3,5}
RHS = {0,0,1}^2{2,3,3} = {2,3,5}
So it's true.

How can we solve this by means of prime factorizing?

Note that cyc. prod. of [a,b] = (abc)^2 / cyc. prod. of (a,b)

Also note the pemuability of the gcd and lcm function: [a,b,c] = [[a,b],c] and (a,b,c) = ((a,b),c)
[a,b,c] = [[a,b],c] = [a,b]c/([a,b],c) = abc/([a,b],c)(a,b)

[a,b,c]^2(a,b)(b,c)(c,a) = (a,b,c)^2[a,b][b,c][c,a]

<=>
(abc)^2(a,b)^2(b,c)^2(c,a)^2 = (a,b,c)^2(abc)^2([a,b],c)^2(a,b)^2

<=>
(b,c)^2 (c,a)^2 = (a,b,c)^2 ([a,b],c)^2

Now we use prime factorizing method:

k_bc ^2  k_ac ^2 k_3 ^2 = (w_a*w_b*k_ab*k_ac*k_bc*k_abc, w_c*k_ac*k_bc*k_abc)^2
=k_bc ^2  k_ac ^2 k_3 ^2

Or, bet set theory on ([a,b],c):
(a U b) ∩ c
= (a∩c) U (b∩c)
=> k_ac, k_bc and k_abc

Q.E.D..

Exercise:
1) Generalize the cases of n numbers

No comments:

Post a Comment