Largest Integer Divisible by All IntegersDate: 01/01/2002 at 00:43:23 From: Salman Subject: Number theory Hello, Dr. Maths, Please help me in solving the following problem: Show that 24 is the largest integer divisible by all integers less than its square root. Thanks. Date: 01/02/2002 at 15:28:04 From: Doctor Rob Subject: Re: Number theory Thanks for writing to Ask Dr. Math, Salman. Any such number n must satisfy the following: Let m be the greatest integer such that m^2 <= n. Then LCM(1,2,3,...,m) | n. But when n >= 25, LCM(1,2,3,...,m) > n, so this division is impossible. This is the crux of the matter, and the part that requires proof. When n >= 25, we get that m >= 5. Now Bertrand's Postulate says that for every real number x > 1 there is a prime number p with x < p < 2*x. Thus there is a prime number p with m < p < 2*m, LCM(1,2,...,2*m) >= LCM(1,2,...,p), because p < 2*m, >= LCM(1,2,...,m)*p, because p > m and p is prime, > n*p, by hypothesis on n, > n*m, because p > m, >= 5*n, because m >= 5, >= 5*m^2, because n >= m^2, > 4*m^2, because m > 0, = (2*m)^2. This eliminates all numbers from n to n*p >= 7*n. Use this fact inductively to eliminate all n >= 25. Feel free to write again if I can help further. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/