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

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.

My Progress: Really hard problem!!!

Obviously, I looked at examples!

For n=2, $$\sigma(2)=3$$ and the second positive relatively prime to 2 was 3.

For n=3, $$\sigma(3)=4$$ and the third positive relatively prime to 3 was 4.

For n=4, $$\sigma(4)=1+2+4=7$$ and the fourth positive relatively prime to 4 was 7.

For n=5, $$\sigma(5)=1+5=6$$ and the fifth positive relatively prime to 5 was 6.

For n=6, $$\sigma(6)=3\cdot 4=12$$ but the sixth positive relatively prime to 6 was 17.

So, from here I conjectured that the equality case is true if and only if $$n =$$ perfect power of a prime.

Firstly, let $$S(n)$$ be the $$n^{\text{th}}$$ smallest positive integer relatively prime to $$n$$.

Now, for $$n=$$ prime.It works, since $$\sigma(n)=p+1$$ and $$S(n)=p+1$$, since only $$p$$ is not relatively prime to $$p$$ and $$p+1$$ is .

Before proceeding further I would like to state the formula which I got and can be proved by induction or just simple modular arithmetic .

For a given integer $$x$$ and a perfect power of prime $$"l^k"$$ . We get that $$x$$ is the $$[x-Q(x,l)]^{\text{th}}$$ number which is relatively prime to $$l^k$$ . where $$Q(x,l)$$ is the quotient when $$x$$ is divided by $$l$$.

Now $$n=p^k$$ , for some prime $$p$$ and $$k>1$$.

So we get that, $$\sigma(p^k)= 1+p^2+\dots +p^k$$ .

We claim that $$S(p^k)=1+p^2+\dots +p^k$$ . we can prove this by using the fact that $$S(n)$$ is unique or in other words , we can show that $$1+p^2+\dots +p^k$$ is the $${p^k}^{\text{th}}$$ relatively prime number rather than finding the $${p^k}^{th}$$ relatively prime number .

But by the formula we stated, we get that $$1+p^2+\dots +p^k$$ is the $$[1+p^2+\dots +p^k - Q(1+p^2+\dots +p^k,p)]=[1+p^2+\dots +p^k -(1+p^2+\dots +p^{k-1})]= p^k$$

And we are done!

I am stuck in showing that equality case doesn't for multiples prime .

The handout which I am using, gave these hints for the general problem:

$$1$$. $$\sum_{d|n} \phi(d)=n$$.

$$2$$. We basically reverse construct the $$\sigma(n$$) as the sum of the divisors and construct intervals which each have a different $$d_i$$ number of relatively prime numbers.

I couldn't even understand the $$2^{\text{nd}}$$ hint.

Please give a try to this beautiful problem and hope one can give me hints for this problem.

• Where do you find such beautiful questions? Jul 31 '20 at 16:53
• @Arjun All the credit goes to my mentor! Jul 31 '20 at 16:59
• @Shubhangi I am encountering frequent posts from you (this is the 3rd today I think!). Are you sure that you are giving a sufficient amount of time to solve a single problem? When you are stuck, you should spend at least a week for one single problem. Don't hurry and try to solve a problem completely by yourself. In every post, I can see that you are approaching the problem in the right way, which will definitely lead you to the full solution if you spend more time on it. Before making the next post in MSE please solve an EGMO or a USAMO/USAJMO problem completely yourself without any hints😊 Jul 31 '20 at 17:30
• @ShubhrajitBhattacharya you are right, I guess I should spend at least 2 days on a single problem. Aug 1 '20 at 1:10
• @Shubhangi thanks that you agreed with me. You are doing fine with Olympiad problems. Starting to solve a problem in the right direction is very important and I have seen that you did that yourself everytime. No doubt that you're brilliant. Just spend more and more time with problems😊 Aug 1 '20 at 1:31

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 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!

• Beautiful solution!! I also got this solution! But of course your writing style is perfect ! I learned a lot! thanks. Aug 3 '20 at 11:00
• Thanks @Shubhangi! I am glad that you solved this problem yourself spending 2 days without looking at my solution. I have read your solution. Your writing is complete and every step is well-interpreted. This is needed when you will write a solution in the exam. Best of luck, you will definitely succeed in your Olympiad journey. 👍 Aug 3 '20 at 13:39
• @Shubhangi try this problem: Prove that, for any positive integer $N$, there exists an integer $k=k(N)$, such that we can find more than $N$ primes, which can be written as $a^2+k$, for natural numbers $a$. Aug 4 '20 at 7:03
• I will surely try ! Aug 4 '20 at 16:40
• You are not quite done yet. You have shown that there are at most $n$ integers coprime to $n$ in the interval $[1,\sigma(n)]$, but if it happened that there are exactly $n$, and $\gcd(n,\sigma(n)) > 1$, then the $n^{\text{th}}$ positive integer coprime to $n$ would be smaller than $\sigma(n)$. Thus it remains to show this can't happen. This is done (with a minuscule glitch) in @SunainaPati's answer. Oct 16 '20 at 19:15

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

• Thank you so much, I got it ! The second hint is just so beautiful! It reminded me to re-read David burton's book :) Aug 3 '20 at 10:58

Finally got the proof! Took me almost 2 days to solve. The hint was almost everything .

Here is the full solution which I got.

Proof: Let $$1 be the divisors of $$n$$ .

Note that $$\sigma (n) = 1+d_1+\dots + n$$.

Now, Consider the following partitions

$$P_1= [1,d_1]$$

$$P_2= [1+d_1,\cdots , d_1+d_2]$$

.

.

.

$$P_{k+1}= [1+d_1+d_2 +\cdots d_k, \cdots, 1+d_1+d_2 +\cdots d_k+n]= [1+d_1+d_2 +\cdots d_k, \cdots, \sigma (n)]$$

Note that in each partition $$P_i$$ is of length $$d_i$$.

Also note that there are at most $$\phi (d_i)$$ numbers in the partition $$P_i$$ which are relatively prime to $$n$$. ( since $$\phi(m)$$ is the number of integers coprime to $$m$$ in any $$m$$ consecutive integers )

Hence, between $$1$$ to $$d_1+d_2\cdots d_k=\sigma(n)$$ , there are at most $$\sum_{d \mid n} \varphi(d) = n$$ numbers which are relatively prime to $$n$$ .

This proves the main part of the problem!

Now, the equality case .

We claim that the equality case holds true if and only if $$n=$$ perfect power of a prime.

First, we will show that $$n=$$ perfect power of a prime.

let $$S(n)$$ be the $$n^{\text{th}}$$ smallest positive integer relatively prime to $$n$$.

Now, for $$n=$$ prime. It works, since $$\sigma(n)=p+1$$ and $$S(n)=p+1$$, since only $$p$$ is not relatively prime to $$p$$ and $$p+1$$ is .

Consider the following proposition, which can be proved by induction or modular arithmetic.

For a given integer $$x$$ and a perfect power of prime $$"l^k"$$ . We get that $$x$$ is the $$[x-Q(x,l)]^{\text{th}}$$ number which is relatively prime to $$l^k$$ ,where $$Q(x,l)$$ is the quotient when $$x$$ is divided by $$l$$.

Now $$n=p^k$$ , for some prime $$p$$ and $$k>1$$.

So we get that, $$\sigma(p^k)= 1+p^2+\dots +p^k$$ .

We claim that $$S(p^k)=1+p^2+\dots +p^k$$ . we can prove this by using the fact that $$S(n)$$ is unique or in other words , we can show that $$1+p^2+\dots +p^k$$ is the $${p^k}^{\text{th}}$$ relatively prime number rather than finding the $${p^k}^{th}$$ relatively prime number .

But by the formula we stated, we get that $$1+p^2+\dots +p^k$$ is the $$[1+p^2+\dots +p^k - Q(1+p^2+\dots +p^k,p)]=[1+p^2+\dots +p^k -(1+p^2+\dots +p^{k-1})]= p^k$$

And we are done for this part .

Now, we will show that if n is a product of multiple distinct primes , then the equality case does not hold.

Let $$n={p_1}^{\alpha_1}\cdot{p_2}^{\alpha_2}\cdot X$$ , where gcd$$(p_1,X)=1$$ and gcd$$(p_2,X)=1$$; and $$p_1$$ and $$p_2$$ are primes .

Proceeding by the similar construction like we did for the main proof,

let $$1 be the divisors of $$n$$ .

Note that $$\sigma (n) = 1+d_1+\dots + n$$.

Now, Consider the following partitions

$$P_1= [1,d_1]$$

$$P_2= [1+d_1,\cdots ,d_1+d_2]$$

.

.

.

$$P_{k+1}= [1+d_1+d_2 +\cdots d_k, \cdots, 1+d_1+d_2 +\cdots d_k+n]= [1+d_1+d_2 +\cdots d_k, \cdots, \sigma (n)]$$

Note that here, $$d_1=p_1$$ and $$d_2=p_2$$ .

Now, let us look at partition $$P_2=[1+p_1,\cdots , p_1+p_2]$$ . Since $$p_1, note that $$2p_1$$ will also be there in this partition, . So we have at most $$\phi(p_2)-1$$ numbers from $$P_2$$ which are relatively prime to $$n$$.

Hence between $$1$$ to $$d_1+d_2\cdots d_k=\sigma(n)$$ , there are at most $$\sum_{d \mid n} \varphi(d)-1 = n-1$$ numbers which are relatively prime to $$n$$ .

Hence the $$n^{\text{th}}$$ realtively prime number to $$n$$ will be strictly larger than $$\sigma (n)$$ , if $$n$$ is a multiple of $$2$$ or more primes.

And we are done!

• There's a small inexactness in your argument for the case where $n$ isn't a prime power. You say "let $1 < d_1 < d_2 < \cdots < d_k < n$ be the divisors of $n$", and a bit later "Note that here, $d_1 = p_1$ and $d_2 = p_2$". But that need not be the case, it may well be that $p_1^2 < p_2$ and $p_1^2 \mid n$. However, the argument uses only that each sequence of $d$ consecutive positive integers contains exactly $\varphi(d)$ integers coprime to $d$, so we don't need to consider the divisors in ascending order. Oct 16 '20 at 19:23
• Thus your argument that $[1+p_1, p_1 + p_2]$ contains at most $p_2-2$ integers coprime to $n$ still suffices. Oct 16 '20 at 19:24
• yeah.. i got what you are saying.. i should have been more careful ..thanks ! Oct 17 '20 at 1:38

So, here's my solution without any hints :

Let $$T[x]$$ denote the $$x^{th}$$ smallest natural co-prime to $$x$$.

First we begin by showing that for $$n = p^k$$, equality holds.

In this case, $$T[x] - \lfloor T[x]/p \rfloor = p^k$$. We see that $$\sigma (p)$$ satisfies this equation but moreover, we know that if $$T_{k}[x]$$ denoted the number of naturals which are at least $$k$$ and are co-prime to $$x$$, then $$T_{k}[x]$$ is unique as $$k$$ varies, which finishes our first claim.

Now, a nice part. We will show that $$T_{\sigma (x)}[x] \leq x$$. Let $$d_1, d_2 \dots d_k$$ be divisors of $$x$$. We see that among the first $$d_1$$ naturals, exactly $$\phi (d_1)$$ are co-prime to $$d_1$$ and so at most $$\phi ( d_1)$$ co-prime to $$x$$. Then we consider $$[d_1 + 1, d_1 + d_2]$$ for $$d_2$$ and so on. Hence $$T_{\sigma (x)}[x] \leq \sum_{p \mid x} \phi (p) = x$$ and clearly equality will hold if and only if $$\Omega (x) = 1$$. Why? Consider if $$d_t$$ is a prime less than $$d_j$$ which is another prime and both of them dividing $$x$$ and consider the interval of $$d_j$$, in the interval, at most $$\phi (d_j) - 1$$ naturals will be co-prime to $$x$$ and we're done.