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

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment