Proofs Involving Greatest Common Divisors

[Ateowa]

I'm not sure if it goes here or the section beyond calculus, so I'm just putting it here because it doesn't involve any calculus.

Homework Statement

Suppose that (a,b)=1 [Greatest Common Divisor=1] and (a,c)=1. Does (bc, a)=1?

Homework Equations

(a,b)=d=au+bv, where u and v are integers and d is the greatest common divisor of a and b.

The Attempt at a Solution

OK, so I'm taking both of the facts I already know, that (a,b)=1 and (a,c)=1 and turning them into a useful equation:
1=au+bv, and 1=am+cn where u,v,m, and n are all integers. I know that my end goal is to find a(q)+bc(r)=1 However, I can't seem to find a way to get there. The closest I've gotten is by setting the two equal:
au+bv=am+cn, and them multiplying by bc to get:
abcu-abcm=bc²n+b²cv
Then I factor and move them to the same side to find:
0=a(bcm-bcu)+bc(cn+bv)
Which is not what I need.

Am I going about this the completely wrong way? I have a feeling I'm mistaking a basic part of the proof, as a similar problem is also giving me trouble.

 

[HallsofIvy]

Just think about prime factors. Do a and b have any prime factors in common? Do a and c have any prime factors in common? What does that tell you about a and bc?

 

[Ateowa]

I know that they all share no prime factors. If they did, they would have a GCD other than one. However, I don't know how to incorporate that (Or much at all) into a proof. I'm having a bit of trouble because I skipped into this course without taking the pre-req where you learn a lot of proof techniques. I ordered a book the professor recommended but I haven't gotten it yet... I feel like that's what I'm missing, but maybe not?

 

[Focus]

Try a contradiction, let a number k (not 1) divide bc and a, and let (a,b)=1 and (a,c)=1. Without loss of generality let k be prime. Use the definition of a prime (if a prime divides bc then it divides b or c). You should be able to derive a contradiction from that easily.

 

[snipez90]

The answer is yes and to show it by using the fact that the gcd of two numbers can be represented as a linear combination of the numbers, the key was to multiply instead of setting them equal (the hint is that 1*1 = 1). But that's not very elegant so we can be more clear.

From the given info, we have that ax_0 + by_0 = 1 = ax_1 + cy_1. Thus (by_0)(cy_1) = (1 - ax_0)(1 - ax_1) = 1 - ax_2 where x_2 = x_1 + x_0 - ax_0x_1. Rearranging, we have bcy_0y_1 + ax_2 = 1. Hence, (bc, a) = 1.

 

[HallsofIvy]

I know that they all share no prime factors. If they did, they would have a GCD other than one. However, I don't know how to incorporate that (Or much at all) into a proof. I'm having a bit of trouble because I skipped into this course without taking the pre-req where you learn a lot of proof techniques. I ordered a book the professor recommended but I haven't gotten it yet... I feel like that's what I'm missing, but maybe not?

Any integer has a unique prime factorization. If a and b have gcd 1, then they have no prime factors in common- if they did their gcd would be be divisible by those prime factors. Similarly a and c have no prime factors in common. But bc is just the product of the prime factors of b and c. None of the prime factors of bc can divide a because none of the prime factors of b and c separately did.

 

[Ateowa]

Thanks guys! I really appreciate your help.