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.

1. The problem statement, all variables and given/known data
Suppose that (a,b)=1 [Greatest Common Divisor=1] and (a,c)=1. Does (bc, a)=1?


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


3. 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=bc2n+b2cv
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.