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

Question

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.

Thanks in advance.

Answer 1

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 $\sigma(n)=k$. 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!

Answer 2

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

Answer 3

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<d_1<d_2<\dots<d_k<n$ 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<d_1<d_2<\dots<d_k<n$ 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<p_2$, 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!

Answer 4

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.