Question

Prove that if gcd(a,b)=1, then gcd(a,bc)=gcd(a,c) (Hint: let gcd(a,c)=d and let gcd(a,bc)=e)

Answer 1

god is it late. i wonder if we can do this without making a mess

Answer 2

start with
\[ax+by=1\]

Answer 3

then
\[ax_1+cy_2=d\]
\[ax_2+bcy_2=e\]

Answer 4

and we want to show that
\[d|e,e|d\]

Answer 5

multiply
\[ax+by=1\] by d to get
\[adx+bdy=d\]

Answer 6

no i don't think it is that easy

Answer 7

but i am on the way i think, although at any time i can screw this up

Answer 8

good night. i am going to try a couple more lines of this. i know this is the right idea

Answer 9

it doesn't say anywhere that a b or c are integers
so I don't think it is that easy

Answer 10

we have
\[adx+bdy=d=ax_1+cy_1\]

Answer 11

i think we are suppose to assume they are integers

Answer 12

oh of course everything in sight is an integer

Answer 13

otherwise question doesn't even make sense

Answer 14

You're right it doesn't make sense if they aren't integers

Answer 15

oki think i am almost there

Answer 16

is this line ok
\[adx+bdy=d=ax_1+cy_1\]

Answer 17

it just says
\[d=d\]

Answer 18

That looks right

Answer 19

damn got stuck again hold on

Answer 20

ok i think we write
\[adx+b(ax_1+cy_1)y=d\] and then
\[adx+abx_1y+bcy_1y=d\] and finally
\[a(dx+bx_1y)+bcy_1y=d\]

Answer 21

there got it. and what does this algebra mean?

Answer 22

the last line is a linear combination of
\[a\] and
\[bc\] and since
\[e=\gcd(a,bc)\] it divides any linear combination of the two

Answer 23

and therefore
\[e|d\]

Answer 24

i believe it is all there and actually correct. but we are not done. we just showed that e divides d. the next job is to show that d divides e, but that works with the same idea

Answer 25

again start with
\[ax+by=1\] multiply by
\[e=ax_2+bcy_2\] to get
\[aex+bex=e=ax_2+bcy_2\] and the replace e by
\[ax_2+bcy_2\] in that equation and so on.

Answer 26

You'll have to give me a minute to understand this, but I think it looks right
Why can't we just say that acx + bcy = c so

a(cx) + bc(y) = c and
a(cx) + c(by) = c

so a(cx) + bc(y) = a(cx) + c(by)
which means that gcd(a, bc) = gcd(a, c)

Does this make any sense?

Answer 27

i have to say that i am too tired to get this but i am almost certain it is wrong . but i cannot give a good reason at the moment.

Answer 28

I think you are probably right. Thank you for your help!