GGPiku wrote: Please check if my solution is correct...

I think this solution is incorrect, because by your logic, you've only reduced it to showing $\lfloor n^2/\phi(n)\rfloor\ge\sigma(n)$ which is false (http://www.wolframalpha.com/input/?i=n*floor(n%2Fphi(n))-sigma(n)). The point is you can't just say that $a\geq \frac{n^2}{\phi(n)}$, since within each block $kn+1,(k+1)n$, the relatively prime numbers aren't evenly spaced. However, this does give a good heuristic as to why the problem makes sense.

Also, could someone with proper privileges please add this to AoPS contest collections (the whole TST)?

Let $f(m)$ denote the number of positive integers less than or equal to $m$ which are relatively prime to $n$. The $n^\text{th}$ smallest positive integer relatively prime to $n$ is the smallest value of $m$ which satisfies $f(m)=n$. Additionally, $f$ is non-decreasing. We will show that $f(\sigma(n))\leq n$, and equality holds if and only if $n$ is a prime power. Let $d_1, \dotsc, d_k$ denote the divisors of $n$ (in any order), and $\phi$ be the totient function. Note that any integer relatively prime to $n$ is also relatively prime to $d_i$. Among any set of $d_i$ consecutive integers, there are exactly $\phi(d_i)$ integers relatively prime to $d_i$, and hence at most $\phi(d_i)$ integers relatively prime to $n$. Then among the first $d_1+\dotsb + d_k$ positive integers, there are at most $\phi(d_1)+\dotsb + \phi(d_k)$ positive integers relatively prime to $n$. Now just observe that $d_1+\dotsb + d_k=\sigma(n)$ and $\phi(d_1)+\dotsb + \phi(d_k)=n$, so $f(\sigma(n))\leq n$. If $n$ is not a prime power, it has two distinct prime divisors $p < q$. If we order the divisors so that $d_1=q$, then in the above process, there are strictly less than $\phi(d_1)$ positive integers among the first $d_1$ positive integers which are relatively prime to $n$ because $p$ and $q$ are both in this interval. Therefore $f(\sigma(n)) < n$. Hence the $n^\text{th}$ smallest positive integer relatively prime to $n$ is strictly larger than $\sigma(n)$. If $n=p^k$ is a prime power, then $f(m)=m-\left\lfloor\frac{m}{p}\right\rfloor$ because the integers not coprime to $n$ are the multiples of $p$. For $m=1+p+\dotsb+p^k=\sigma(n)$, we have $\gcd(m, n)=1$ and $f(m)=(1+p+\dotsb + p^k)-(1+p+\dotsb +p^{k-1})=n$. Hence if $n$ is a prime power, the $n^\text{th}$ smallest positive integer relatively prime to $n$ is $\sigma(n)$.

CantonMathGuy wrote: Let $n \ge 2$ be a positive integer, and let $\sigma(n)$ denote the sum of the positive divisors of $n$. Prove that the $n^{\text{th}}$ smallest positive integer relatively prime to $n$ is at least $\sigma(n)$, and determine for which $n$ equality holds. Proposed by Ashwin Sah Answer. Equality occurs only when $n=p^k$ for some prime $p \ge 2$ and integer $k \ge 1$. (Proof) First we prove prime powers work. Let $M=1+p+\dots+p^{k-1}$. Then we claim that $M$ is the $p^{k-1}$th number co-prime to $p^k$. Indeed for any $m>0$ if we have $pm<M$ then $m \le (1+p+\dots+p^{k-2})$. Consequently, $M$ is the $p^{k-1}$th number coprime to $M$. Hence $1+p+\dots+p^k$ is the $p^k$th number coprime to $p^k$. Now we prove the bound. Pick any $n=\prod_{i \ge 1} p_i^{e_i}$ with $m \ge 2$ prime factors. Now pick the maximum $k \ge 1$ with $k\phi(n) \le n$ and let $\ell=n-k\phi(n)$. Let $A$ be the $\ell$th number coprime to $n$. Clearly, $M=kn+A$ is the $n$th number coprime to $n$. Case 1. If $\ell=0$. Then $M=\tfrac{n^2}{\phi(n)}> \sigma(n)$ and we're done. Case 2. If $\ell \ge 1$. Now the number of numbers prime to and less than $n$ below $A$ must be given by $$\ell=A-\sum_{i \ge 1} \left \lfloor \frac{A}{p_i} \right \rfloor +\sum_{i>j>1} \left \lfloor \frac{A}{p_ip_j} \right \rfloor - \dots \le A \prod_{i \ge 1} \left(1-\frac{1}{p_i}\right)+2^{m-1}.$$Consequently, $kn+A \ge kn+\frac{n-k\phi(n)-2^{m-1}}{\prod_{i \ge 1} \left(1-\frac{1}{p_i}\right)}=\frac{n-2^{m-1}}{\prod_{i \ge 1} \left(1-\frac{1}{p_i}\right)}.$ Hence we aim to prove $$\prod_{i \ge 1} p_i^{e_i+1}-\prod_{i \ge 1} (p_i^{e_i+1}-1) \ge 2^{m-1}\prod_{i \ge 1} p_i.$$ WLOG, let $p_1<p_2< \dots$ then we have $$\prod_{i \ge 1} p_i^{e_i+1}-\prod_{i \ge 1} (p_i^{e_i+1}-1)>(p_2^{e_2+1}-1)\dots (p_m^{e_m+1}-1)>(p_2-1)\dots (p_m-1) p_2\dots p_m.$$Hence if $m>2$ then $p_2-1 \ge p_1$ and $p_3-1 \ge 4$ together with $p_i-1 \ge 2$ for $i>3$ yield the desired bound. For $m=2$ we just want $$p_1^{e_1+1}+p_2^{e_2+1}- \ge 2p_1p_2.$$Now clearly $p_i^{e_i+1} \ge p_i^2$ and $(p_1-p_2)^2 \ge 1$ so equality can occur only if $p_1=2, p_2=3$ and $e_1=e_2=1$. But $n=6$ fails at the job hence this case sinks too! All in all $M>\sigma(n)$ if $n \ne p^k$ and the answer is proved. $\blacksquare$ Note. If I did a bound wrong, please tell me! Actually, don't, because it's unlikely I'll consider fixing it I wonder if a solution is possible by combinatorial arguments alone?

The equality case is $n = p^e$ for $p$ prime and a positive integer $e$. It is easy to check that this works. First solution: In what follows, by $[a,b]$ we mean $\{a,a+1,\dots,b\}$. First, we make the following easy observation. Claim: If $a$ and $d$ are positive integers, then precisely $\phi(d)$ elements of $[a, a + d - 1]$ are relatively prime to $d$. Let $d_1$, $d_2$, \dots, $d_k$ denote denote the divisors of $n$ in some order. Consider the intervals \begin{align*} I_1 &= [1, d_1], \\ I_2 &= [d_1+1, d_1+d_2] \\ &\vdots \\ I_k &= [d_1+\dots+d_{k-1}+1, d_1+\dots+d_k]. \end{align*}of length $d_1, \ldots, d_k$ respectively. The $j$th interval will have exactly $\varphi(d_j)$ elements which are relatively prime $d_j$, hence at most $\varphi(d_j)$ which are relatively prime to $n$. Consequently, in $I = \bigcup_{j=1}^k I_k$ there are at most \[ \sum_{j=1}^k \varphi(d_j) = \sum_{d \mid n} \varphi(d) = n \]integers relatively prime to $n$. On the other hand $I = [1,\sigma(n)]$ so this implies the inequality. We see that the equality holds for $n = p^e$. Assume now $p < q$ are distinct primes dividing $n$. Reorder the divisors $d_i$ so that $d_1 = q$. Then $p,q \in I_1$, and so $I_1$ should contain strictly fewer than $\varphi(d_1)=q-1$ elements relatively prime to $n$, hence the inequality is strict. Second solution (Ivan Borsenco and Evan Chen): Let $n = p_1^{e_1} \dots p_k^{e_k}$, where $p_1 < p_2 < \dots$. We are going to assume $k \ge 2$, since the $k=1$ case was resolved in the very beginning, and prove the strict inequality. For a general $N$, the number of relatively prime integers in $[1,N]$ is given exactly by \[ f(N) = N - \sum_i \left\lfloor \frac{N}{p_i} \right\rfloor + \sum_{i<j} \left\lfloor \frac{N}{p_i p_j} \right\rfloor - \dots \]according to the inclusion-exclusion principle. So, we wish to show that $f(\sigma(n)) < n$ (as $k \ge 2$). Discarding the error terms from the floors (noting that we get at most $1$ from the negative floors) gives \begin{align*} f(N) &< 2^{k-1} + N - \sum_i \frac{N}{p_i} + \sum_{i<j} \frac{N}{p_i p_j} - \dots \\ &= 2^{k-1} + N \prod_i \left( 1 - p_i^{-1} \right) \\ &= 2^{k-1} + \prod_i \left( 1 - p_i^{-1} \right) \left( 1 + p_i + p_i^2 + \dots + p_i^{e_i} \right) \\ &= 2^{k-1} + \prod_i \left( p_i^{e_i} - p_i^{-1} \right). \end{align*}The proof is now divided into two cases. If $k=2$ we have \begin{align*} f(N) &< 2 + \left( p_1^{e_1} - p_1^{-1} \right)\left( p_2^{e_2} - p_2^{-1} \right) \\ &= 2 + n - \frac{p_2^{e_2}}{p_1} - \frac{p_1^{e_1}}{p_2} + \frac{1}{p_1p_2} \\ &\le 2 + n - \frac{p_2}{p_1} - \frac{p_1}{p_2} + \frac{1}{p_1p_2} \\ &= n + \frac{1-(p_1-p_2)^2}{p_1p_2} \le n. \end{align*}On the other hand if $k \ge 3$ we may now write \begin{align*} f(N) &< 2^{k-1} + \left[ \prod_{i=2}^{k-1} \left( p_i^{e_i} \right) \right] \left( p_1^{e_1} - p_1^{-1} \right) \\ &= 2^{k-1} + n - \frac{p_2^{e_2} \dots p_k^{e_k}}{p_1} \\ &\le 2^{k-1} + n - \frac{p_2 p_3 \dots p_k}{p_1}. \end{align*}If $p_1 = 2$, then one can show by induction that $p_2 p_3 \dots p_k \ge 2^{k+1}-1$, which implies the result. If $p_1 > 2$, then one can again show by induction $p_3 \dots p_k \ge 2^k-1$ (since $p_3 \ge 7$), which also implies the result.

Equality occurs only when $n=p^k$ for some prime $p \ge 2$ and integer $k \ge 1$. First we prove prime powers work. Let $M=1+p+\dots+p^{k-1}$. Then we claim that $M$ is the $p^{k-1}$th number co-prime to $p^k$. Indeed for any $m>0$ if we have $pm<M$ then $m \le (1+p+\dots+p^{k-2})$. Consequently, $M$ is the $p^{k-1}$th number coprime to $M$. We proceed by proving the string: $\varphi_n(\sum_{j=1}^k d_j) \leq \sum_{d \mid n} \varphi(d) = n.$ Let $d_1,d_2,...d_k$ be the divisors of $n$. It suffices to show that $\varphi_n(\sum_{j=1}^k d_j) \leq \sum_{j=1}^k \varphi_n(d_j)$ because then we can simply use a well-known lemma of multiplicative functions to get to the desired. To show that $\varphi_n(\sum_{j=1}^k d_j) \leq \sum_{j=1}^k \varphi(d_j)$, we begin by claiming $\varphi_n(\sum_{j=1}^r d_j) \leq \sum_{j=1}^r \varphi(d_j)$ for all $r$. We prove this by induction. The base case is just $d_1=d_1$, which is obvious. Now notice that we must prove $\varphi_n(\sum_{j=1}^{r+1} d_j)-\varphi_n(\sum_{j=1}^r d_j) \leq \varphi(d_{r+1)}$. But this is immediate because there are exactly $\varphi(d_{r+1})$ numbers relatively prime to $d_{r+1}$ in the interval, but also that is an upper bound because any element satisfying the case for $n$ must also satisfy it for $d_{r+1}$. Applying the induction up to $k-1$, we can see that the claim must hold. It suffices to find the equality case. We can see that if $n$ has more than one distinct prime factor (at least two with $p<q$), we can reorder the numbers so that $d_1=q$, but then $p$ would be included, resulting in an immediate contradiction. We have proven that only prime powers work.

Does this work? This is equivalent to showing that the number of positive integers $\leq \sigma (n)$ that are relatively prime to $n$ is $\leq n$, with equality holding at $=n$. We induct on the number of distinct prime factors of $n$. Define $X_{k,l}$ be the set of integers relatively prime to $k$ less than or equal to $l$. We thus are trying to prove $|X_{n,\sigma(n)}| \leq n$. The base case is when $n = p^a$ for some prime $p$ and nonnegative integer $a$. Here, $\sigma(n) = 1 + p + \dots + p^a$. We have $|X_{p,p}| = \phi (p) = p-1$, so $|X_{p,\sigma(n)-1}| = (p-1) \cdot \frac{\sigma(n)-1}{p} = p^k - 1$. $\sigma(n)$ is also relatively prime to $p$, so our total is $p^a$. Thus, equality holds here. Now for the inductive step. Assume that for all $n$ with $k-1$ distinct prime factors, the assertion holds. Then it remains to show that for all $n$ with $k$ distinct prime factors, the assertion also holds. Let the largest prime factor of $n$ be $P$, so $n = P^b \cdot n'$, where $n'$ has $k-1$ distinct prime factors. Notice that being relatively prime with $n$ is equivalent to being relatively prime to both $n'$ and $P$, so $$|X_{n,\sigma(n)}| = |X_{n',\sigma(n)} \cap X_{P,\sigma(n)}| = |X_{n',\sigma(n)}| - |\text{multiples of } P \in X_{n',\sigma(n)}|.$$By the inductive hypothesis, $X_{n',\sigma(n')} \leq n'$, and because $\sigma(n')|\sigma(n)$, we have $$|X_{n',\sigma(n)}| = |X_{n',\sigma(n')}| \cdot \frac{\sigma(n)}{\sigma(n')} \leq n' \cdot (1+P+P^2 + \dots + P^b).$$In addition, notice that a multiple of $P$ in $X_{n',\sigma(n)}$ can be divided by $P$ and still be in $X_{n',\sigma(n)}$, and vice versa (as $\gcd(P, n') = 1$) so we have that $$|\text{multiples of } P \in X_{n',\sigma(n)}| = |X_{n',\lfloor \sigma(n)/P \rfloor}| > \frac{n' \cdot (P+P^2 + \dots + P^b)}{P} = n' \cdot (1 + P + \dots + P^{b-1}).$$We therefore have $$|X_{n',\sigma(n)}| - |\text{multiples of } P \in X_{n',\sigma(n)}| < n' \cdot P^b = n,$$as desired. Notice this shows that the strict inequality shows that our only equality case is at the prime powers.

Let $d_1<d_2<\dots<d_k$ be the divisors of $n.$ Write $S_i=d_1+d_2+\dots+d_i$ for $i\in\{1,2,\dots,k\}.$ Say a number $m$ is $\emph{special}$ if for some $i,$ we have $m\in(S_{i-1},S_i]$ and $\gcd(m,d_i)=1$ and $\emph{good}$ if it is relatively prime to $n.$ If a number is relatively prime to $n,$ then it is relatively prime to all divisors of $n.$ Hence, all good numbers in the interval $[1,\sigma(n)]$ are special. Furthermore, since there are exactly $\varphi(k)$ numbers in an interval of length $k$ which are relatively prime to $k,$ there are exactly $\sum_{d\mid n}\varphi(d)=n$ special numbers. Therefore, the $n$th good number is at least $\sigma(n),$ as desired. It is easy to check that equality occurs for all powers of primes, so suppose that equality occurs for some $n$ with at least two prime factors. Let $p_1,p_2$ be the smallest prime factors of $n.$ $\textbf{Case 1: }$ $p_2>2p_1$ Suppose $p_2=d_i.$ Since the interval $(S_{i-1},S_i]$ contains $p_2$ numbers, it contains at least two multiples of $p_1.$ Moreover, all numbers in the interval $(S_{i-1},S_i]$ except one are relatively prime to $p_2.$ Therefore, there is some special number divisible by $p_1$ and hence not good, contradiction. $\blacksquare$ $\textbf{Case 2: }$ $p_2<2p_1$ If $p_1=2$ and $p_2=3,$ then the number $3$ is special but not good, so we may assume this is not true. Since $p_1\ge 2,$ we have $p_{1}^2\ge 2p_1>p_2.$ This implies that $d_2=p_1$ and $d_3=p_2,$ so $S_2=1+p_1$ and $S_3=1+p_1+p_2.$ Since $(p_1,p_2)\ne (2,3),$ we know $p_{1}p_{2}>1+p_1+p_2.$ Therefore, there is no number in the interval $(S_2,S_3]$ divisible by both $p_1$ and $p_2.$ But since $p_2>p_1,$ there must be some number in the interval $(S_2,S_3]$ divisible by $p_1.$ Hence, there is some special number that is not good, contradiction. $\blacksquare$ Thus, equality occurs if and only if $n$ is a power of a prime.

Let $d_1,d_2,...,d_m$ be the divisors of $n$. Let $s_0=0$ and $s_i=\sum_{j=1}^{i}d_j$ let $I_i$ be the interval $[s_{i-1}+1,s_i]$. Let $c_i$ be the number of integers in the interval $I_i$ that is coprime to $m$. Now if an integer is coprime with $n$ then it is coprime with $d_i$, meanwhile, the number of integers in $I_i$ which is coprime to $d_i$ is equal to the number of integers in the set $\{1,2,...,d_i\}$ that is coprime to $d_i$, therefore $$c_i\leq \varphi(d_i)$$Let $S$ be the number of integers smaller than $\sigma{d_i}$ and coprime with $n$, then $$S=\sum_{i=1}^m c_i\leq \sum_{i=1}^m\varphi(d_i)=n$$as desired. Now if $n$ has at least two prime factors $p<q$, then there exists some integer in the interval of $q$ such that it is divisible by $p$, hence equality can never hold. Conversely, if $n$ has one prime factor, it is straightforward to check that equality holds.

This is such a beautiful problem. Lemma (obvious): If $d\mid n$ is a divisor of $n$, then any $d$ consecutive positive integers contain at most $\varphi(d)$ numbers that are coprime to $n$. Furthermore, if there exists a number in that interval coprime to $d$ but not coprime to $n$, equality does not hold. Using this lemma, we see that among positive integers at most $\sigma(n)$, there are at most $\sum_{d\mid n} \varphi(d) = n$ numbers coprime to $n$. Furthermore, if there exist two distinct primes $p < q$ that both divide $n$, then any $q$ consecutive integers contain a multiple of $p$, making the inequality strict. Lastly, if $n$ is a prime power, then it is easy to verify that equality holds.

Thanks samuel for the hint! Equality holds only when $n = p^{k}$ for some prime $p$. This is true because the nth number relatively prime to $p$ is $p\cdot \frac{p^{k} - 1}{p-1} + 1 = p^{k} + p^{k-1} + p^{k-2} + \ldots + 1 = \sigma(n)$. We will now prove that the nth number relatively prime to $n$ is greater than $\sigma(n)$ Lemma: I claim that for any $d, k$, the number of numbers in the range $k, k+1, \ldots k + d - 1$ that is relatively prime to $d$ is $\varphi(d)$. Define $f(d, k)$ as the amount, we prove $f(d,k) = \varphi(d)$ We can prove this using induction on $k$; our base case of $k = 0$ is the definition of $\varphi(d)$, and if it is true for $k$, then we have two cases: Case 1, where $gcd(k, d) = 1$, then $gcd(k+d, d) = 1$ so $f(k+1, d) = f(k, d) + 1 - 1 = f(k, d) = \varphi(d)$. Case 2, where $gcd(k, d) > 1,$ then $gcd(k+d, d) > 1$, so $f(k+1, d) = f(k, d) = \varphi(d)$. This completes our induction. We have the identity $\sum_{d | n} \varphi(n) = n$. Then, have a counter cnt that starts at $0$. For each $d|n$, the next $\varphi(d)$ numbers relatively prime to $n$ that is greater than cnt is greater or equal than the next $\varphi(d)$ numbers relatively prime to $d$ that is greater than cnt. Then, this means the next $\varphi(d)$ numbers relatively prime to $n$ is greater than $cnt + d$, so we can add $d$ to cnt. Doing this over all $d$ gives the nth relatively prime number to $n$ (using our identity) is greater or equal to $\sigma(n)$. It is equal to $\sigma(n)$ only when the number of numbers relatively prime to $d$ is equal to the number of numbers relatively prime to $n$ in the next $d$ numbers, but this means $d, n$ share all the same prime factors, which must also mean that $n$ can have at most one prime factor. Thus, equality only holds when $n = p^{k}$.

Lemma(well known): The number of numbers relatively prime to $n$ in the interval $[X,X+1,........,X+d]$ with $d|N$ is exactly $\varphi(d)$ Claim: $\sum_{d|n} \varphi(d)=n$ Proof: Define $F(d)=\sum_{d|n} \varphi(d)$ By the property of multiplicative functions we know that $(f \cdot g)(n) \equiv \sum_{d|n} f(d) g(\frac{n}{d})$ with both $f(X),g(X)$ multiplicative. Over here $g \rightarrow 1$ maps to $1$ hence the sum becomes $F(d)=\sum_{d|n} \varphi(d)$ is multiplicative. Hence it suffices to evaluate this sum for $n=p^{\ell}$ where the sum becomes $p-1 \cdot \frac{p^{\ell}-1}{p-1}+1=p^{\ell}$,as required. Now we are almost done:Consider intervals of the length $[1,2,......d_1],[d_1+1,............,d_1+d_2],........$ Clearly there are $\sum_{d|n} \varphi(d)=n$ numbers which is atleast $\sum_{d|n} d$ which is $\sigma(n)$ and we are done. Equality holds only when $n = p^{k}$ since $p\cdot \frac{p^{k} - 1}{p-1} + 1 = p^{k} + p^{k-1} + p^{k-2} + \ldots + 1 = \sigma(n)$

Let $\phi_n(k)$ denote the number of numbers $\leq k$ relatively prime to $n$. It is equivalent to the prolem to prove that $\phi_n(\sigma(n)) \leq n$ and determine when equality holds. Let $T$ be the total number of positive integer divisors of $n$ and let $\sigma(n) = d_1 + d_2 + \ldots + d_T$. Suppose we divide $[1, \sigma(n)]$ into $T$ intervals $I_1, \ldots , I_T$ where $I_1$ consists of the first $d_1 = 1$ positive integers, $I_2$ of the next $d_2$, and so on until $I_T$ consisting of the last $d_T = n$. Note that for every $d \mid n$, the number of positive integers in any consecutive interval of size $d$ relatively prime to $d$ is $\phi(d)$ by definition. Furthermore, for each such $d \mid n$, since being relatively prime to $n$ is at least as much criteria than being relatively prime to $d$, it follows that\[\phi_n(d_1 + \ldots + d_T) \leq \phi(d_1) + \ldots + \phi(d_T) = n\]where the last step holds by a well known identity (or just Dirichlet Convolution). This proves the desired inequality. It is easy to check that equality clearly exists when $n = p^m$ is a prime power. If not, and some two primes $p, q \mid n$, then in some interval say, of length $p^r$ for some $r$, the number of numbers relatively prime to $pq$ is strictly less than the number of numbers relatively prime to $p$, making the inequality strict. Hence, the result holds, with equality if and only if $n = p^m$.

The answer is prime powers. These clearly work since $\sigma(p^k) - \lfloor \frac{\sigma(p^k)}{p}\rfloor = p^k$. Otherwise, note that for any $d\mid n$, any string of $d$ consecutive numbers has at most $\varphi(d)$ numbers relatively prime to n. Thus, the number of numbers relatively prime to $n$ that are $\leq \sigma(n)$ can be broken into blocks of $d$, and the total is $\leq \sum_{d\mid n} \phi(d) = n$. Since $n$ is not a prime power however, there exist $p<q$ such that $p,q\mid n$, and thus the segment of $q$ will have at most $q-2$ numbers relatively prime to $n$. Thus, the inequality is tight, so for such $n$ there are $<n$ numbers $\leq \sigma(n)$ that are relatively prime to $n$, so we are done. $\blacksquare$.

What beautiful solution? I claim that the equality case holds for prime powers only. I will prove this later. Let the prime factorization of $n$ be $p_1^{e_1}\ldots p_k^{e_k}$, where $p_1<\cdots<p_k$. Define $f(N)$ to be the number of positive integers that are at most $N$ and are coprime to $n$. By inclusion-exclusion, we have $$f(N)=\sum_{S \subseteq \{1,\ldots,k\}} (-1)^{|S|}\left\lfloor\frac{N}{\prod_{i \in S} p_i}\right\rfloor=N-\sum_{i} \left\lfloor \frac{N}{p_i}\right\rfloor+\sum_{i<j} \left\lfloor \frac{N}{p_ip_j}\right\rfloor-\cdots.$$Since $f$ is obviously nondecreasing it suffices to show that $f(N) \leq n$ where $N=\sigma(n)$, where equality holds only when $n$ is a prime power. For $n=p^k$, we have $$f(\sigma(n))=(p^k+\cdots+1)-\left\lfloor \frac{p^k+\cdots+1}{p}\right\rfloor = (p^k+\cdots+1)-(p^{k-1}+\cdots+1)=p^k,$$so equality holds in this case. Henceforth suppose $k \geq 2$. Remove the floors and correct for only the negative errors, which are at most $1$ per negative floor, yielding \begin{align*} f(N)&<2^{k-1}+N-\sum_{i} \frac{N}{p_i}+\sum_{i<j} \frac{N}{p_ip_j}-\cdots\\ &=2^{k-1}+N\prod_i(1-p_i^{-1})\\ &=2^{k-1}+\prod_i (1-p_i^{-1})(p_i^{e_i}+\cdots+1)\\ &=2^{k-1}+\prod_i (p_i^{e_i}-p_i^{-1}). \end{align*}First I will show that we can WLOG assume that $e_i=1$ for all $i$ (this isn't super necessary because we can just explicitly account for it later on, but it's how I originally solved the problem). We would like to show that the final expression is strictly less than $n$, which is equivalent to $$\prod_i p_i^{e_i}-\prod_i (p_i^{e_i}-p_i^{-1}) \geq 2^{k-1}.$$Fix some $1 \leq j \leq k$, so the LHS equals $$p_j^{e_j}\left(\prod_{i \neq j} p_i^{e_i} - \prod_{i \neq j} (p_i^{e_i}-p_i^{-1})\right)+\text{something independent of }e_j,$$which is minimized when $e_j$ is minimized, since the expression inside the parentheses is clearly positive. This proves our desired mini-claim. Suppose $k=2$, and for convenience let $p_1=p,p_2=q$. Then applying our mini-claim \begin{align*} f(N)&<2+(p-p^{-1})(q-q^{-1})\\ &=2+pq-\frac{p}{q}-\frac{q}{p}+\frac{1}{pq}\\ &=pq-\frac{p^2-2pq+q^2-1}{pq}\\ &=pq-\frac{(p-q)^2-1}{pq} \leq pq=n, \end{align*}since $p \neq q \implies |p-q|\geq 1$, hence proved. Now suppose $k \geq 3$. In this case, \begin{align*} f(N)&<2^{k-1}+\prod_i (p_i^{e_i}-p_i^{-1})\\ &<2^{k-1} (p_1-p_1^{-1})\prod_{i \geq 2} p_i\\ &=n+2^{k-1}-\frac{p_2\ldots p_k}{p_1}. \end{align*}To show that this is at most $n$, it suffices to show that $$\frac{p_2\ldots p_k}{p_1} \geq 2^{k-1} \impliedby p_3\ldots p_k \geq 2^{k-1}$$as $p_2>p_1$. Since $p_3>4$ and $p_i>2$ for all $i \geq 4$, this is true by induction, so we are done. $\blacksquare$ v_Enhance wrote: If $p_1 = 2$, then one can show by induction that $p_2 p_3 \dots p_k \ge 2^{k+1}-1$, which implies the result. If $p_1 > 2$, then one can again show by induction $p_3 \dots p_k \ge 2^k-1$ (since $p_3 \ge 7$), which also implies the result. Am I tripping or are you instead proving that $\frac{p_2\ldots p_k}{p_1}\geq 2^k$?

The answer is all prime powers. The number of numbers at most $k$ that are not coprime to $n$ is at least $k \left(1 - \prod_{p \mid n} (1 - \frac{1}{p})\right) - 1$ by partial sums. Rearranging, we must have $1 + k \prod_{p \mid n} (1 - \frac{1}{p}) \geq n$ if $k$ is $n$th smallest positive integer relatively prime to $n$. So $k \geq \frac{n^2-n}{\phi(n)}$ for all $n$. If $n$ is a not a prime power, I claim $\frac{n^2-n}{\phi(n)} > \sigma(n)$. This rearranges to $1 - \frac{1}{n} > \prod_{p_i \mid n} (1 - \frac{1}{p_i^{\alpha_i+1}})$ Let $p_1$ be the smallest prime, then since $1 - \frac{1}{n} > 1 - \frac{1}{p_i^{\alpha_i} \cdot p_i} > \prod_{p_i \mid n} (1 - \frac{1}{p_i^{\alpha_i+1}})$ we are done, so $k > \sigma(n)$ as desired. If $n = p^a$ is a prime power then $k = \frac{p}{p-1} (p^a - 1) + 1 = 1+p+p^2+\ldots + p^a$, giving equality as desired.

Let $\omega(n)$ denote the number of positive integers $k$ where $k \leq \sigma(n)$ and $\gcd(k,n)=1$. It is sufficient to show that $\omega(n) \leq n$. Indeed, notice that the number of positive integers in the interval $[m,m+\ell-1]$ relatively prime to $\ell$ is exactly $\varphi(\ell)$. Now split up the interval $[1,\sigma(n)]$ into the intervals \[ \bigcup_{i=0}^{k-1} \left [ \left ( \sum_{x=1}^{k-1}d_x \right )+1, \sum_{y=1}^{k}d_y \right ] \]where $d_0=0$ and $d_1<d_2< \cdots <d_k$ are the divisors of $n$. Now, notice that if \[ r \in \left [ \left ( \sum_{x=1}^{m-1}d_x \right )+1, \sum_{y=1}^{m}d_y \right ] := I\]and $\gcd(r,n)=1$ then $\gcd(r,d_m)=1$. But the number of integers in $I$ relatively prime to $d_m$ is $\varphi(d_m)$. So, \[ \omega(n) \leq \sum_{i=1}^k \varphi(d_i)=n \]as desired. Equality holds if $\left [ \left ( \sum_{x=1}^{m-1}d_x \right )+1, \sum_{y=1}^{m}d_y \right ]$ has exactly $\varphi(d_m)$ elements relatively prime to $n$ for every $m \leq k$. So, $n$ can only have one distinct prime divisor. Implying $n=p^\alpha$ which clearly works.

wait this solution is absolutely disgusting Observe that for any $d$, among $d$ consecutive integers, there are exactly $\phi(d)$ integers that are relatively prime to $d$. In particular, we can arrange the divisors of $n$ as $n = d_1 > d_2 > \cdots > d_k = 1$ and partition $\{1, 2, \dots, \sigma(n)\}$ into $k$ sets of the form $S_i = \{d_1+d_2+\cdots+d_i+1, \dots, d_1+d_2+\cdots+d_i+d_{i+1}\}$ for each $i$, where $d_0 = 0$. Then for $\Phi(S)$ the number of elements of $S$ relatively prime to $n$, we have \begin{align*} \Phi([\sigma(n)]) &= \Phi(S_0)+\Phi(S_1) + \cdots + \Phi(S_{k-1}) \\ &\leq \phi(d_1)+\phi(d_2)+\cdots+\phi(d_k) = n \end{align*}which finishes the proof. Equality holds if and only if $\Phi(S_i) = \phi(d_{i+1})$ for each $i$, which stipulates that $n$ is a prime power.

Let's denote with $f(m,n)$ - # of $x$ s.t. $x\leq m, gcd(x,n)=1$. Obviously when fixing $n$ $f$ becomes an increasing function. We now want to prove that if $f(m_0,n)=n$, then $m_0\geq \sigma(n)$ or to show that $n=f(m_0,n)\geq f(\sigma(n),n)$. Let $n=p_1^{a_1}\ldots p_k^{a_k}$. The explisit formula for $f(m,n)$ is: $$f(m,n)= \sum_{r=1}^{n} (-1)^{r+1}(\sum_{1\leq i_1\leq \ldots \leq i_r \leq k} \lfloor \frac{m}{p_{i_1}p_{i_2}\ldots p_{i_r}} \rfloor) $$So: $$f(m,n)\leq v_k+\sum_{r=1}^{n} (-1)^{r+1}(\sum_{1\leq i_1\leq \ldots \leq i_r \leq k} \frac{m}{p_{i_1}p_{i_2}\ldots p_{i_r}})$$where $v_k=\sum_{j=0}^{\lfloor\frac{k}{2}\rfloor} \binom{k}{2j+1}$ For $k=1$ one can easily check that $m_0=p\frac{p_1^{a_1}-1}{p_1-1}+1=\sigma(p_1^{a_1})$, hence equality holds. So it is sufficient to show for $k\geq 2$ that: $$n\geq v_k+\sum_{r=1}^{n} (-1)^{r+1}(\sum_{1\leq i_1\leq \ldots \leq i_r \leq k} \frac{\sigma(n)}{p_{i_1}p_{i_2}\ldots p_{i_r}})=$$$$=v_k+\sigma(n)\frac{(p_1-1)(p_2-1)\ldots(p_k-1)}{p_1p_2\ldots p_k}=v_k+\frac{(p_1^{a_1+1}-1)(p_2^{a_2+1}-1)\ldots(p_k^{a_k+1}-1)}{p_1p_2\ldots p_k} \Leftrightarrow$$$$\frac{p_1^{a_1+1}p_2^{a_2+1}\ldots p_k^{a_k+1}-(p_1^{a_1+1}-1)(p_2^{a_2+1}-1)\ldots(p_k^{a_k+1}-1)}{p_1p_2\ldots p_k}\geq v_k$$ We will prove the last by induction on $k$, when we order $p_1\leq p_2 \leq \cdots \leq p_k$: Base case is $k=2$ where we need to show that $p_1^{a_1+1}+p_2^{a_1+1}-1\geq 2p_1p_2$. This is true as: $$p_1^{a_1+1}+p_2^{a_1+1}-1\geq p_1^{2}+p_2^{2}-1\geq 2p_1p_2$$In the last equality can only hold when $n=6$, which checking in the original we see that equality does not in fact hold. Induction step for $k+1$. Denote $A=p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}$, $B=\frac{(p_1^{a_1+1}-1)(p_2^{a_2+1}-1)\ldots(p_k^{a_k+1}-1)}{p_1p_2\ldots p_k}$, $A'= p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}p_{k+1}^{a_{k+1}}$, $B'=\frac{(p_1^{a_1+1}-1)(p_2^{a_2+1}-1)\ldots(p_k^{a_k+1}-1)(p_{k+1}^{a_{k+1}}-1)}{p_1p_2\ldots p_kp_{k+1}}$. So: $$A'-B'=p_{k+1}^{a_{k+1}}A-p_{k+1}^{a_{k+1}}B+\frac{1}{p_{k+1}}B>p_{k+1}^{a_{k+1}}(A-B)\geq p_{k+1}^{a_{k+1}}v_k\geq 5v_k $$It is now left to show that $5v_k>v_{k+1}$. It is well-known that $v_t=2^{t-1}$, so it is sufficient to prove $5\cdot 2^{k-1}>2^{k}$, which follows from the fact that $5>2$

Equality holds at powers of primes. From now on, assume that $n=p_1^{e_1}\dots P_k^{e_k}$ has more than $1$ prime factor. Then, the number of integers under $\sigma(n)$ relatively prime to $n$ is \[\sum_{S \subseteq \{1,\dots, k\}}(-1)^{|S|} \left \lfloor \frac{\sigma(n)}{\prod_{i \in S} p_i} \right \rfloor \leq 2^{k-1} + \sum_{S \subseteq \{1,\dots, k\}}(-1)^{|S|} \frac{\sigma(n)}{\prod_{i \in S} p_i} \]where we bounded $\lfloor x \rfloor\leq x$ and $-\lfloor x \rfloor\leq -x+1$. Simplifying, we get that it suffices to show $2^{k-1}+\prod_{i=1}^k \left(p_i^{e_i}-\frac{1}{p_i}\right) \leq n$. Claim: This holds when $e_i=1$ for all $i$. Proof. We induct on $k$. The base case follows since $\frac{p_1}{p_2}+\frac{p_2}{p_1}-\frac{1}{p_1p_2}\geq 2$. For the inductive step, note that \[\prod_{i=1}^k p_i = p_k\prod_{i=1}^{k-1}p_i \geq p_k\left(2^{k-2}+\prod_{i=1}^{k-1}(p_i-\tfrac{1}{p_i})\right) \geq 2^{k-1}+\prod_{i=1}^{k}(p_i-\tfrac{1}{p_i})\]$\blacksquare$ Claim: The inequality holds for all $n$. Proof. We induct from $\prod_{i=1}^k p_i^{e_i}$ to $p\prod_{i=1}^k p_i^{e_i}$. The base cases were checked in the last claim. To complete the induction, we observe \begin{align*} & 2^{k-1}+(p_{1}^{e_1+1}-\tfrac{1}{p_1})\prod_{i=2}^k(p_i^{e_i}-\tfrac{1}{p_i}) \\ &=2^{k-1}+\prod_{i=1}^k(p_i^{e_i}-\tfrac{1}{p_i})+ (p_{1}^{e_1+1}-p_1^{e_i})\prod_{i=2}^k(p_i^{e_i}-\tfrac{1}{p_i}) \\ &<\left(\prod_{i=1}^kp_i^{e_i}\right)+ (p_{1}^{e_1+1}-p_1^{e_i})\prod_{i=2}^k p_i^{e_i} \\ &=p\prod_{i=1}^k p_i^{e_i} \end{align*}$\blacksquare$