5
$\begingroup$

My nine year old asked this question at lunch today: Is there a number that is divisible by everything that is half or less than the number?

I immediately answered, "No. I mean, 6. But not for any number bigger than 6."

So I tried to think why that was true, and my first efforts didn't quite work. I did come up with a proof, but it isn't as elegant as I hoped.

How would you prove this?

$\endgroup$
  • $\begingroup$ So far, while there are some nice answers, I'm feeling ok about my failure to come up with a beautiful proof quickly. None of these answers would be easy for a bright nine-year-old to follow. $\endgroup$ – Eric Wilson Mar 26 '15 at 18:50
6
$\begingroup$

if $n\geq 7$ and $n$ is divisible by all numbers less then $\frac{n}{2}$, so $n$ is even and we can deduce easily that $\frac{n}{2}(\frac{n}{2}-1)$ divides $n$ (because $\gcd(\frac{n}{2},(\frac{n}{2}-1))=1$) and the most important: $$\frac{n}{2}(\frac{n}{2}-1)\leq n$$

whence : $n-2=2(\frac{n}{2}-1)\leq 4$ so $n\leq 6$

$\endgroup$
  • 1
    $\begingroup$ Where do you get $n-2 \leq 4$ from, exactly? (I know how you did it, you multiply both sides by $4/n$, but it's not obvious from what you wrote.) $\endgroup$ – Ian Mar 26 '15 at 17:42
  • $\begingroup$ we have $\frac{n}{2}(\frac{n}{2}-1)\leq n$ and so $(\frac{n}{2}-1)\leq 2$ and hence $n-2\leq 4$ $\endgroup$ – Elaqqad Mar 26 '15 at 17:46
4
$\begingroup$

Since $n>6$, we have that $2<3 <n/2$, so $n$ is divisible by $2$ and $3$.

Since $n=2\cdot\frac{n}{2}$ and $\frac{n}{2}-1<\frac{n}{2}$, $\frac{n}{2}-1$ divides $n$. $\frac{n}{2}−1$ must have the next smallest codivisor, which is $3$, so must be equal to $\frac{n}{3}$.

Solving $\frac{n}{2}-1=\frac{n}{3}$ gives $n=6$, a contradiction to $n>6$. Thus, $6$ is the largest such positive integer.

$\endgroup$
  • 1
    $\begingroup$ Why must $\frac{n}{2}-1$ equal $\frac{n}{3}$? $\endgroup$ – vadim123 Mar 26 '15 at 17:36
  • 2
    $\begingroup$ It must divide $n$, $n$ is divisible by $3$, and $n/2$ is the codivisor of $2$, so $n/2-1$ must have the next smallest codivisor, which is $3$. $\endgroup$ – Nishant Mar 26 '15 at 17:42
1
$\begingroup$

Set $t=\lfloor \sqrt{n}\rfloor$. By Bertrand's postulate, provided $t>3$, there is a prime $p$ with $t<p<2t-2$. By Bertrand's postulate again, there is a prime $q$ with $2t-2<q<4t-6$. The product $pq>t^2\ge n$, so it is not possible that both $p,q$ are divisors of $n$. Hence, there is some number $k$ not dividing $n$, satisfying $$1<k<4\lfloor \sqrt{n}\rfloor-6$$

For all $n$, this is a better bound than $n/2$. However we need $\lfloor \sqrt{n}\rfloor >3$, i.e. $n\ge 16$. For smaller $n$ we need to check by hand, as you have done.

$\endgroup$
0
$\begingroup$

$\sqrt{n}<\frac{n}{2}-2$ if $n \geq 12$. This means it is not possible after 12. It is also false smaller numbers between 7 and 12.

$\endgroup$
-1
$\begingroup$

if n is odd, $f=\frac{n-1}2$ is an integer less than $\frac n2$. $2f=n-1$, so if $f\gt1$ f is not a factor of n. if $f\gt1$ then $n\gt3$, so for all odd $n\gt3$ n there is a number f which is not a factor. if n is even, $f=\frac{n-2}2$ is an integer less than $\frac n2$. $2f=n-2$, so if $f\gt2$ f is not a factor of n. if $f\gt2$ then $n\gt6$, so for all even $n\gt6$ n there is a number f which is not a factor.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.