Lower bound for integer relatively prime to n

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

22 users

TOPICS

No tags match your search

M

No tags match your search

M

Lower bound for integer relatively prime to n

G H J

Reveal topic tags

relatively prime

Arithmetic Functions

L

G H BBookmark kLocked kLocked NReply

Source: USA Winter Team Selection Test #1 for IMO 2018, Problem 1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3564 posts

62861

#1 h Dec 11, 2017, 5:00 PM • 21 Y

Y by tenplusten, GeniusF, Davi-8191, Kayak, yayups, Giffunk, eisirrational, anantmudgal09, rkm0959, acegikmoqsuwy2000, atmchallenge, cookie112, Mathuzb, Gaussian_cyber, megarnie, centslordm, Adventure10, Mango247, kiyoras_2001, cadaeibf, cubres

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

This post has been edited 3 times. Last edited by 62861, Dec 11, 2017, 5:07 PM
Reason: proposer

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

402 posts

GGPiku

#2 h Dec 11, 2017, 7:04 PM • 3 Y

Y by Adventure10, Mango247, cubres

I tried

This post has been edited 6 times. Last edited by GGPiku, Dec 11, 2017, 7:37 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1614 posts

yayups

#3 h Dec 11, 2017, 7:06 PM • 3 Y

Y by Adventure10, Mango247, cubres

GGPiku wrote:

Please check if my solution is correct...
In honor of Mister Aiscrim

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.

This post has been edited 4 times. Last edited by yayups, Dec 11, 2017, 7:10 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1614 posts

yayups

#4 h Dec 11, 2017, 7:13 PM • 2 Y

Y by Adventure10, cubres

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

223 posts

#7 h Dec 11, 2017, 7:33 PM • 25 Y

Y by GGPiku, ThE-dArK-lOrD, laegolas, tapir1729, talkon, trumpeter, yiwen, B.J.W.T, cookie112, nmd27082001, zephyr7723, SeanGee, Anar24, lminsl, mathleticguyyy, JTY26, Math_Is_Fun_101, guptaamitu1, CyclicISLscelesTrapezoid, IAmTheHazard, Kobayashi, rayfish, Adventure10, Mango247, cubres

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

This post has been edited 2 times. Last edited by a1267ab, Dec 11, 2017, 7:35 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4071 posts

#8 h Dec 11, 2017, 8:25 PM • 7 Y

Y by Tawan, enhanced, magicarrow, Adventure10, Mango247, cubres, MS_asdfgzxcvb

Don't underestimate algebraic method!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1979 posts

#9 h Dec 11, 2017, 8:27 PM • 5 Y

Y by Tawan, Anar24, starchan, Adventure10, cubres

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6857 posts

#10 h Dec 12, 2017, 1:18 AM • 23 Y

Y by rafayaashary1, anantmudgal09, baopbc, cookie112, nmd27082001, Anar24, huricane, ShamimAkhtar212, BobaFett101, alifenix-, TAMREF, fukano_2, amuthup, v4913, JTY26, mijail, HamstPan38825, L567, Kobayashi, Adventure10, Mango247, cubres, MS_asdfgzxcvb

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

641 posts

tree3

#11 h Dec 12, 2017, 2:01 AM • 3 Y

Y by Tawan, Adventure10, cubres

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.

This post has been edited 2 times. Last edited by tree3, Dec 12, 2017, 3:47 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1247 posts

#13 h Jun 9, 2018, 3:22 AM • 4 Y

Y by L567, Adventure10, Mango247, cubres

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.

This post has been edited 2 times. Last edited by Th3Numb3rThr33, Jun 22, 2018, 4:37 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

779 posts

#15 h Sep 13, 2020, 4:43 PM • 1 Y

Y by cubres

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.

This post has been edited 2 times. Last edited by amuthup, Sep 13, 2020, 4:45 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

308 posts

#16 h Sep 14, 2020, 11:59 AM • 1 Y

Y by cubres

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 post has been edited 1 time. Last edited by mathaddiction, Sep 14, 2020, 11:59 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

206 posts

#17 h Nov 9, 2020, 2:53 AM • 4 Y

Y by Mango247, Mango247, Mango247, cubres

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.

Motivation

This post has been edited 2 times. Last edited by Idio-logy, Nov 9, 2020, 2:55 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1065 posts

Eyed

#18 h Nov 14, 2020, 3:58 PM • 1 Y

Y by cubres

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

478 posts

#19 h Sep 7, 2021, 3:44 AM • 1 Y

Y by cubres

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

This post has been edited 1 time. Last edited by Sprites, Sep 7, 2021, 10:51 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2726 posts

#20 h Sep 26, 2021, 5:14 PM • 1 Y

Y by cubres

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

This post has been edited 1 time. Last edited by jj_ca888, Sep 26, 2021, 5:14 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

579 posts

#21 h Dec 26, 2021, 12:00 AM • 1 Y

Y by cubres

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5000 posts

#22 h Aug 26, 2022, 8:14 PM • 1 Y

Y by cubres

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1455 posts

#23 h Nov 13, 2022, 3:28 AM • 1 Y

Y by cubres

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

302 posts

#24 h Nov 19, 2022, 8:25 PM • 3 Y

Y by teomihai, kiyoras_2001, cubres

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8846 posts

#25 h Aug 19, 2024, 7:35 PM • 1 Y

Y by cubres

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

130 posts

#26 h Oct 14, 2024, 6:28 AM • 1 Y

Y by cubres

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

812 posts

#27 h Nov 26, 2024, 5:24 PM • 1 Y

Y by ihatemath123

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1484 posts

#28 h Yesterday at 6:12 AM • 1 Y

Y by MS_asdfgzxcvb

ok ban bashers

We first show the inequality.

Claim: For any divisor $d > 1$ of $n$ , there are at least $\frac{n}{d}$ integers $x$ below $\sigma(n)$ such that $\gcd(x, n) = d$ .
Proof. Split $\sigma(n)$ into segments of divisors of length $i$ for each $i \mid n$ . Then for each $i = dk$ , we have $\varphi(k)$ elements of that segment satisfying this property.
As such, the number of elements is at least $\sum_{d \mid i \mid n} \varphi\left(\frac{i}{d}\right) = \sum_{i \mid \frac{n}{d}} \varphi\left(j\right) = 1 \star \varphi \left(\frac{n}{d}\right) = \frac{n}{d}.$ $\blacksquare$
As such, the number of non-coprime elements less than $\sigma(n)$ is at least $\sum_{d \mid n, d > 1} \frac{n}{d} = \sigma(n) - n$ so the $n$ th smallest positive integer is at least $\sigma(n)$ .
Now, equality only holds if the remaining segment with total length contain no additional element, so $\sigma(n) - d\sigma\left(\frac{n}{d}\right) \le d$ .
If we take $d = p$ as the smallest prime, then the LHS becomes $\frac{n}{p^{\nu_p(n)}}$ , so for equality to hold $n$ must be a prime power.
Conversely, if $n = p^k$ is a prime power, then there are $1 + p + \dots + p^{k-1}$ multiples of $p$ less than $\sigma(p^k) = 1 + p + \dots + p^{k+1}$ , so the $p^k$ th relatively prime element is in fact $\sigma(p^k)$ as desired.

This post has been edited 1 time. Last edited by YaoAOPS, Yesterday at 6:12 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a