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
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
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?
Sure does.
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?
Although you would probably want to say more as to why it is 'clear' that this is the case.
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?
Suppose and where is prime. This means that: . Similarly, we get .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
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 . This means that there exists a prime such that and . Can you arrive at a contradiction? (Remember, if , then either or )
Can't quite read what you have there but I'm guessing you're going down the prime factorization approach.
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.
So, let and where may equal to 0.
By definition, we have:
and:
Multiply them both together and it should be clear from there.