Question

So like I just discovered some kind of a theorem. Looking how to prove it.

\[k_0 < k_1 < k_2 < k_3 < \cdots < k_n \implies \gcd (k_0, k_1, k_2 \cdots k_n) \le \min \left(\bigcup_{i = 1}^{n} \left(k_i - k_{i - 1}\right)\right) \]

Answer 1

@Jhannybean Yeah, this discovery comes from that gcf question :P

Answer 2

Looks kind of like a Reimann Sum.

Answer 3

Technically, that just says that gcd is lesser than the least difference between any two numbers. Seems obvious but how to prove it?

Answer 4

I don't know atm D: you're asking too difficult questions at 3:30 AM ^_^''.....

Answer 5

The question is not difficult at all! The answer is...

Answer 6

@nincompoop :'D

Answer 7

@ganeshie8 @whpalmer4 :)

Answer 8

@radar

Answer 9

@oldrin.bataku

Answer 10

@shubhamsrg :)

Answer 11

gcd has to each of the term. it follows that gcd| min(k_i - k_{i+1})

Answer 12

are you trying to prove that:

the biggest common divisor cannot be bigger than the smallest element in the set.

and the smallest common multiple cannot be smaller than the largest element in the set.

Answer 13

gcd(5,5) = 5

5 - 5 = 0

is the gcd(5,5) <= 0?

Answer 14

But \(5 < 5\) is not true.

Answer 15

@amistre64

Answer 16

your thrm states:

gcd(k0,k1) <= k1-k0

gcd(5,5) <= 5-5

5 <= 0

or am i reading your notation incorrectly?

Answer 17

i see, the implication is that k0 < k1 so they cant be equal

Answer 18

Hey KingGeorge, I hope you could help me with this tough (for me) problem.

Answer 19

I think it's simpler than I first thought. Suppose WLOG that \(k_i-k_{i-1}\) is the minimal difference. Then the gcd of \(k_0,...,k_n\) must divide both \(k_i\) and \(k_{i-1}\). Thus, it must divide \(k_i-k_{i-1}\), and since \(k_i>k_{i-1}\), we immediately get that the gcd is \(\le (k_i-k_{i-1})\).

Answer 20

My first thought was via induction, but I think this is good enough.

Answer 21

I'd have to keep reading this proof again and again. Let me think about it. Thanks for the help!

Answer 22

You're welcome.

Answer 23

I got it till \(k_i > k_{i - 1}\). How did you get that the gcd is \(\le k_i - k_{i-1}\)

Answer 24

Well, it must divide \(k_i-k_{i-1}\) (which is positive), but if the gcd were greater, then it clearly would not be able to divide it. Thus, the gcd must be less than or equal to \(k_i-k_{i-1}\).

We need that it's positive, since if it were negative, then the gcd would actually be greater since the gcd is defined to be positive.

Answer 25

Oh, of course! I never thought of the negation of that. Thanks!

Answer 26

You're welcome.