Question

How to say that l.c.m of any number in {1,2,....n} divides n!
Please, help

Answer 1

@rational

Answer 2

\[\large \mathbb{lcm}\times \gcd = a\times b\]

Answer 3

I don't get ;)

Answer 4

lets start with that

Answer 5

product of lcm and gcd equals produt of numbers

Answer 6

I mean, if I have (2)(3)(5) , then the product divides n!
But I want it in general.
:) English is not my mother tongue so that I have trouble in interpreting the math problem to words

Answer 7

and the question has to be rephrased a bit

you want to prove `lcm(1,2,3...n) divides n!` right ?

Answer 8

any of them, like
(2)(3)(5)
(2)(3)(5)(7)
and more... until I can factor the whole set into product of something and that something divides n!

Answer 9

Oh ok got you :)
so basically we want to prove lcm of any arbitrary # of elements from the set divides n!

Answer 10

l.c.m ((2)(3)(5))
l.c.m(2)(3)(5)(7))
and those l.c.m divides n!

Answer 11

Yes. :) I am sorry for my poooooooor explanation.

Answer 12

Rational's idea will work. Try to prove: $$\text{lcm}\left(a_1,a_2,\ldots ,a_k\right)\cdot\gcd\left(a_1,a_2,\ldots ,a_k\right)=a_1\cdot a_2\cdots a_k.$$

Answer 13

But we don't have gcd.

Answer 14

We just prove l.c.m (any # of the set)| n!

Answer 15

Hmm...then maybe a slight change. Try to prove that if \(c\) is any common multiple of \(a_1,a_2,\ldots ,a_k \), then \(\text{lcm}\left(a_1,a_2,\ldots ,a_k\right)\mid c.\)

Answer 16

Or try to prove lcm (a1, a2) = c and c \(\in\) the set?

Answer 17

That might not be true. The lcm(n,n-1)=n(n-1), which is too big to be in the set.

Answer 18

But it |n! still, right?

Answer 19

ah, thats correct.

Answer 20

The biggest case is n(n-1)(n-2) |n!
and it is the case of 3 consecutive numbers. Other smaller one is a factor of this case. Am I right?

Answer 21

Intuition says yes, but that's something you would need to prove.

Answer 22

:(

Answer 23

For any \(a_1,a_2,\cdots,a_k\in \{1,2,\ldots ,n\}\), it turns out \(n!\) is a common multiple of \(a_1,a_2,\cdots,a_k\in \{1,2,\ldots ,n\}\). That's why I think proving the lcm divides any common multiple is a decent idea.

If we had access to the gcd, Rational's idea would be best and fastest.

Answer 24

Please , put it in logic.

Answer 25

Claim: Let \(a_1,a_2,\cdots,a_k\in \{1,2,\ldots ,n\}\), let \(l=\text{lcm}(a_1,a_2,\cdots,a_k)\), and let \(c\) be any common multiple of \(a_1,a_2,\cdots,a_k\). Then \(l\mid c\).

Answer 26

If we can prove this claim, then it follows that \(n!\) is always a common multiple of \(a_1,a_2,\cdots,a_k\), so \(l\mid n!\)

Answer 27

To prove the claim, we use two facts:
1) Division Algorithm, and

2) The LCM is the LEAST positive common multiple. In other words, there cannot be a positive common multiple that is smaller than the LCM.

Answer 28

Alright. So let \(a_1,a_2,\cdots,a_k\in \{1,2,\ldots ,n\}\), \(l\) be their LCM, and \(c\) be any common multiple. Using the division algorithm on c and l, we know there exist integers q and r such that $$c=lq+r, \quad 0\le r<l.$$

Answer 29

Rearranging this equation yields: $$c-lq=r.$$ Now, \(a_i\mid c\), and \(a_i\mid l\) (because both l and c are multiples of \(a_i\)). Thus \(a_i \mid r\) for any i. But this means \(r\) is a common multiple of \(a_1,a_2,\cdots,a_k\).

Answer 30

So we now know \(r\) is a common multiple of \(a_1,a_2,\cdots,a_k\), and that \(0\le r<l\). Since l is the LEAST common multiple, \(r\) cannot be positive. Therefore \(r=0\), and we conclude that $$c=lq,$$ which implies \(l\mid c\).

Answer 31

Question: why do we have to go on that way while we can do something shorter to get l |c?
As your logic, l =l.c.m ((a1,a2,.....,a_k))
c is any common multiplication, then \(c= \alpha l\) for some \(\alpha\) in Z

Answer 32

It depends on if you are given $$c=\alpha l$$ as a definition, or if you need to prove it. I wasn't sure which you were given, so i proved it just incase.

Answer 33

I guess I should have asked that before I started >.< haha

Answer 34

:)

Answer 35

Anywhos, now that you have this fact, the problem is done, since \(n!\) will be a common multiple of any \(a_1,a_2,\cdots,a_k\) in the set.

Answer 36

Thank you very much. I got you. :)