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 Peer-to-Peer Programs Forum
jwelsh   157
N Dec 11, 2023 by cw357
Many of our AoPS Community members share their knowledge with their peers in a variety of ways, ranging from creating mock contests to creating real contests to writing handouts to hosting sessions as part of our partnership with schoolhouse.world.

To facilitate students in these efforts, we have created a new Peer-to-Peer Programs forum. With the creation of this forum, we are starting a new process for those of you who want to advertise your efforts. These advertisements and ensuing discussions have been cluttering up some of the forums that were meant for other purposes, so we’re gathering these topics in one place. This also allows students to find new peer-to-peer learning opportunities without having to poke around all the other forums.

To announce your program, or to invite others to work with you on it, here’s what to do:

1) Post a new topic in the Peer-to-Peer Programs forum. This will be the discussion thread for your program.

2) Post a single brief post in this thread that links the discussion thread of your program in the Peer-to-Peer Programs forum.

Please note that we’ll move or delete any future advertisement posts that are outside the Peer-to-Peer Programs forum, as well as any posts in this topic that are not brief announcements of new opportunities. In particular, this topic should not be used to discuss specific programs; those discussions should occur in topics in the Peer-to-Peer Programs forum.

Your post in this thread should have what you're sharing (class, session, tutoring, handout, math or coding game/other program) and a link to the thread in the Peer-to-Peer Programs forum, which should have more information (like where to find what you're sharing).
157 replies
jwelsh
Mar 15, 2021
cw357
Dec 11, 2023
k i C&P posting recs by mods
v_Enhance   0
Jun 12, 2020
The purpose of this post is to lay out a few suggestions about what kind of posts work well for the C&P forum. Except in a few cases these are mostly meant to be "suggestions based on historical trends" rather than firm hard rules; we may eventually replace this with an actual list of firm rules but that requires admin approval :) That said, if you post something in the "discouraged" category, you should not be totally surprised if it gets locked; they are discouraged exactly because past experience shows they tend to go badly.
-----------------------------
1. Program discussion: Allowed
If you have questions about specific camps or programs (e.g. which classes are good at X camp?), these questions fit well here. Many camps/programs have specific sub-forums too but we understand a lot of them are not active.
-----------------------------
2. Results discussion: Allowed
You can make threads about e.g. how you did on contests (including AMC), though on AMC day when there is a lot of discussion. Moderators and administrators may do a lot of thread-merging / forum-wrangling to keep things in one place.
-----------------------------
3. Reposting solutions or questions to past AMC/AIME/USAMO problems: Allowed
This forum contains a post for nearly every problem from AMC8, AMC10, AMC12, AIME, USAJMO, USAMO (and these links give you an index of all these posts). It is always permitted to post a full solution to any problem in its own thread (linked above), regardless of how old the problem is, and even if this solution is similar to one that has already been posted. We encourage this type of posting because it is helpful for the user to explain their solution in full to an audience, and for future users who want to see multiple approaches to a problem or even just the frequency distribution of common approaches. We do ask for some explanation; if you just post "the answer is (B); ez" then you are not adding anything useful.

You are also encouraged to post questions about a specific problem in the specific thread for that problem, or about previous user's solutions. It's almost always better to use the existing thread than to start a new one, to keep all the discussion in one place easily searchable for future visitors.
-----------------------------
4. Advice posts: Allowed, but read below first
You can use this forum to ask for advice about how to prepare for math competitions in general. But you should be aware that this question has been asked many many times. Before making a post, you are encouraged to look at the following:
[list]
[*] Stop looking for the right training: A generic post about advice that keeps getting stickied :)
[*] There is an enormous list of links on the Wiki of books / problems / etc for all levels.
[/list]
When you do post, we really encourage you to be as specific as possible in your question. Tell us about your background, what you've tried already, etc.

Actually, the absolute best way to get a helpful response is to take a few examples of problems that you tried to solve but couldn't, and explain what you tried on them / why you couldn't solve them. Here is a great example of a specific question.
-----------------------------
5. Publicity: use P2P forum instead
See https://artofproblemsolving.com/community/c5h2489297_peertopeer_programs_forum.
Some exceptions have been allowed in the past, but these require approval from administrators. (I am not totally sure what the criteria is. I am not an administrator.)
-----------------------------
6. Mock contests: use Mock Contests forum instead
Mock contests should be posted in the dedicated forum instead:
https://artofproblemsolving.com/community/c594864_aops_mock_contests
-----------------------------
7. AMC procedural questions: suggest to contact the AMC HQ instead
If you have a question like "how do I submit a change of venue form for the AIME" or "why is my name not on the qualifiers list even though I have a 300 index", you would be better off calling or emailing the AMC program to ask, they are the ones who can help you :)
-----------------------------
8. Discussion of random math problems: suggest to use MSM/HSM/HSO instead
If you are discussing a specific math problem that isn't from the AMC/AIME/USAMO, it's better to post these in Middle School Math, High School Math, High School Olympiads instead.
-----------------------------
9. Politics: suggest to use Round Table instead
There are important conversations to be had about things like gender diversity in math contests, etc., for sure. However, from experience we think that C&P is historically not a good place to have these conversations, as they go off the rails very quickly. We encourage you to use the Round Table instead, where it is much more clear that all posts need to be serious.
-----------------------------
10. MAA complaints: discouraged
We don't want to pretend that the MAA is perfect or that we agree with everything they do. However, we chose to discourage this sort of behavior because in practice most of the comments we see are not useful and some are frankly offensive.
[list] [*] If you just want to blow off steam, do it on your blog instead.
[*] When you have criticism, it should be reasoned, well-thought and constructive. What we mean by this is, for example, when the AOIME was announced, there was great outrage about potential cheating. Well, do you really think that this is something the organizers didn't think about too? Simply posting that "people will cheat and steal my USAMOO qualification, the MAA are idiots!" is not helpful as it is not bringing any new information to the table.
[*] Even if you do have reasoned, well-thought, constructive criticism, we think it is actually better to email it the MAA instead, rather than post it here. Experience shows that even polite, well-meaning suggestions posted in C&P are often derailed by less mature users who insist on complaining about everything.
[/list]
-----------------------------
11. Memes and joke posts: discouraged
It's fine to make jokes or lighthearted posts every so often. But it should be done with discretion. Ideally, jokes should be done within a longer post that has other content. For example, in my response to one user's question about olympiad combinatorics, I used a silly picture of Sogiita Gunha, but it was done within a context of a much longer post where it was meant to actually make a point.

On the other hand, there are many threads which consist largely of posts whose only content is an attached meme with the word "MAA" in it. When done in excess like this, the jokes reflect poorly on the community, so we explicitly discourage them.
-----------------------------
12. Questions that no one can answer: discouraged
Examples of this: "will MIT ask for AOIME scores?", "what will the AIME 2021 cutoffs be (asked in 2020)", etc. Basically, if you ask a question on this forum, it's better if the question is something that a user can plausibly answer :)
-----------------------------
13. Blind speculation: discouraged
Along these lines, if you do see a question that you don't have an answer to, we discourage "blindly guessing" as it leads to spreading of baseless rumors. For example, if you see some user posting "why are there fewer qualifiers than usual this year?", you should not reply "the MAA must have been worried about online cheating so they took fewer people!!". Was sich überhaupt sagen lässt, lässt sich klar sagen; und wovon man nicht reden kann, darüber muss man schweigen.
-----------------------------
14. Discussion of cheating: strongly discouraged
If you have evidence or reasonable suspicion of cheating, please report this to your Competition Manager or to the AMC HQ; these forums cannot help you.
Otherwise, please avoid public discussion of cheating. That is: no discussion of methods of cheating, no speculation about how cheating affects cutoffs, and so on --- it is not helpful to anyone, and it creates a sour atmosphere. A longer explanation is given in Seriously, please stop discussing how to cheat.
-----------------------------
15. Cutoff jokes: never allowed
Whenever the cutoffs for any major contest are released, it is very obvious when they are official. In the past, this has been achieved by the numbers being posted on the official AMC website (here) or through a post from the AMCDirector account.

You must never post fake cutoffs, even as a joke. You should also refrain from posting cutoffs that you've heard of via email, etc., because it is better to wait for the obvious official announcement. A longer explanation is given in A Treatise on Cutoff Trolling.
-----------------------------
16. Meanness: never allowed
Being mean is worse than being immature and unproductive. If another user does something which you think is inappropriate, use the Report button to bring the post to moderator attention, or if you really must reply, do so in a way that is tactful and constructive rather than inflammatory.
-----------------------------

Finally, we remind you all to sit back and enjoy the problems. :D

-----------------------------
(EDIT 2024-09-13: AoPS has asked to me to add the following item.)

Advertising paid program or service: never allowed

Per the AoPS Terms of Service (rule 5h), general advertisements are not allowed.

While we do allow advertisements of official contests (at the MAA and MATHCOUNTS level) and those run by college students with at least one successful year, any and all advertisements of a paid service or program is not allowed and will be deleted.
0 replies
v_Enhance
Jun 12, 2020
0 replies
k i Stop looking for the "right" training
v_Enhance   50
N Oct 16, 2017 by blawho12
Source: Contest advice
EDIT 2019-02-01: https://blog.evanchen.cc/2019/01/31/math-contest-platitudes-v3/ is the updated version of this.

EDIT 2021-06-09: see also https://web.evanchen.cc/faq-contest.html.

Original 2013 post
50 replies
v_Enhance
Feb 15, 2013
blawho12
Oct 16, 2017
Inequality => square
Rushil   12
N 17 minutes 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
1 viewing
Rushil
Oct 7, 2005
ohiorizzler1434
17 minutes ago
p + q + r + s = 9 and p^2 + q^2 + r^2 + s^2 = 21
who   28
N 33 minutes 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
33 minutes ago
H not needed
dchenmathcounts   44
N an hour 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
1 viewing
dchenmathcounts
May 23, 2020
Ilikeminecraft
an hour ago
AMC- IMO preparation
asyaela.   9
N an hour ago by Schintalpati
I'm a ninth grader, and I recently attempted the AMC 12, getting 18 questions correct and leaving 7 empty. I started working on Olympiad math in November and currently dedicate about two hours per day to preparation. I'm feeling a bit demotivated, but if it's possible for me to reach IMO level, I'd be willing to put in more time. How realistic is it for me to get there, and how much study would it typically take?
9 replies
asyaela.
4 hours ago
Schintalpati
an hour ago
Tennessee Math Tournament (TMT) Online 2025
TennesseeMathTournament   29
N an hour ago by NashvilleSC
Hello everyone! We are excited to announce a new competition, the Tennessee Math Tournament, created by the Tennessee Math Coalition! Anyone can participate in the virtual competition for free.

The testing window is from March 22nd to April 5th, 2025. Virtual competitors may participate in the competition at any time during that window.

The virtual competition consists of three rounds: Individual, Bullet, and Team. The Individual Round is 60 minutes long and consists of 30 questions (AMC 10 level). The Bullet Round is 20 minutes long and consists of 80 questions (Mathcounts Chapter level). The Team Round is 30 minutes long and consists of 16 questions (AMC 12 level). Virtual competitors may compete in teams of four, or choose to not participate in the team round.

To register and see more information, click here!

If you have any questions, please email connect@tnmathcoalition.org or reply to this thread!
29 replies
TennesseeMathTournament
Mar 9, 2025
NashvilleSC
an hour ago
IZHO 2017 Functional equations
user01   51
N an hour 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
an hour ago
AIME score for college apps
Happyllamaalways   75
N an hour ago by hashbrown2009
What good colleges do I have a chance of getting into with an 11 on AIME? (Any chances for Princeton)

Also idk if this has weight but I had the highest AIME score in my school.
75 replies
+1 w
Happyllamaalways
Mar 13, 2025
hashbrown2009
an hour ago
AMC 8 discussion
Jaxman8   42
N 2 hours ago by mpcnotnpc
Discuss the AMC 8 below!
42 replies
Jaxman8
Jan 29, 2025
mpcnotnpc
2 hours ago
Segment has Length Equal to Circumradius
djmathman   72
N 2 hours ago by Zhaom
Source: 2014 USAMO Problem 5
Let $ABC$ be a triangle with orthocenter $H$ and let $P$ be the second intersection of the circumcircle of triangle $AHC$ with the internal bisector of the angle $\angle BAC$. Let $X$ be the circumcenter of triangle $APB$ and $Y$ the orthocenter of triangle $APC$. Prove that the length of segment $XY$ is equal to the circumradius of triangle $ABC$.
72 replies
djmathman
Apr 30, 2014
Zhaom
2 hours ago
[Registration Open] Mustang Math Tournament 2025
MustangMathTournament   22
N 2 hours ago by RainbowSquirrel53B
Mustang Math is excited to announce that registration for our annual tournament, MMT 2025, is open! This year, we are bringing our tournament to 9 in-person locations, as well as online!

Locations include: Colorado, Norcal, Socal, Georgia, Illinois, Massachusetts, New Jersey, Nevada, Washington, and online. For registration and more information, check out https://mustangmath.com/competitions/mmt-2025.

MMT 2025 is a math tournament run by a group of 150+ mathematically experienced high school and college students who are dedicated to providing a high-quality and enjoyable contest for middle school students. Our tournament centers around teamwork and collaboration, incentivizing students to work with their teams not only to navigate the challenging and interesting problems of the tournament but also to develop strategies to master the unique rounds. This includes a logic puzzle round, a strategy-filled hexes round, a race-like gallop round, and our trademark ‘Mystery Mare’ round!

Awards:
[list]
[*] Medals for the top teams
[*] Shirts, pins, stickers and certificates for all participants
[*] Additional awards provided by our wonderful sponsors!
[/list]

We are also holding a free MMT prep seminar from 3/15-3/16 to help students prepare for the upcoming tournament. Join the Google Classroom! https://classroom.google.com/c/NzQ5NDUyNDY2NjM1?cjc=7sogth4
22 replies
MustangMathTournament
Mar 8, 2025
RainbowSquirrel53B
2 hours ago
d_k-eja Vu
ihatemath123   46
N 4 hours ago by Ilikeminecraft
Source: 2024 USAMO Problem 1
Find all integers $n \geq 3$ such that the following property holds: if we list the divisors of $n!$ in increasing order as $1 = d_1 < d_2 < \dots < d_k = n!$, then we have
\[ d_2 - d_1 \leq d_3 - d_2 \leq \dots \leq d_k - d_{k-1}. \]
Proposed by Luke Robitaille.
46 replies
ihatemath123
Mar 20, 2024
Ilikeminecraft
4 hours ago
average FE
KevinYang2.71   75
N 5 hours ago by Marcus_Zhang
Source: USAJMO 2024/5
Find all functions $f:\mathbb{R}\rightarrow\mathbb{R}$ that satisfy
\[
f(x^2-y)+2yf(x)=f(f(x))+f(y)
\]for all $x,y\in\mathbb{R}$.

Proposed by Carl Schildkraut
75 replies
KevinYang2.71
Mar 21, 2024
Marcus_Zhang
5 hours ago
apparently circles have two intersections :'(
itised   76
N 5 hours ago by Ilikeminecraft
Source: 2020 USOJMO Problem 2
Let $\omega$ be the incircle of a fixed equilateral triangle $ABC$. Let $\ell$ be a variable line that is tangent to $\omega$ and meets the interior of segments $BC$ and $CA$ at points $P$ and $Q$, respectively. A point $R$ is chosen such that $PR = PA$ and $QR = QB$. Find all possible locations of the point $R$, over all choices of $\ell$.

Proposed by Titu Andreescu and Waldemar Pompe
76 replies
itised
Jun 21, 2020
Ilikeminecraft
5 hours ago
Too Bad I'm Lactose Intolerant
hwl0304   216
N Today at 5:20 PM by AshAuktober
Source: 2018 USAMO Problem 1/USAJMO Problem 2
Let \(a,b,c\) be positive real numbers such that \(a+b+c=4\sqrt[3]{abc}\). Prove that \[2(ab+bc+ca)+4\min(a^2,b^2,c^2)\ge a^2+b^2+c^2.\]
216 replies
hwl0304
Apr 18, 2018
AshAuktober
Today at 5:20 PM
Lower bound for integer relatively prime to n
62861   23
N Today 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
Today 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, Today at 6:12 AM
Z K Y
N Quick Reply
G
H
=
a