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?
 A: 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$
A: 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.
A: 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.
A: $\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.
A: 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.
