We have your learning goals covered with Spring and Summer courses available. Enroll today!

G
Topic
First Poster
Last Poster
k a March Highlights and 2025 AoPS Online Class Information
jlacosta   0
Mar 2, 2025
March is the month for State MATHCOUNTS competitions! Kudos to everyone who participated in their local chapter competitions and best of luck to all going to State! Join us on March 11th for a Math Jam devoted to our favorite Chapter competition problems! Are you interested in training for MATHCOUNTS? Be sure to check out our AMC 8/MATHCOUNTS Basics and Advanced courses.

Are you ready to level up with Olympiad training? Registration is open with early bird pricing available for our WOOT programs: MathWOOT (Levels 1 and 2), CodeWOOT, PhysicsWOOT, and ChemWOOT. What is WOOT? WOOT stands for Worldwide Online Olympiad Training and is a 7-month high school math Olympiad preparation and testing program that brings together many of the best students from around the world to learn Olympiad problem solving skills. Classes begin in September!

Do you have plans this summer? There are so many options to fit your schedule and goals whether attending a summer camp or taking online classes, it can be a great break from the routine of the school year. Check out our summer courses at AoPS Online, or if you want a math or language arts class that doesn’t have homework, but is an enriching summer experience, our AoPS Virtual Campus summer camps may be just the ticket! We are expanding our locations for our AoPS Academies across the country with 15 locations so far and new campuses opening in Saratoga CA, Johns Creek GA, and the Upper West Side NY. Check out this page for summer camp information.

Be sure to mark your calendars for the following events:
[list][*]March 5th (Wednesday), 4:30pm PT/7:30pm ET, HCSSiM Math Jam 2025. Amber Verser, Assistant Director of the Hampshire College Summer Studies in Mathematics, will host an information session about HCSSiM, a summer program for high school students.
[*]March 6th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar on Math Competitions from elementary through high school. Join us for an enlightening session that demystifies the world of math competitions and helps you make informed decisions about your contest journey.
[*]March 11th (Tuesday), 4:30pm PT/7:30pm ET, 2025 MATHCOUNTS Chapter Discussion MATH JAM. AoPS instructors will discuss some of their favorite problems from the MATHCOUNTS Chapter Competition. All are welcome!
[*]March 13th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar about Summer Camps at the Virtual Campus. Transform your summer into an unforgettable learning adventure! From elementary through high school, we offer dynamic summer camps featuring topics in mathematics, language arts, and competition preparation - all designed to fit your schedule and ignite your passion for learning.[/list]
Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Sunday, Mar 2 - Jun 22
Friday, Mar 28 - Jul 18
Sunday, Apr 13 - Aug 10
Tuesday, May 13 - Aug 26
Thursday, May 29 - Sep 11
Sunday, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
Wednesday, Jul 16 - Oct 29

Prealgebra 2 Self-Paced

Prealgebra 2
Tuesday, Mar 25 - Jul 8
Sunday, Apr 13 - Aug 10
Wednesday, May 7 - Aug 20
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
Friday, Jul 25 - Nov 21


Introduction to Algebra A Self-Paced

Introduction to Algebra A
Sunday, Mar 23 - Jul 20
Monday, Apr 7 - Jul 28
Sunday, May 11 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, May 14 - Aug 27
Friday, May 30 - Sep 26
Monday, Jun 2 - Sep 22
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
Tuesday, Jul 15 - Oct 28

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Sunday, Mar 16 - Jun 8
Wednesday, Apr 16 - Jul 2
Thursday, May 15 - Jul 31
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Wednesday, Jul 9 - Sep 24
Sunday, Jul 27 - Oct 19

Introduction to Number Theory
Monday, Mar 17 - Jun 9
Thursday, Apr 17 - Jul 3
Friday, May 9 - Aug 1
Wednesday, May 21 - Aug 6
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
Tuesday, Jul 15 - Sep 30

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Sunday, Mar 2 - Jun 22
Wednesday, Apr 16 - Jul 30
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Tuesday, Mar 4 - Aug 12
Sunday, Mar 23 - Sep 21
Wednesday, Apr 23 - Oct 1
Sunday, May 11 - Nov 9
Tuesday, May 20 - Oct 28
Monday, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
Monday, Jul 14 - Jan 19

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Mar 16 - Sep 14
Tuesday, Mar 25 - Sep 2
Monday, Apr 21 - Oct 13
Sunday, Jun 1 - Nov 23
Tuesday, Jun 10 - Nov 18
Wednesday, Jun 25 - Dec 10
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22

Intermediate Counting & Probability
Sunday, Mar 23 - Aug 3
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Friday, Apr 11 - Jun 27
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Sunday, Mar 16 - Aug 24
Wednesday, Apr 9 - Sep 3
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Wednesday, Mar 5 - May 21
Tuesday, Jun 10 - Aug 26

Calculus
Sunday, Mar 30 - Oct 5
Tuesday, May 27 - Nov 11
Wednesday, Jun 25 - Dec 17

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Sunday, Mar 23 - Jun 15
Wednesday, Apr 16 - Jul 2
Friday, May 23 - Aug 15
Monday, Jun 2 - Aug 18
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

MATHCOUNTS/AMC 8 Advanced
Friday, Apr 11 - Jun 27
Sunday, May 11 - Aug 10
Tuesday, May 27 - Aug 12
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Problem Series
Tuesday, Mar 4 - May 20
Monday, Mar 31 - Jun 23
Friday, May 9 - Aug 1
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Tuesday, Jun 17 - Sep 2
Sunday, Jun 22 - Sep 21 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Jun 23 - Sep 15
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Final Fives
Sunday, May 11 - Jun 8
Tuesday, May 27 - Jun 17
Monday, Jun 30 - Jul 21

AMC 12 Problem Series
Tuesday, May 27 - Aug 12
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Wednesday, Aug 6 - Oct 22

AMC 12 Final Fives
Sunday, May 18 - Jun 15

F=ma Problem Series
Wednesday, Jun 11 - Aug 27

WOOT Programs
Visit the pages linked for full schedule details for each of these programs!


MathWOOT Level 1
MathWOOT Level 2
ChemWOOT
CodeWOOT
PhysicsWOOT

Programming

Introduction to Programming with Python
Monday, Mar 24 - Jun 16
Thursday, May 22 - Aug 7
Sunday, Jun 15 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Tuesday, Jun 17 - Sep 2
Monday, Jun 30 - Sep 22

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22

USACO Bronze Problem Series
Tuesday, May 13 - Jul 29
Sunday, Jun 22 - Sep 1

Physics

Introduction to Physics
Sunday, Mar 30 - Jun 22
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Tuesday, Mar 25 - Sep 2
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Sat & Sun, Apr 26 - Apr 27 (4:00 - 7:00 pm ET/1:00 - 4:00pm PT)
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
Mar 2, 2025
0 replies
k i Adding contests to the Contest Collections
dcouchman   1
N Apr 5, 2023 by v_Enhance
Want to help AoPS remain a valuable Olympiad resource? Help us add contests to AoPS's Contest Collections.

Find instructions and a list of contests to add here: https://artofproblemsolving.com/community/c40244h1064480_contests_to_add
1 reply
dcouchman
Sep 9, 2019
v_Enhance
Apr 5, 2023
k i Zero tolerance
ZetaX   49
N May 4, 2019 by NoDealsHere
Source: Use your common sense! (enough is enough)
Some users don't want to learn, some other simply ignore advises.
But please follow the following guideline:


To make it short: ALWAYS USE YOUR COMMON SENSE IF POSTING!
If you don't have common sense, don't post.


More specifically:

For new threads:


a) Good, meaningful title:
The title has to say what the problem is about in best way possible.
If that title occured already, it's definitely bad. And contest names aren't good either.
That's in fact a requirement for being able to search old problems.

Examples:
Bad titles:
- "Hard"/"Medium"/"Easy" (if you find it so cool how hard/easy it is, tell it in the post and use a title that tells us the problem)
- "Number Theory" (hey guy, guess why this forum's named that way¿ and is it the only such problem on earth¿)
- "Fibonacci" (there are millions of Fibonacci problems out there, all posted and named the same...)
- "Chinese TST 2003" (does this say anything about the problem¿)
Good titles:
- "On divisors of a³+2b³+4c³-6abc"
- "Number of solutions to x²+y²=6z²"
- "Fibonacci numbers are never squares"


b) Use search function:
Before posting a "new" problem spend at least two, better five, minutes to look if this problem was posted before. If it was, don't repost it. If you have anything important to say on topic, post it in one of the older threads.
If the thread is locked cause of this, use search function.

Update (by Amir Hossein). The best way to search for two keywords in AoPS is to input
[code]+"first keyword" +"second keyword"[/code]
so that any post containing both strings "first word" and "second form".


c) Good problem statement:
Some recent really bad post was:
[quote]$lim_{n\to 1}^{+\infty}\frac{1}{n}-lnn$[/quote]
It contains no question and no answer.
If you do this, too, you are on the best way to get your thread deleted. Write everything clearly, define where your variables come from (and define the "natural" numbers if used). Additionally read your post at least twice before submitting. After you sent it, read it again and use the Edit-Button if necessary to correct errors.


For answers to already existing threads:


d) Of any interest and with content:
Don't post things that are more trivial than completely obvious. For example, if the question is to solve $x^{3}+y^{3}=z^{3}$, do not answer with "$x=y=z=0$ is a solution" only. Either you post any kind of proof or at least something unexpected (like "$x=1337, y=481, z=42$ is the smallest solution). Someone that does not see that $x=y=z=0$ is a solution of the above without your post is completely wrong here, this is an IMO-level forum.
Similar, posting "I have solved this problem" but not posting anything else is not welcome; it even looks that you just want to show off what a genius you are.

e) Well written and checked answers:
Like c) for new threads, check your solutions at least twice for mistakes. And after sending, read it again and use the Edit-Button if necessary to correct errors.



To repeat it: ALWAYS USE YOUR COMMON SENSE IF POSTING!


Everything definitely out of range of common sense will be locked or deleted (exept for new users having less than about 42 posts, they are newbies and need/get some time to learn).

The above rules will be applied from next monday (5. march of 2007).
Feel free to discuss on this here.
49 replies
ZetaX
Feb 27, 2007
NoDealsHere
May 4, 2019
chat gpt
fuv870   6
N a minute ago by jkim0656
The chat gpt alreadly knows how to solve the problem of IMO USAMO and AMC?
6 replies
+1 w
fuv870
3 hours ago
jkim0656
a minute ago
Unsolved Diophantine(I think)
Nuran2010   2
N 4 minutes ago by ohiorizzler1434
Find all solutions for the equation $2^n=p+3^p$ where $n$ is a positive integer and $p$ is a prime.(Don't get mad at me,I've used the search function and did not see a correct and complete solution anywhere.)
2 replies
Nuran2010
Mar 14, 2025
ohiorizzler1434
4 minutes ago
Functional Equations Marathon March 2025
Levieee   0
11 minutes ago
1. before posting another problem please try your best to provide the solution to the previous solution because we don't want a backlog of many problems
2.one is welcome to send functional equations involving calculus (mainly basic real analysis type of proofs) as long it is of the form $\text{"find all functions:"}$
0 replies
1 viewing
Levieee
11 minutes ago
0 replies
Another NT FE
nukelauncher   60
N 24 minutes ago by pi271828
Source: ISL 2019 N4
Find all functions $f:\mathbb Z_{>0}\to \mathbb Z_{>0}$ such that $a+f(b)$ divides $a^2+bf(a)$ for all positive integers $a$ and $b$ with $a+b>2019$.
60 replies
nukelauncher
Sep 22, 2020
pi271828
24 minutes ago
Perfect Squares, Infinite Integers and Integers
steven_zhang123   4
N 38 minutes ago by ohiorizzler1434
Source: China TST 2001 Quiz 5 P1
For which integer \( h \), are there infinitely many positive integers \( n \) such that \( \lfloor \sqrt{h^2 + 1} \cdot n \rfloor \) is a perfect square? (Here \( \lfloor x \rfloor \) denotes the integer part of the real number \( x \)?
4 replies
steven_zhang123
Yesterday at 12:06 PM
ohiorizzler1434
38 minutes ago
another geometry problem with sharky-devil point
anyone__42   11
N 40 minutes ago by zhenghua
Source: The francophone mathematical olympiads P1
Let $ABC$ be an acute triangle with $AC>AB$, Let $DEF$ be the intouch triangle with $D \in (BC)$,$E \in (AC)$,$F \in (AB)$,, let $G$ be the intersecttion of the perpendicular from $D$ to $EF$ with $AB$, and $X=(ABC)\cap (AEF)$.
Prove that $B,D,G$ and $X$ are concylic
11 replies
anyone__42
Jun 27, 2020
zhenghua
40 minutes ago
IMO Shortlist 2011, Algebra 5
orl   18
N an hour ago by mathfun07
Source: IMO Shortlist 2011, Algebra 5
Prove that for every positive integer $n,$ the set $\{2,3,4,\ldots,3n+1\}$ can be partitioned into $n$ triples in such a way that the numbers from each triple are the lengths of the sides of some obtuse triangle.

Proposed by Canada
18 replies
orl
Jul 11, 2012
mathfun07
an hour ago
Line Perpendicular to Euler Line
tastymath75025   55
N an hour ago by ohiorizzler1434
Source: USA TSTST 2017 Problem 1, by Ray Li
Let $ABC$ be a triangle with circumcircle $\Gamma$, circumcenter $O$, and orthocenter $H$. Assume that $AB\neq AC$ and that $\angle A \neq 90^{\circ}$. Let $M$ and $N$ be the midpoints of sides $AB$ and $AC$, respectively, and let $E$ and $F$ be the feet of the altitudes from $B$ and $C$ in $\triangle ABC$, respectively. Let $P$ be the intersection of line $MN$ with the tangent line to $\Gamma$ at $A$. Let $Q$ be the intersection point, other than $A$, of $\Gamma$ with the circumcircle of $\triangle AEF$. Let $R$ be the intersection of lines $AQ$ and $EF$. Prove that $PR\perp OH$.

Proposed by Ray Li
55 replies
tastymath75025
Jun 29, 2017
ohiorizzler1434
an hour ago
Foot from vertex to Euler line
cjquines0   31
N an hour ago by pUssydestroyer777
Source: 2016 IMO Shortlist G5
Let $D$ be the foot of perpendicular from $A$ to the Euler line (the line passing through the circumcentre and the orthocentre) of an acute scalene triangle $ABC$. A circle $\omega$ with centre $S$ passes through $A$ and $D$, and it intersects sides $AB$ and $AC$ at $X$ and $Y$ respectively. Let $P$ be the foot of altitude from $A$ to $BC$, and let $M$ be the midpoint of $BC$. Prove that the circumcentre of triangle $XSY$ is equidistant from $P$ and $M$.
31 replies
1 viewing
cjquines0
Jul 19, 2017
pUssydestroyer777
an hour ago
Inequality => square
Rushil   12
N 2 hours ago by ohiorizzler1434
Source: INMO 1998 Problem 4
Suppose $ABCD$ is a cyclic quadrilateral inscribed in a circle of radius one unit. If $AB \cdot BC \cdot CD \cdot DA \geq 4$, prove that $ABCD$ is a square.
12 replies
Rushil
Oct 7, 2005
ohiorizzler1434
2 hours ago
p + q + r + s = 9 and p^2 + q^2 + r^2 + s^2 = 21
who   28
N 2 hours ago by asdf334
Source: IMO Shortlist 2005 problem A3
Four real numbers $ p$, $ q$, $ r$, $ s$ satisfy $ p+q+r+s = 9$ and $ p^{2}+q^{2}+r^{2}+s^{2}= 21$. Prove that there exists a permutation $ \left(a,b,c,d\right)$ of $ \left(p,q,r,s\right)$ such that $ ab-cd \geq 2$.
28 replies
who
Jul 8, 2006
asdf334
2 hours ago
H not needed
dchenmathcounts   44
N 3 hours ago by Ilikeminecraft
Source: USEMO 2019/1
Let $ABCD$ be a cyclic quadrilateral. A circle centered at $O$ passes through $B$ and $D$ and meets lines $BA$ and $BC$ again at points $E$ and $F$ (distinct from $A,B,C$). Let $H$ denote the orthocenter of triangle $DEF.$ Prove that if lines $AC,$ $DO,$ $EF$ are concurrent, then triangle $ABC$ and $EHF$ are similar.

Robin Son
44 replies
dchenmathcounts
May 23, 2020
Ilikeminecraft
3 hours ago
IZHO 2017 Functional equations
user01   51
N 3 hours ago by lksb
Source: IZHO 2017 Day 1 Problem 2
Find all functions $f:R \rightarrow R$ such that $$(x+y^2)f(yf(x))=xyf(y^2+f(x))$$, where $x,y \in \mathbb{R}$
51 replies
user01
Jan 14, 2017
lksb
3 hours ago
Inequality with wx + xy + yz + zw = 1
Fermat -Euler   23
N 3 hours ago by hgomamogh
Source: IMO ShortList 1990, Problem 24 (THA 2)
Let $ w, x, y, z$ are non-negative reals such that $ wx + xy + yz + zw = 1$.
Show that $ \frac {w^3}{x + y + z} + \frac {x^3}{w + y + z} + \frac {y^3}{w + x + z} + \frac {z^3}{w + x + y}\geq \frac {1}{3}$.
23 replies
Fermat -Euler
Nov 2, 2005
hgomamogh
3 hours ago
Lower bound for integer relatively prime to n
62861   23
N Yesterday at 6:12 AM by YaoAOPS
Source: USA Winter Team Selection Test #1 for IMO 2018, Problem 1
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
23 replies
62861
Dec 11, 2017
YaoAOPS
Yesterday at 6:12 AM
Lower bound for integer relatively prime to n
G H J
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.
62861
3564 posts
#1 • 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.
GGPiku
402 posts
#2 • 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.
yayups
1614 posts
#3 • 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.
yayups
1614 posts
#4 • 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.
a1267ab
223 posts
#7 • 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.
ThE-dArK-lOrD
4071 posts
#8 • 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.
anantmudgal09
1979 posts
#9 • 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 :P
I wonder if a solution is possible by combinatorial arguments alone? :maybe:
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6857 posts
#10 • 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.
tree3
641 posts
#11 • 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.
Th3Numb3rThr33
1247 posts
#13 • 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.
amuthup
779 posts
#15 • 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.
mathaddiction
308 posts
#16 • 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.
Idio-logy
206 posts
#17 • 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.
Eyed
1065 posts
#18 • 1 Y
Y by cubres
Thanks samuel for the hint! :D

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.
Sprites
478 posts
#19 • 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.
jj_ca888
2726 posts
#20 • 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.
AwesomeYRY
579 posts
#21 • 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.
IAmTheHazard
5000 posts
#22 • 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.
Inconsistent
1455 posts
#23 • 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.
blackbluecar
302 posts
#24 • 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.
HamstPan38825
8846 posts
#25 • 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.
GeorgeRP
130 posts
#26 • 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.
GrantStar
812 posts
#27 • 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.
YaoAOPS
1484 posts
#28 • 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
=
a