USA TST 2018/P1: Prove that the $n^{\text{th}}$ smallest positive integer relatively prime to $n$ is at least $\sigma(n)$

The second hint is a beautiful hint. I will just add that:

$\phi(m)$ is the number of integers coprime to $m$ in any $m$ consecutive integers.

and use the first hint to cover the interval $n+1,n+2,\dots,\sigma(n)$. Note that any number coprime to $n$ must be coprime to all divisors of $n$.

Your $2^{nd}$ hint can be written as below

Claim: If $k$ and $m$ are positive integers then the number of integers in the interval $[k,k+m-1]$ which are coprime to $m$ is exactly $\varphi(m)$ where $\varphi$ is the Euler's Totient function.

Proof (sketch): It's an easy observation that $\{k,k+1,\ldots,k+m-1\}$ is a complete residue class modulo $m$. Therefore there is a one-to-one correspondence between the positive integers in $\{0,1,2,\ldots,m-1\}$ which are coprime to $m$ and the positive integers in $\{k,k+1,\ldots,k+m-1\}$ which are coprime to $m$. Therefore the claim follows.

To show that the $n^{th}$ smallest positive integer which is relatively prime to $n$ is at least $\sigma(n)$ it is enough to show that the number of integers in the interval $[1,\sigma(n)]$, which are relatively prime to $n$, is at most $n$. Let $\tau(n)=k$, where $\tau(n)$ denotes the number of positive divisors of $n$ including $n$ and $1$. Let $$1=d_1<d_2<\cdots<d_k=n$$ be the $k$ divisors. Then $$\sigma(n)=d_1+d_2+\cdots+d_k$$ We partition the interval $[1,\sigma(n)]$ in the following way,

$$[1,\sigma(n)]=I_1\cup I_2\cup\cdots\cup I_k$$

where,

$$I_1=[1,d_1]\\I_2=[d_1+1,d_1+d_2]\\I_3=[d_1+d_2+1,d_1+d_2+d_3]\\\vdots\\I_k=[d_1+d_2+\cdots+d_{k-1}+1,d_1+d_2+\cdots+d_k]=[d_1+d_2+\cdots+d_{k-1}+1,\sigma(n)]$$

Note that $I_j$ has length $d_j$ for $1\leq j\leq k$. Now by the claim above, the number of positive integers in the interval $I_j$ which are coprime to $d_j$ is exactly $\varphi(d_j)$. Since the intervals, $I_j$'s are pairwise disjoint and the positive integers which are relatively prime to $n$ are exactly those which are coprime to all of its divisors, we have the number of positive integers in the interval $[1,\sigma(n)]$ is at most $$\sum_{j=1}^{k}\varphi(d_j)=\sum_{d\mid n}\varphi(d)=n$$ Hence we are done!