Prove that for $n \gt 6$, there is a number $1 \lt k \lt n/2$ that does not divide $n$

Question

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?

Answer 1

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$

Answer 2

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.

Answer 3

$\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.

Answer 4

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.

Answer 5

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.