Abstract/Modern Algebra - Relatively Prime

[b0it0i]

Homework Statement

Note: gcd(a,b) = the greatest common divisor of integers a and b (not both 0)

suppose that (a,b)=1 and (a,c)=1
that is, a and b are relatively prime, and a and c are relatively prime

Is the following statement true? if so prove it

(bc,a)=1

I computed a few examples, and i claim that it is true

Homework Equations

theorem: linear combination of gcd

if d = gcd(a,b)

then there exists integers u and v such that

d = au + bv

corollary:

(a,b)=1 if and only if 1 = au +bv

The Attempt at a Solution

From the corollary stated above, i claimed that we must show that

1 = (bc)u + (a)v

thus we must find integers u and v that satisfy the statement above

since (a,b) = 1 and (a,c) = 1, I used that corollary again,

1 = ax + by and 1 = af + cg
for some integers x,y,f, and g

and i am stuck at this point. I have no idea what i can do with these statements

I'm not sure if my approach is correct. But in the textbook, and in my class notes there are no examples showing how we can prove two integers are relatively prime. So i assumed this is how we approach the problem

the only other thing we have learned so far, is the divisibility algorithm, and division

any hints, guidance, would be appreciated. thanks

edit: possible solution

i see, that's the final step missing

i said since
(a,b) = 1 --> 1 = ax + by
(a,c) = 1 --> 1 = af + cg
By Theorem, x,y,f, and g exist

1 = 1.1 = (ax+by)(af+cg) = a^2xf + axcg + aabyf + bycg
= a(axf + xcg + byf) + bc(yg)
therefore let

u = axf + xcg + byf
and
v = yg

and since, all the "letters" used exist and are integers, they satisfy the domain, and the proposition

is that correct? even though "u" is messy, it doesn't matter right? because those integers exist (by theorem)

 

[Dick]

The easiest way to prove it is to use unique prime factorization. If gcd(a,b)=1 then a and b have no common prime factors. Ditto for a and c. The set of prime factors of bc is the union of the set of prime factors of b and c. If a has none in common with b and none in common with c, doesn't that prove it has none in common with bc?

 

[b0it0i]

i see what you're saying and it makes sense

but we have not gone over that topic in class, and that was not introduced in any of the proofs in the book

even though that is the easiest way, is there another method to do so?

actually i skimmed through the book, and i see it's in the upcoming section

i doubt that my professor would allow me to use an idea from a chapter we will be discussing later

 

[b0it0i]

what about this other approach: using the definition of GCD

d=gcd(a,b) if d satisfies the 2 following conditions

1) d|a and d|b
2) IF c|a and c|b --> c less than equal to d

1) is clearly true, since 1 divides any integer
2) i guess the hard part is to show that c is less than or equal to 1Or I believe this is the correct approach

d = gcd(a,b) iff and only if d satisfies

1) d|a and d|b
2) if c|a and c|b --> c|d

nevermind, this last approach doesn't work, because by hypothesis, c neither divides a nor b

 

[Dick]

Ok, gcd(a,b)=1 means that there are k1 and k2 such that k1*a+k2*b=1. gcd(a,c)=1 means there are l1 and l2 such that l1*a+l2*c=1. Multiply the two together and find m1 and m2 such that m1*a+m2*b*c=1.

 

[b0it0i]

i see, that's the final step missing

i said since
(a,b) = 1 --> 1 = ax + by
(a,c) = 1 --> 1 = af + cg
By Theorem, x,y,f, and g exist

1 = 1.1 = (ax+by)(af+cg) = a^2xf + axcg + aabyf + bycg
= a(axf + xcg + byf) + bc(yg)
therefore let

u = axf + xcg + byf
and
v = yg

and since, all the "letters" used exist and are integers, they satisfy the domain, and the proposition

is that correct? even though "u" is messy, it doesn't matter right? because those integers exist (by theorem)

 

[Dick]

That's correct. axf+xcg+byf is just as much of an integer as x is. It doesn't matter that it's "messy".