Greatest common divisor

**Cabouli** · March 15th 2009, 09:50 PM

Some help with these would be appreciated

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

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

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

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

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

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

**Jhevon** · March 15th 2009, 10:02 PM

Originally Posted by Cabouli

Some help with these would be appreciated

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

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

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

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

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

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

please show what you have tried or where you are getting stuck. this seems like you just want someone to do your homework for you

**Cabouli** · March 17th 2009, 06:25 PM

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

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?

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?

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

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

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.

Please any help would be appreciated.

Also I am too old to still be doing homework but I do voluntary tutoring for disadvantaged kids. This is the first time I have come across a student needing help with number theory.

Cheers
Cabouli

**o_O** · March 17th 2009, 07:16 PM

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: $\gcd(a,b) = 1 \ \Rightarrow \ ax + by = 1$

Multiply both sides by $c$ to get: $acx + bcy = c$

Now, since $\gcd(a,b) \mid acx$ and $\gcd(a,b) \mid bcy$ , then $\gcd(a,b) \mid c$ (Why?).

Thus, $\gcd (a,b)$ is a divisor of both $a$ and $c$ . What can you conclude?

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.

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?

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

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 $p \mid (a+b)$ and $p \mid (a-b)$ where $p$ is prime. This means that: $p \mid (a+b + (a-b) \Leftrightarrow p \mid 2a$ . Similarly, we get $p \mid 2b$ .

Can you finish off?

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 $\gcd (a^n, b^n) > 1$ . This means that there exists a prime $p$ such that $p \mid a^n$ and $p \mid b^n$ . Can you arrive at a contradiction? (Remember, if $p \mid mn$ , then either $p \mid m$ or $p \mid n$ )

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 $a = p_1^{e_1}p_2^{e_2}\cdots p_n^{e_n}$ and $b = p_1^{f_1}p_2^{f_2}\cdots p_n^{f_n}$ where $e_j, f_j$ may equal to 0.

By definition, we have: $\gcd (a,b) = p_1^{\min (e_1, f_1)}p_2^{\min (e_2, f_2)}\cdots p_n^{\min (e_n, f_n)}$

and: $\text{lcm} (a,b) = p_1^{\max (e_1, f_1)}p_2^{\max (e_2, f_2)}\cdots p_n^{\max (e_n, f_n)}$

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

Thread: Greatest common divisor

LinkBack

Thread Tools

Display

Greatest common divisor

Here are my attempts

Similar Math Help Forum Discussions

Greatest Common Divisor of (9m+8, 6m+5)

[SOLVED] Least common multiple - Greatest common divisor

Greatest Common Divisor.

greatest common divisor

greatest common divisor

Search Tags