Question

Prove the following about greatest common divisors. gcd(a,b) denotes the greatest common divisor of a and b.
i) If gcd(a,b)=1 then gcd(ac,b)=gcd(b,c)
ii) If gcd(a,b)=1 and c|(a+b) then gcd(a,c)=gcd(b,c)=1

Answer 1

c|(a+b) denotes that c divides (a+b), that is, there exists an integer k such that (a+b)=k.c

Answer 2

what you need for both of these i think, is that if \((a,b)=1\) there exists \(x,y\) with \(ax+by=1\)

Answer 3

lets call \((ac,b)=d\) you want to show that \(d|c\)
since \(d|b\) and \(d|ac\) it must also divide \(acx+bcy\) for the same \(x,y\) above

Answer 4

therefore \(d|acx+bcy=c(ax+by)=c\) since \(ax+by=1\) showing you that \(d|c\)

Answer 5

Why do I want to show that d|c?

Answer 6

I know that, d|c and d|b would mean that... Oh I see, it would divide any linear combination of b and c. But how do I guarantee that it is the smallest number that divides that linear combination?

Answer 7

you show that the gcd's are equal by showing that the gcd of one pair divides the other pair, and that the gcd of the second pair divides the first pair

Answer 8

But you only showed that d|c.... There's something I'm not seeing here.

Answer 9

ok let me try again because all these symbols are confusing

Answer 10

you want to show gcd(ac,b)=gcd(b,c)

Answer 11

so if you call \((b,c)=d\) you know that \(d|b, d|c\) and so clearly \(d|ac\) and thus \(d|gcd(ac,b)\)

Answer 12

in other words, it is fairly clear that the gcd of \(c\) and \(b\) divides the gcd of \(ac\) and \(b\) right?

Answer 13

if not let me know

Answer 14

It's because d|ac and d|b, right?

Answer 15

yes

Answer 16

so if it divides them both, it must divide their greatest common divisor, on account of the greatest common divisor is, well, the greatest

Answer 17

so the hard part is to show that the gcd of ac and b also divides the gcd of c and b

Answer 18

if you can show that, they must be equal
i hope the logic of that is clear
i have two numbers, \(d_1\) and \(d_2\) and they each divide the other
then they must be the same number

Answer 19

Yes, I understand that. So, now we have to prove that the gcd(ac,b)|gcd(b,c)

Answer 20

yes that is what you have to do
which amounts to showing that it divides c, because it obviously divides b

Answer 21

And we do so by stating that, since gcd(a,b)=1, it means that
\[1=ax+by\] for some x,y integers

Answer 22

yes

Answer 23

Ah, yes, clearly divides b.

Answer 24

So we multiply by c

Answer 25

yes

Answer 26

So \[c=acx+bcy\], which can be rewritten as
\[c=c(ax)+b(cy)\] which means that c is a multiple of the gcd(b,c), obviously. That means that gcd(b,c)|c

Answer 27

hmm i think the logic got a little lost there

Answer 28

Yes, i'm now stating obvious things.

Answer 29

Let me get a piece of paper.

Answer 30

only one typo

Answer 31

since gcd (ac, b) divides ac it must divide acx
likewise it must divide by
therefore it must divide \(cax+by=c\)

Answer 32

Why is \[cax+by=c\] ?

Answer 33

because i made a typo

Answer 34

should be \(cax+cby=c\)

Answer 35

and you can see that gcd(ac,b) must divide both terms on the left, so it must divide c

Answer 36

hope the logic is clear, sorry for the typo above

Answer 37

Ok, let me write this nicely and see if I'm doing it right.