Need more help
Doug Magnoli
a = f1*f2*f3...*fn*g1*g2...*gi
b = f1*f2*...*fn *h1*h2*...*hj
i.e., the f's are the factors that a and b have in common. Notice that the
f's, g's, and h's are not unique, i.e., we can have f1=f2=g1, but in no case
does gk = hl, since those two sets don't overlap.
Therefore GCD(a,b) = f1*f2...*fn
[Note that:
i) f1*f2*...*fn divides both a and b
ii) any divisor of both a and b divides f1*f2*...*fn ]
c = f1*f2*..*fm*j1*j2*...*jk
where the f's are the factors that c has in common with a and b, notice that
m<=n but m can't be greater than n. The j's are the other factors of c, some
of which may be the same as some of the g's or h's.
GCD(a,b,c) = f1*f2*...*fm
GCD(GCD(a,b),c) = f1*f2*...*fm
QED.
-------------------
Again, GCD(a,b) = f1*f2*...*fn
Notice that a+b = f1*f2*...*fn*(g1*g2*...*gi + h1*h2*...*hj),
so a+b also includes the factor f1*f2*...*fn
LCM(a,b) = f1*f2*...*fn*g1*g2*...*gi*h1*h2*...*hj
[Note that:
i) LCM(a,b) is a multiple of both a and b
ii) any multiple of a and b is also a multiple of LCM(a,b) ]
GCD(a+b, LCM(a,b)) = GCD (f1*f2*...*fn*(g1...+ h1...), f1*f2*...*fn*g1...*h1)
= f1*f2*...*fn
Since all the g's and h's are prime, no combination of (g1*g2*..*gi +
h1*h2*...*hj) can share any factors with (g1*g2*...*gi*h1*h2...*hj)
QED
-------
LCM(a,b) = f1*f2*...*fn*g1*g2*...*gi*h1*h2*...*hj
GCD(a,b) = f1*f2*...*fn
LCM(a,b)*GCD(a,b) = (f1*f2*...*fn)^2*g1*...*gi*h1*...*hj
= [(f1*f2*...*fn)*g1*...*gi] * [(f1*f2*...*fn) * h1*h2*...*hj)]
= a*b
QED
-------------
Johann Joubert wrote:
> Thanks guys, for all the assistance you've given me. Anyways, I have two
> questions
>
> 1) If a, b, c (member of integer system), the nonnegative integer d is
> called the GCD of a, b, c, and denoted by GCD(a, b, c) if
> i) d divides a, b, and c
> ii) any divisor of a, b, and c also divides d
>
> Prove that GCD(a, b, c) = GCD(a, GCD(b,c))
>
> ===================================
>
> 2) Either prove, or disprove with a contradition that GCD(a, b) = GCD(a + b,
> LCM(a, b))
>
> The TA (teacher assistant) said to use the following to help:
>
> A nonnegative integer e is called the least common multiple of the integers
> a and b if
> i) e is a multiple of a and b
> ii) any multiple of a and b is also a multiple of e
>
> (question part now, which I don't need to do, but could use help
> with...) --If a = p1^a1...pn^an and b = p1^b1...pn^bn, show that e =
> p1^e1..pn^e1 where ei = max(ai,bi) for i = 1, ..., n. Also show that for any
> positive integers a and b
>
> ab = LCM(a,b) * GCD(a,b)
>
> This last question part is not important, but questions 1 and 2 is bothering
> me :) Thanks for any suggestions, solutions, hints, tips....
Stuart Gall
> called the GCD of a, b, c, and denoted by GCD(a, b, c) if
> i) d divides a, b, and c
> ii) any divisor of a, b, and c also divides d
>
> Prove that GCD(a, b, c) = GCD(a, GCD(b,c))
| means divides.
x = hcf(a,b,c) => x|a and x|b and x|c
y = hcf(a,hcf(b,c)) => y|a and y|b and y |c (because y | hcf(b,c))
so y is a common factor of a,b,c so y|x (y is hcf and hcf is divisible by
all common factors)
x is a common factor of a,b,c so x|y
y|x and x|y => y=x
It is interesting to do it this way we did prove hcf(hcf(a,b),c) =
hcf(a,hcf(b,c)) and then define hcf(a,b,c) to be that.
--
Stuart Gall
------------------------------------------------
This message is not provable.
Stuart Gall
Just realised this is slightly protracted logic
y|x and x|y => |y| = |x|
but since hcf's are always positive y=x
Bill Dubuque
>
> Prove or disprove that gcd(A, B) = gcd(A + B, lcm(A, B))
(a+b, [a,b]) = [(a+b,a), (a+b,b)] since gcd distributes over lcm
= [(a,b), (a,b)]
= (a,b). QED
Another approach: divide through by g = (A,B), thus simplifying to:
1 = (a+b, [a,b]) if (a,b) = 1, here a = A/g, b = B/g
Proof: = (a+b, ab) since (a,b) = 1
= (a+b, a(a+b,b)) since (x, y z) = (x, y (x,z))
= (a+b, a) since (a+b,b) = (a,b) = 1
= 1. since (a+b,a) = (b,a) = 1. QED
-Bill Dubuque