- #1

- 36

- 0

## 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)

Last edited: