Question

Is this true?
gcd(a,b,c)=gcd(gcd(a,b),c)

Answer 1

I think it is not true.

Answer 2

gcd(4,12,16)=4 correct?
gcd(4,12)=4 so gcd(gcd(4,12),16)=gcd(4,16)=4

I think it's true.

Answer 3

this is how I found gcd (a,b,c) using a TI 83/84 . gcd normally has two inputs

gcd(a,b,c) = gcd ( gcd(a,b) , c )

Answer 4

it is true, yes. anybody want to prove it? :)

Answer 5

Honestly it seems like it would be a waste of time to prove it true. It just seems too obviously true to me. For something to be the gcd of 3 numbers then surely it must also be the gcd of the gcd of two of the numbers and the other number.

Answer 6

this is true also for lcm

Answer 7

lcm (a,b,c) = lcm( lcm(a,b), c)

Answer 8

and you can generalize this
In general
gcd (a1,a2,a3,... an) = gcd ( gcd(a1,a2,...an-1) , an)

Answer 9

Does this mean we can extend

gcd(a,b)*lcm(a,b)=a*b

to

gcd(a,b,c)*lcm(a,b,c)=a*b*c

Answer 10

Remember the definition based on the prime factorization.

Answer 11

lcm and gcd are based on max and min functions.

Answer 12

That multiplication works due to the fact that: \[
\min(a,b) + \max(a,b) = a+b
\]

Answer 13

So ask youself: \[
\min(a,b,c) + \max(a,b,c) = a+b+c
\]Because I don't think so.

Answer 14

Simple example... \((1,2,4)=(2^0,2^1,2^2)\).\[
\gcd(1,2,4) = 2^{\min(0,1,2)}=2^0=1\\
\text{lcm}(1,2,4) = 2^{\max(0,1,2)}=2^2=4\\
1\times 4 = 4 \neq 8=1\times 2\times 4
\]

Answer 15

And... no response...

Answer 16

one sec, you are producing a counterexample

Answer 17

yes i agree with that

Answer 18

gcd(gcd(a,b),c)
let integer d>0 such that gcd(a,b)=d
then ax+by=d for some integers x and y
so axL+byL=dL
so au+bv=dL
gcd(d,c)=e means there are some integers m and n such that
\[\frac{au+bv}{L} m+cn =e \\ \frac{u}{L}a m+\frac{v}{L}bm +cn=e\]
xL=u and yL=v
so we have
\[x am +y bm+cn=e\]
so xm, ym, and cn are integers
such that gcd(a,b,c)=e
I think
I don't know if I need more...

Answer 19

I think I need to show that gcd(xm,ym,n)=1

Answer 20

So we know gcd(x,y)=1
so gcd(xm,ym)=m
so we really only need to show gcd(m,n)=1

Answer 21

And please let me know if there is something wrong with what I'm saying

Answer 22

alway we know gcd(m,n)=1 since we suppose gcd(d,c)=e where integers m and n are such that dm+cn=e

Answer 23

so I think that above is enough to prove it

Answer 24

looking back at that I think I made some unnecessary steps

Answer 25

\[\gcd(45,9,27)=9 => 45x_1+9x_2+27x_3=9 \\ \gcd(45,9)=9 => 45a_1+9b_1=9 \\ \gcd(\gcd(45,9),27)=\gcd(9,27)=9 => 9a_2+27b_2=9 \\ \gcd(\gcd(45,9),27)=9 => (45a_1+9b_1)a_2+27b_2=9 \\ 45a_1 a_2+9b_1 a_2+27b_2=9\]

Answer 26

@freckles, We know \(\gcd(a,b,c) = \gcd(\gcd(a,b),c)\) works due to the fact that: \[
\min(a,b,c) = \min(\min(a,b),c)
\]

Answer 27

Because \(\gcd\) is just the \(\min\) function on the exponents of the prime factorization.

Answer 28

I was trying to prove gcd(a,b,c)=gcd(gcd,(a,b),c) a different way