If $n$ is odd then the largest integer that is less than $\frac{n}{2}$ is $\frac{n-1}{2}$. Let $d$ be a common divisor of numbers $\frac{n-1}{2}$ and $n$. Then $d$ is a common divisor of numbers $n-1$ and $n$, implying that $d = 1$. Hence $\frac{n-1}{2}$ and $n$ are relatively prime, meaning that the hypothesis holds in the case of odd numbers.

If $n$ is even then the two largest integers that are less than $\frac{n}{2}$ are $\frac{n}{2} - 1$ and $\frac{n}{2} - 2$. Let $d_1$ be a common divisor of numbers $\frac{n}{2} - 1$ and $n$, and let $d_2$ be a common divisor of numbers $\frac{n}{2} - 2$ and $n$. Then $d_1$ is a common divisor of numbers $n-2$ and $n$, and $d_2$ is a common divisor of numbers $n-4$ and $n$. Hence $d_1$ divides 2, i.e., is either 1 or 2, and $d_2$ divides 4, i.e., is either 1 or 2 or 4. If $d_1$ and $d_2$ were both larger than 1, they both should be even, whence their multiples $\frac{n}{2} - 1$ and $\frac{n}{2} - 2$ should be even. This is impossible, since $\frac{n}{2} - 1$ and $\frac{n}{2} - 2$ are consecutive integers. The contradiction shows that at least one of the divisors $d_1$ and $d_2$ equals 1. Thus one of $\frac{n}{2} - 1$ and $\frac{n}{2} - 2$ is relatively prime to $n$, meaning that the hypothesis holds in the case of even numbers, too.