Quote:

Originally Posted by

**Cabouli** 1. Prove that if gcd(a,b)=1 and gcd(a,c)=1 then gcd(a,bc)=1

gcd(a,b)=1 then ax+by=1

gcd(a,c)=1 then ax+cy=1

let gcd(a,bc)=d then ax+bcy=d

I cannot see how to proceed

So we have:

Multiply both sides by to get:

Now, since and , then (Why?).

Thus, is a divisor of both and . What can you conclude?

Quote:

2. Prove that if a and b are relatively prime and c|a, then c and b are relatively prime

gcd(a,b)=1 ax+by=1

c|a therefore a=cm ,m an integer

therefore cmx+by=1

so c(mx)+by=1

therefore gcd(c,b)=1

Does this work?

Sure does.

Quote:

3. Prove that if a is odd, then 24|a(a^2-1)

sufficient to show RHS is divisible by 3, 2 and 4

let a=2k+1 since it is odd

a(a^2-1)=2k(2k+1)(2k+2)

this is clearly divisible by 2, 3 and 4

Is that idea sufficient?

(Yes) Although you would probably want to say more as to why it is 'clear' that this is the case.

Quote:

4. Prove that if a and b are relatively prime, then gcd(a+b,a-b)=1 or 2

gcd(a,b)=1 and ax+by=1

let gcd(a+b,a-b)=d so (a+b)x+(a-b)y=d so d|(a+b) and d|(a-b)

I can see I need d|2a and d|2b but can't see how to get there

Suppose and where is prime. This means that: . Similarly, we get .

Can you finish off?

Quote:

5. Prove that, if a and b are relatively prime, then so are a^n and B^n, where a and b and n are positive integers

gcd(a,b)=1 and ax+by=1

let gcd(a^n,b^n)=d so a^nx+b^ny=d and a^n=md b^n=pd

again don't know where to proceed

Suppose . This means that there exists a prime such that and . Can you arrive at a contradiction? (Remember, if , then either or )

Quote:

6. Prove that lcm(a,b)xgcd(a,b)=ab

If a=mnp.. m,n,p,... are prime and b=efg.. e,f,g,... are prime

then lcm(a,b)=mnp...efg... assuming none of mnp... and efg... are common

If any are common they will not be in the lcm(a,b)

gcm(a,b)= common elements from mnp.... and efg.... if none then gcm(a,b)=1

aXb=mnp...efg...

gcd(a,b)Xlcm(a,b)=mnp...efg... from above

I think I have the right idea but a messy approach to showing it.

Can't quite read what you have there but I'm guessing you're going down the prime factorization approach.

So, let and where may equal to 0.

By definition, we have:

and:

Multiply them both together and it should be clear from there.