Thread: Greatest common divisor

1. Greatest common divisor

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

2. 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

3. Here are my attempts

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

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

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

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

Thus, $\displaystyle \gcd (a,b)$ is a divisor of both $\displaystyle a$ and $\displaystyle 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 $\displaystyle p \mid (a+b)$ and $\displaystyle p \mid (a-b)$ where $\displaystyle p$ is prime. This means that: $\displaystyle p \mid (a+b + (a-b) \Leftrightarrow p \mid 2a$. Similarly, we get $\displaystyle 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 $\displaystyle \gcd (a^n, b^n) > 1$. This means that there exists a prime $\displaystyle p$ such that $\displaystyle p \mid a^n$ and $\displaystyle p \mid b^n$. Can you arrive at a contradiction? (Remember, if $\displaystyle p \mid mn$, then either $\displaystyle p \mid m$ or $\displaystyle 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 $\displaystyle a = p_1^{e_1}p_2^{e_2}\cdots p_n^{e_n}$ and $\displaystyle b = p_1^{f_1}p_2^{f_2}\cdots p_n^{f_n}$ where $\displaystyle e_j, f_j$ may equal to 0.

By definition, we have: $\displaystyle \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: $\displaystyle \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.