Prove that for $n \gt 6$, there is a number $1 \lt k \lt n/2$ that does not divide $n$ 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?

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.
