Stay ahead of learning milestones! Enroll in a class over the summer!

G
Topic
First Poster
Last Poster
k a May Highlights and 2025 AoPS Online Class Information
jlacosta   0
May 1, 2025
May is an exciting month! National MATHCOUNTS is the second week of May in Washington D.C. and our Founder, Richard Rusczyk will be presenting a seminar, Preparing Strong Math Students for College and Careers, on May 11th.

Are you interested in working towards MATHCOUNTS and don’t know where to start? We have you covered! If you have taken Prealgebra, then you are ready for MATHCOUNTS/AMC 8 Basics. Already aiming for State or National MATHCOUNTS and harder AMC 8 problems? Then our MATHCOUNTS/AMC 8 Advanced course is for you.

Summer camps are starting next month at the Virtual Campus in math and language arts that are 2 - to 4 - weeks in duration. Spaces are still available - don’t miss your chance to have an enriching summer experience. There are middle and high school competition math camps as well as Math Beasts camps that review key topics coupled with fun explorations covering areas such as graph theory (Math Beasts Camp 6), cryptography (Math Beasts Camp 7-8), and topology (Math Beasts Camp 8-9)!

Be sure to mark your calendars for the following upcoming events:
[list][*]May 9th, 4:30pm PT/7:30pm ET, Casework 2: Overwhelming Evidence — A Text Adventure, a game where participants will work together to navigate the map, solve puzzles, and win! All are welcome.
[*]May 19th, 4:30pm PT/7:30pm ET, What's Next After Beast Academy?, designed for students finishing Beast Academy and ready for Prealgebra 1.
[*]May 20th, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 1 Math Jam, Problems 1 to 4, join the Canada/USA Mathcamp staff for this exciting Math Jam, where they discuss solutions to Problems 1 to 4 of the 2025 Mathcamp Qualifying Quiz!
[*]May 21st, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 2 Math Jam, Problems 5 and 6, Canada/USA Mathcamp staff will discuss solutions to Problems 5 and 6 of the 2025 Mathcamp Qualifying Quiz![/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
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
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, 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
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
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
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
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

Paradoxes and Infinity
Mon, Tue, Wed, & Thurs, Jul 14 - Jul 16 (meets every day of the week!)

Intermediate: Grades 8-12

Intermediate Algebra
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
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Tuesday, Jun 10 - Aug 26

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

AIME Problem Series A
Thursday, May 22 - Jul 31

AIME Problem Series B
Sunday, Jun 22 - Sep 21

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
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
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
May 1, 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
Iranians playing with cards module a prime number.
Ryan-asadi   2
N 4 minutes ago by AshAuktober
Source: Iranian Team Selection Test - P2
Let $p$ be an arbitrary prime number.we have a deck of cards which a number is written on the back of each of them. such that for every $i \in \{1,…,p-1\}$ we have at most one card with number $i$ written on its back and we also have exactly one card with number zero on its back.we want to design a game in which we need to decide for every two cards $X,Y$ witch one wins from the other one using the following rules.

$(I)$: If $x$ wins from $y$ and also $y$ wins from $z$ , then $x$ wins from $z$.
$(II)$: If $x$ doesn’t fail $y$ and $z$ doesn’t fail $t$ , then in case of existing of both cards $y+t$ and $x+z$ module $p$, card $x+z$ also doesn’t fail $y+t$.

What is the maximum number of cards which designing such game is possible?

2 replies
Ryan-asadi
2 hours ago
AshAuktober
4 minutes ago
Coloring plane in black
Ryan-asadi   1
N 5 minutes ago by AshAuktober
Source: Iran Team Selection Test - P3
We are given $n>10$ lines in the plane such that no two of them are parallel and no three of them are concurrent. We color at least $\frac{n^2}{8}+1$ regions in black from all limited regions which have constructed in the plane. We call a triangle constructed by three lines “black-less” if there exist exactly one black region inside that. Prove that there exist at least $\frac{n}{2}$ “black-lass” triangles in plane.
1 reply
Ryan-asadi
2 hours ago
AshAuktober
5 minutes ago
An analytic sequence
Ryan-asadi   1
N 6 minutes ago by AshAuktober
Source: Iran Team Selection Test - P1
Let $a_n$ be a sequence of real positive numbers such that for all $n>2025$ :
$$a_n = \max_{1 \le i \le 2025}{a_{n-i}}-\min_{1 \le i \le 2025}{a_{n-i}} $$Prove that for all large enough natural $n$ we have that $a_n < \frac{1}{1404}$.
1 reply
Ryan-asadi
2 hours ago
AshAuktober
6 minutes ago
AD=BE implies ABC right
v_Enhance   115
N 18 minutes ago by Adywastaken
Source: European Girl's MO 2013, Problem 1
The side $BC$ of the triangle $ABC$ is extended beyond $C$ to $D$ so that $CD = BC$. The side $CA$ is extended beyond $A$ to $E$ so that $AE = 2CA$. Prove that, if $AD=BE$, then the triangle $ABC$ is right-angled.
115 replies
v_Enhance
Apr 10, 2013
Adywastaken
18 minutes ago
Geometry
gggzul   6
N 22 minutes ago by Captainscrubz
In trapezoid $ABCD$ segments $AB$ and $CD$ are parallel. Angle bisectors of $\angle A$ and $\angle C$ meet at $P$. Angle bisectors of $\angle B$ and $\angle D$ meet at $Q$. Prove that $ABPQ$ is cyclic
6 replies
gggzul
Yesterday at 8:22 AM
Captainscrubz
22 minutes ago
Need help on this simple looking problem
TheGreatEuler   0
27 minutes ago
Show that 1+2+3+4....n divides 1^k+2^k+3^k....n^k when k is odd. Is this possible to prove without using congruence modulo or binomial coefficients?
0 replies
TheGreatEuler
27 minutes ago
0 replies
Geometry
Lukariman   5
N an hour ago by Lukariman
Given circle (O) and point P outside (O). From P draw tangents PA and PB to (O) with contact points A, B. On the opposite ray of ray BP, take point M. The circle circumscribing triangle APM intersects (O) at the second point D. Let H be the projection of B on AM. Prove that $\angle HDM$ = 2∠AMP.
5 replies
Lukariman
Yesterday at 12:43 PM
Lukariman
an hour ago
inq , not two of them =0
win14   0
an hour ago
Let a,b,c be non negative real numbers such that no two of them are simultaneously equal to 0
$$\frac{1}{a + b} + \frac{1}{b + c} + \frac{1}{c + a} \ge \frac{5}{2\sqrt{ab + bc + ca}}.$$
0 replies
1 viewing
win14
an hour ago
0 replies
IMO Genre Predictions
ohiorizzler1434   62
N an hour ago by ehuseyinyigit
Everybody, with IMO upcoming, what are you predictions for the problem genres?


Personally I predict: predict
62 replies
ohiorizzler1434
May 3, 2025
ehuseyinyigit
an hour ago
Number theory
MathsII-enjoy   5
N 2 hours ago by MathsII-enjoy
Prove that when $x^p+y^p$ | $(p^2-1)^n$ with $x,y$ are positive integers and $p$ is prime ($p>3$), we get: $x=y$
5 replies
MathsII-enjoy
Monday at 3:22 PM
MathsII-enjoy
2 hours ago
Number theory
Foxellar   0
2 hours ago
It is known that for all positive integers $k$,
\[
1^2 + 2^2 + 3^2 + \ldots + k^2 = \frac{k(k + 1)(2k + 1)}{6}
\]Find the smallest positive integer $k$ such that $1^2 + 2^2 + 3^2 + \ldots + k^2$ is divisible by 200.
0 replies
Foxellar
2 hours ago
0 replies
Combinatorics
P162008   4
N 2 hours ago by cazanova19921
Let $m,n \in \mathbb{N}.$ Let $[n]$ denote the set of natural numbers less than or equal to $n.$

Let $f(m,n) = \sum_{(x_1,x_2,x_3, \cdots, x_m) \in [n]^{m}} \frac{x_1}{x_1 + x_2 + x_3 + \cdots + x_m} \binom{n}{x_1} \binom{n}{x_2} \binom{n}{x_3} \cdots \binom{n}{x_m} 2^{\left(\sum_{i=1}^{m} x_i\right)}$

Compute the sum of the digits of $f(4,4).$
4 replies
P162008
Today at 5:38 AM
cazanova19921
2 hours ago
Aime type Geo
ehuseyinyigit   4
N 2 hours ago by ehuseyinyigit
Source: Turkish First Round 2024
In a scalene triangle $ABC$, let $M$ be the midpoint of side $BC$. Let the line perpendicular to $AC$ at point $C$ intersect $AM$ at $N$. If $(BMN)$ is tangent to $AB$ at $B$, find $AB/MA$.
4 replies
ehuseyinyigit
Monday at 9:04 PM
ehuseyinyigit
2 hours ago
n variables with n-gon sides
mihaig   1
N 2 hours ago by mihaig
Source: Own
Let $n\geq3$ and let $a_1,a_2,\ldots, a_n\geq0$ be reals such that $\sum_{i=1}^{n}{\frac{1}{2a_i+n-2}}=1.$
Prove
$$\frac{24}{(n-1)(n-2)}\cdot\sum_{1\leq i<j<k\leq n}{a_ia_ja_k}\geq3\sum_{i=1}^{n}{a_i}+n.$$
1 reply
mihaig
Apr 25, 2025
mihaig
2 hours ago
Least integer T_m such that m divides gauss sum
Al3jandro0000   33
N Apr 22, 2025 by NerdyNashville
Source: 2020 Iberoamerican P2
Let $T_n$ denotes the least natural such that
$$n\mid 1+2+3+\cdots +T_n=\sum_{i=1}^{T_n} i$$Find all naturals $m$ such that $m\ge T_m$.

Proposed by Nicolás De la Hoz
33 replies
Al3jandro0000
Nov 17, 2020
NerdyNashville
Apr 22, 2025
Least integer T_m such that m divides gauss sum
G H J
G H BBookmark kLocked kLocked NReply
Source: 2020 Iberoamerican P2
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Al3jandro0000
804 posts
#1 • 3 Y
Y by superagh, centslordm, itslumi
Let $T_n$ denotes the least natural such that
$$n\mid 1+2+3+\cdots +T_n=\sum_{i=1}^{T_n} i$$Find all naturals $m$ such that $m\ge T_m$.

Proposed by Nicolás De la Hoz
This post has been edited 3 times. Last edited by Al3jandro0000, Nov 18, 2020, 3:54 PM
Reason: Some clarifications
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Al3jandro0000
804 posts
#2 • 2 Y
Y by centslordm, The_Eureka
Notice the problem is equivalent to find all $m$ such that $f(x)=\frac{x^2+x}{2}\equiv 0\mod m$ has no a non trivial solution i.e there is a solution $r\not\equiv 0\mod m$ which satisfy the relation, contradiction.

If $m$ is odd we have $\gcd(m,2)=1$ so
$$2f(x)\equiv 0\mod m$$which has a solution $x=m-1$ so $T_m\le m-1$ there are no odd solutions. Thus $m$ must be of the form $m=2^k\prod_{i=1}^{\omega(m)-1} p_i^{\nu_{p_i}(m)}$. If $\omega(m)>1$ we have at least a prime satisfying
$$f(x)\equiv 0\mod p_i^{\nu_{p_i}(m)}$$And this has two roots so by $CRT$ we have at least $2$ distinct solutions for $x$ after considering the system of relatively primes
$$f(x)\equiv 0\mod 2^k$$$$f(x)\equiv 0\mod p_i^{\nu_{p_i}(m)}$$But this implies there is a non-trivial solution and we are done, this can't be a solution. So $m=2^k$.

The converse is quite easy to check, suppose $m=2^k$ is satisfying $$\frac{T_m(T_m+1)}{2}\equiv 0\mod 2^k\implies T_m(T_m+1)\equiv 0\mod 2^{k+1}$$And since $\gcd(T_m,T_m+1)=1$ we have either $2^{k+1}\mid T_m$ or $2^{k+1}\mid T_m+1$ the first implies
$$T_m\ge 2^{k+1}>2^k$$And the later implies
$$T_m\ge 2^{k+1}-1\ge 2^{k+1}-2^k=2^k$$So we are done, we showed all the solutions are $m=2^k\forall k\in\mathbb N\cup \{0,\}$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Packito
37 posts
#3 • 10 Y
Y by mijail, amar_04, LolitaLaLolita, Oznerol1, centslordm, Aryan-23, aidan0626, EpicBird08, Supertinito, akliu
This problem was proposed by Colombia :) by me (Nicolás De la Hoz).
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
hectorraul
363 posts
#4 • 2 Y
Y by centslordm, SerdarBozdag
If $m=2^a$ clearly $T_m>m$.

Let $m=2^a(2k+1)$, with $k\geq 1$.

Consider the set $S=\{2^{a+1}, 2\cdot 2^{a+1},\dots,k\cdot 2^{a+1}\}$. Notice that every element of the set is strictly smaller than $m$.

Easy to check that:

* mod $(2k+1)$, the $k$ elements of $S$ are different.
* mod $(2k+1)$, at most one of the elements of the tuple $(x,2k+1-x)$ belongs $S$.

Conclusion: From each tuple in $\{(1,2k),(2,2k-1),\dots,(k,k+1)\}$ we have exactly one element in $S$. Then there exist $1\leq b\leq k$ such that either $b\cdot 2^{a+1}-1\equiv 0(2k+1)$ or $b\cdot 2^{a+1}+1\equiv 0(2k+1)$.

Case 1: $b\cdot2^{a+1}-1\equiv 0(2k+1)$.
Clearly $\frac{(b\cdot 2^{a+1}-1)(b\cdot 2^{a+1})}{2}$ is divisible by $m=2^a(2k+1)$, then $T_m\leq b\cdot 2^{a+1}-1\leq 2^a(2k+1)=m$ .

Case 2: $b\cdot 2^{a+1}+1\equiv 0(2k+1)$.
Clearly $\frac{(b\cdot 2^{a+1})(b\cdot 2^{a+1}+1)}{2}$ is divisible by $m=2^a(2k+1)$, then $T_m\leq b\cdot 2^{a+1}\leq 2^a(2k+1)=m$.

Then the answer is every $m$ but the powers of $2$.
This post has been edited 5 times. Last edited by hectorraul, Nov 18, 2020, 7:11 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
grupyorum
1418 posts
#5 • 3 Y
Y by Alphatrion, centslordm, Mango247
The gist is essentially to analyze the case when $m=2^{\alpha}\cdot m'$, $k\ge 1$, and $m'>1$ odd (the rest, case when $m$ is odd and $m$ is a power of two are both quite trivial). For this case, I think my solution below is instructive and clear: Consider two congruences:
\[
\mathcal{C}_1 : \quad x\equiv 0\pmod{2^{\alpha+1}} \quad\text{and}\quad x\equiv -1\pmod{m'}.
\]\[
\mathcal{C}_2 : \quad x\equiv -1\pmod{2^{\alpha+1}} \quad\text{and}\quad x\equiv 0\pmod{m'}.
\]By the CRT, both $\mathcal{C}_1$ and $\mathcal{C}_2$ have a solution modulo $2^{\alpha+1}m'=2m$. I claim it is the case that the smallest solution to one of them is less than or equal to $m$. For that, let $\ell m'-1$ be the smallest positive solution to $\mathcal{C}_1$. In particular, $\ell m'\equiv 1\pmod{2^{\alpha+1}}$. If $\ell m'-1 \le m$, we are done. Otherwise, assume $\ell m'-1>m$. We have
\[
2m>\ell m'>m \implies 2^{\alpha+1}>\ell >2^\alpha.
\]Consider now the number
\[
x = \left(2^{\alpha+1}-\ell\right) m' = 2m - \ell m'.
\]Clearly $x<m$, and $x$ is divisible by $m'$. Furthermore, $x\equiv -1\pmod{2^{\alpha+1}}$. Therefore, $x<m$ solves the congruence $\mathcal{C}_2$. This concludes the proof.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Orestis_Lignos
558 posts
#7 • 2 Y
Y by A-Thought-Of-God, centslordm
Iberoamerican Math Olympiad 2020 P2 wrote:
Let $T_n$ denotes the least natural such that
$$n\mid 1+2+3+\cdots +T_n=\sum_{i=1}^{T_n} i$$Find all naturals $m$ such that $m\ge T_m$.

Proposed by Nicolás De la Hoz

Somewhat similar to @above, I think.

Suppose firstly that $m$ is a power of $2$. Let $m=2^k$. We must have $2^{k+1} \mid T_m(T_m+1)$, hence $2^{k+1} \mid T_m$ or
$2^{k+1} \mid T_m+1$. In both cases, $T_m \geq 2^{k+1}_1 >2^k=m$, therefore all powers of $2$ don't satisfy.

Suppose now $m$ is not a power of $2$. Let $m=2^P Q$ with $Q>1$ odd. We prove now the following Claim, which gives the result.

Claim: Let $s,t$ be minimal such that $2^{P+1} \mid (s+1), \, Q \mid s$ and $2^{P+1} \mid t, \, Q \mid (t+1)$. Then, either $s$ or $t$ is $<2^PQ$.

This Claim instantly solves the problem, since if for example $s<2^PQ$, then we have $2^{P+1}Q \mid s(s+1)$, hence $2^PQ=m \mid 1+2+\ldots+s$, therefore $m=2^PQ>s \geq T_m$, hence we are done.
What remains is to prove the Claim.

Proof: Let $s=2^{P+1}B-1$ and $t=2^{P+1}A$. Then, we have $Q \mid (2^{P+1}B-1)$ and $Q \mid (2^{P+1}A+1)$. Note that by CRT and the minimal condition we have $t,s \leq 2^{P+1}Q,$ therefore $A,B \leq Q$. In addition, $$2^{P+1}(Q-B)+1 \equiv -2^{P+1}B+1 \equiv 0 \pmod Q$$hence we must have $Q-B \geq A$, since $t$, and subsequently $A$, is minimal.
Therefore $A+B \leq Q$, implying that either $A$ or $B$ is $\leq Q/2$. Suppose $A \leq Q/2$.
Then $t=2^{P+1}A \leq 2^PQ=m$, as desired. Similarly we conclude if $B \leq Q/2$. $\blacksquare$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
hydo2332
435 posts
#8 • 1 Y
Y by centslordm
grupyorum wrote:
The gist is essentially to analyze the case when $m=2^{\alpha}\cdot m'$, $k\ge 1$, and $m'>1$ odd (the rest, case when $m$ is odd and $m$ is a power of two are both quite trivial). For this case, I think my solution below is instructive and clear: Consider two congruences:
\[
\mathcal{C}_1 : \quad x\equiv 0\pmod{2^{\alpha+1}} \quad\text{and}\quad x\equiv -1\pmod{m'}.
\]\[
\mathcal{C}_2 : \quad x\equiv -1\pmod{2^{\alpha+1}} \quad\text{and}\quad x\equiv 0\pmod{m'}.
\]By the CRT, both $\mathcal{C}_1$ and $\mathcal{C}_2$ have a solution modulo $2^{\alpha+1}m'=2m$. I claim it is the case that the smallest solution to one of them is less than or equal to $m$. For that, let $\ell m'-1$ be the smallest positive solution to $\mathcal{C}_1$. In particular, $\ell m'\equiv 1\pmod{2^{\alpha+1}}$. If $\ell m'-1 \le m$, we are done. Otherwise, assume $\ell m'-1>m$. We have
\[
2m>\ell m'>m \implies 2^{\alpha+1}>\ell >2^\alpha.
\]Consider now the number
\[
x = \left(2^{\alpha+1}-\ell\right) m' = 2m - \ell m'.
\]Clearly $x<m$, and $x$ is divisible by $m'$. Furthermore, $x\equiv -1\pmod{2^{\alpha+1}}$. Therefore, $x<m$ solves the congruence $\mathcal{C}_2$. This concludes the proof.

Why do you have $2m > \ell \cdot m'$ ?
This post has been edited 1 time. Last edited by hydo2332, Dec 6, 2020, 6:49 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Lioghte24
38 posts
#9 • 5 Y
Y by Kimchiks926, centslordm, pavanscoding, Tang_Tang, akliu
Here is my solution, which I will present in two important lemmas:
$\textbf{Lemma 1.}$
There does not exist $T_{n}$ for $n=2^k$ such that it is smaller than $n$.
Proof:
$1+2+3+\cdots+n=\frac{n(n+1)}{2}$,
so $2^k\mid \frac{T_{2^k}(T_{2^k}+1)}{2}$ implies that $2^{k+1}\mid T_{2^k}(T_{2^k}+1)$ so $T_{2^k}\geq2^{k+1}-1>2^k$, contradiction!
$\textbf{Lemma 2.}$
For all numbers $n=2^{k}m$, with $m$ being odd and larger than $1$, $T_{n}\leq n$.
Proof:
When $k$ $=$ $0$ just put $m-1$, it satisfies given condition.
When $k\geq 1$ put $T_{n}=2^{k+1}x$ or $T_{n}=2^{k+1}x-1$ and we will find suitable $x\leq \frac{m}{2}$.
So if $2^{k}m\mid \frac{2^{k+1}x(2^{k+1}x+1)}{2}$ or $2^{k}m\mid \frac{2^{k+1}x(2^{k+1}x-1)}{2}$
it implies that
$m\mid x(2^{k+1}x+1)$ or $m\mid x(2^{k+1}x-1)$,
and now we will look at the system of congruences
$2^{k+1}x\equiv -1 mod $ $m$ and $2^{k+1}x \equiv 1 mod $ $m$
and finding one solution $x$ such that it is congruent to number that is smaller than $\frac{m}{2}$ will prove the lemma since we can just pick that number and it will satisfy all conditions. Now we reduce all numbers $mod$ $m$ and look at the solution to $2^{k+1}x_{1}\equiv 1$, that solution will definitely exist because $gcd(2^{k+1},m)=1$ since m is odd. And if $x_{1}>\frac{m}{2}$ then we can just pick $x_{2}=m-x_{1}< \frac{m}{2}$ and it satisfies all conditions, proving our lemma.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Maths_1729
390 posts
#10 • 1 Y
Y by centslordm
Al3jandro0000 wrote:
Let $T_n$ denotes the least natural such that
$$n\mid 1+2+3+\cdots +T_n=\sum_{i=1}^{T_n} i$$Find all naturals $m$ such that $m\ge T_m$.

Proposed by Nicolás De la Hoz
As $\sum_{i=1}^{T_n} i=\frac{T_n(T_n+1)}{2}$

Now as $\frac{T_m(T_m+1)}{2m}\in N$

and let $m=2^k*y$ for some $y,k\in N$ then we have $2^{k+1}*y|T_m(T_m+1)$ Now as $gcd(T_m, T_m+1)=1$ so either $2^{k+1}*x=T_m$ or $2^{k+1}*x-1=T_m$ then we also have $y|x(2^{k+1}x-1)$ or $y|x(2^{k+1}x+1)$ Now as we need $2^{k+1}*y\geq T_m$
Claim 1-: $y\neq 2^z$ for any $z\in N$
We will asume the contrary so let $y=2^z$ then we have $2^z|x(2^{k+1}x +1)$ or

$2^z|x(2^{k+1}x+1)\implies 2^z|x$ hence $T_m=2^{z+k+1}*x_1$ or $2^{k+z+1}*x_1-1>2^{k+z}=m$ which is contradiction.
Hence $2^k$ is the maximum of $2$ which divide $m$ or $v_2(m)=k$ and so let $m=2^k*y_1$ for some odd $y$.
Claim 2-: for all odd $y_1$ where $m=2^k*y_1$ will satisfy the condition.
So we have to prove that there always exist $x$ such that $x<\prod_{i=1}^{m-1} p_i$ and $y=\prod_{i=1}^{m}p_i$ for prime $p_i$ such that $p_m>p_{m-1}>....>p_1>2$ for some $m\in N$ we have $y_1|x(2^{k+1}x+1)$ or $y_1|x(2^{k+1}x-1)$ so either $x(2^{k+1}x-1)\equiv 0\mod y_1$ or $x(2^{k+1}x+1)\equiv 0\mod y_1$ as $x<y$ so we must need to prove $2^{k+1}x\equiv \pm 1\mod p_n$ for some $p_n|y,p_n\nmid x$ and $n<m$ which is clearly true as by property of mods as $gcd(2^{k+1}x, p_n)|\pm 1$ so there will always exist exactly one $x<p_n$ so we are done. $\blacksquare$
This post has been edited 1 time. Last edited by Maths_1729, Feb 3, 2021, 1:03 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JustKeepRunning
2958 posts
#11 • 1 Y
Y by centslordm
Ok so for some reason I solved the opposite problem, so I'll rephrase the problem here so that my solution makes sense:
Al3jandro0000 wrote:
Let $T_n$ denotes the least natural such that
$$n\mid 1+2+3+\cdots +T_n=\sum_{i=1}^{T_n} i$$Find all naturals $m$ such that $T_m > m$.

Proposed by Nicolás De la Hoz


The answer is $2^n$ for positive integers $n$ and $0$. We first show that these do work, and then we show that the others don't work.

$1$ trivially works. Now we assume that $n$ is positive. For convenience, let $T_n=x$. Then notice that the condition is basically just that no $x\leq n$ satisfy $\nu_2(\frac{x(x+1)}{2})\geq n$. Notice that for it to satisfy the equation, $x=2^n-1$ or $x=2^n$, so that the numerator at least has an $\nu_2$ values $\geq n$. However, it is easy to see the division by $2$ causes both of these too fail, so we have showed that these solutions work.

We now show that no other numbers work. First off, it is clear that no odd number works, as for any odd $k,$ $k-1$ works, so $T_k\leq k-1,$ already strong enough to prove the claim. Now, to finish, we just show that any odd number multiply by any power of $2$ also does not work. This would be strong enough to prove the claim.

Notice that this condition is basically equivalent to $kc\pm 1\equiv 0\pmod 2^{d+1},$ for whatever power of $2$ you are trying to multiply by(we have to add one to the $\nu_2$ because of the division by $2$). Then it is easy to see that the solutions for $c$ are just $\pm k^{-1},$ and $k^{-1}$ exists because it is odd, coprime with modulus. Clearly, at least one of these $\leq 2^d$(the two halves of the residue class each contain one of $k^{-1}$ or $-k^{-1}$, and notice there is no "single middle" issue because the number of elements in the $2^{d+1}$ residue class is even), so we are done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
bever209
1522 posts
#12
Y by
(this solution is for $m \geq T_m$ instead of $m< T_m$)

Click to reveal hidden text
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
HamstPan38825
8860 posts
#13 • 4 Y
Y by centslordm, Mango247, Mango247, Mango247
The answer is all positive integers. In particular, we just need an integer $k \leq n$ such that $$2n \mid k(k+1).$$We will show that there must exist such a $k \leq n$ such that
\begin{align*}
k+1 &\equiv 0 \pmod {2^{\nu_2(n)+1}} \\
k+1 &\equiv 1 \pmod {\tfrac n{\nu_2(n)}}.
\end{align*}or vice versa. Because the two mods are relatively prime, we know there exists some $k \leq 2n$ such that this is true. If this $k \leq n$, we are done. If $k \geq n$, then consider the number $2n-k$. First, $$2n-k \equiv 0 - (-1) \equiv 1 \pmod {2^{\nu_2(n)+1}},$$whilst $$2n-k \equiv 0 - 0 \equiv 0 \pmod {\tfrac n{\nu_2(n)}},$$and thus satisfies the ``vice versa" system of congruences. We also know that $2n-k \leq n$ -- thus the claim is true as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
rafaello
1079 posts
#14
Y by
Oops, I solved also the opposite problem just as JustKeepRunning did.
Rephrased IberoAmerican 2020 P2 wrote:
Let $T_n$ denotes the least natural such that
$$n\mid 1+2+3+\cdots +T_n=\sum_{i=1}^{T_n} i$$Find all naturals $m$ such that $T_m > m$.
I claim that the answer is $2^k$ for all $k\geq 1$.

Firstly, we simplify the given,
$$n\mid \sum_{i=1}^{T_n} i =\frac{T_n(T_n+1)}{2}\implies T_n(T_n+1)\equiv 0\pmod{2n}.$$
For the numbers in the form $n=2^k$, we must have $$T_n(T_n+1)\equiv 0 \pmod{2^{k+1}}$$and as $\gcd(T_n,T_n+1)=1$, we must have either $2^{k+1}\mid T_n$ or $2^{k+1}\mid T_n+1$, thus $T_n=2^{k+1}-1=2n-1>n$.

For all the odd numbers $m$ note that $m$ works, thus definitely $m\geq T_m$ for any odd.


Claim. For any odd $s$, there exists odd $x<2^{l}$ such that $xs\pm 1\equiv 0\pmod{2^{l+1}}$, where $l\geq 1$.
Proof. Take any $x_1,x_2<2^{l}$. Firstly note that if $x_1s\pm 1\equiv x_2s\pm 1\equiv 0\pmod{2^{l+1}}$, then $x_1\equiv x_2\pmod{2^{l+1}}$, which implies that $x_1=x_2$. This essentially means that as $x$ varies, $xs\pm1$ give different residues mod $2^{l+1}$, similarly $xs\pm 1$ is injective over $F_{2^{l}}$.
Now take $x_1,x_2<2^{l}$ and consider $x_1s\pm 1\equiv x_2s\mp 1\equiv 0\pmod{2^{l+1}}$, which implies that $(x_1-x_2)s\pm 2\equiv 0\pmod{2^{l+1}}$. But note that this implies a contradictions as if $4\mid x_1-x_2$, we get that $4\mid 2$ as $l\geq 1$, which is impossible. But if $x_1-x_2=2k$ for some odd $k$, we get that $ks\pm 1\equiv 0\pmod{2^{l}}$, which contradicts that fact that $xs\pm 1$ is injective over $F_{2^{l}}$.

Therefore, all $xs\pm 1\equiv 0\pmod{2^{l+1}}$ imply different values of $s$, and, as we have $2^{l}$ different congruences, we obtain $2^{l}$ different odd values of $s$, the claim follows. $\square$
Consider numbers in the form $n=2^ls$, where $l\geq 1$ and $s$ is any odd number. By the claim, we get that for any odd $s$, there exists odd $x<2^{l}$ such that $xs\pm 1\equiv 0\pmod{2^{l+1}}$, thus either $xs-1$ or $xs$ works, where both are smaller than $n=2^ls$, we are done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
asbodke
1914 posts
#15 • 1 Y
Y by centslordm
The answer is all $m$ except for the powers of 2, as well as 1. Clearly 1 works.

Let $f(n)=\sum_{i=1}^{n}i$, and suppose $m=2^k$ for $k\ge 1$. Assume for the sake of the contradiction that there existed an even solution $a\le m$. Then $\nu_2(a)\le k$, and $\nu_2(a+1)=0$. Clearly $\nu_2(f(a))\le k+0-1=k-1$, and therefore $m$ cannot divide the sum. Now assume for the sake of contradiction that there existed an odd solution $a$. Then $\nu_2(a)=0,$ and $\nu_2(a+1)\le n$. Repeat.

Now suppose $m=2^k(a)$ for odd $c>1$. Let $a\pmod{2^{k+1}}=b$. It is clear that one of $\tfrac 1b$ and $-\tfrac 1b \pmod{2^{k+1}}$ is less than $2^k$. Let $c$ be this value. If $c=\tfrac 1b$, then $ac-1$ is a valid solution since it is less than $m$ and $f(ac-1)=\tfrac{(ac-1)(ac)}{2}$ which is clearly divisible by both $a$ and $2^k$ since $ac\equiv b\cdot \tfrac 1b=1\pmod {2^{k+1}}$. If $c=-\tfrac 1b$, then $ac$ is a valid solution by the same reasoning.

We have shown that powers of 2 greater than 1 don't work, and every other number works, so we are done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ilikemath40
500 posts
#16 • 1 Y
Y by itslumi
We claim that all $m$ works except for when $m$ is a power of two and is greater than $1$.

Claim 1. All odd $m$ works.
Proof. We know that $T_m=m$ works, but this might not be the smallest, so we have \[ T_m \le m \implies m \ge T_m. \]
Claim 2. $m=1$ works.
Proof. Obvious. If you don't understand why this is true, stop reading this solution and go to first grade, please.

Claim 3. When $m$ is a power of two, it doesn't satify the condition.
Proof. Notice that the condition implies that there exists a positive integer $a$ such that $a(a+1)=2m$. Now if $a$ is even, then $a+1$ is odd which means $\nu_2(a+1)=0$. So $\nu_2(a)+\nu_2(a+1)=\nu_2(a)$. Now let $m=2^b$ and so $\nu_2(2m)=b+1$. Also notice that $\nu_2(a) \le b$ because $a\le m$, and hence a contradiction. The case when $a$ is odd, and $a+1$ is even follows the same logic and we are done.

Claim 4. All $m$ that is even and not a power of two work.
Proof. Let
\begin{align*}
    a&=2^{\nu_2(m)+1} \\
    b&=\frac{m}{2^{\nu_2(m)}}
\end{align*}Now if $a>b$, let $a\equiv x\pmod{b}$. Then let $y$ be the modular inverse of $a \mod b$. This means that $ay \equiv 1 \pmod{b}$ and $0<y<b$. Because we know $0<y<b$, we know that $ay<2m$. Now if $ay\le m$ then we can have $T_m=ay-1$ and we would be done. Now if $ay>m$ then we consider the number $2n-ay$. Notice that
\begin{align*}
    2n-ay \equiv 1 \pmod{b} \\
    2n-ay \equiv 0 \pmod{a} \\
\end{align*}and so we can have $T_m=2n-ay-1$. Using the same proof as above for when $b>a$, we are done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
lazizbek42
548 posts
#17
Y by
Answer:$m=2^s(2t+1)$, with $t \geq  1$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
channing421
1353 posts
#18
Y by
solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
minusonetwelth
225 posts
#19
Y by
Answer: All positive integers that are not powers of $2$ besides $m=1$.

Clearly all odd numbers $n=2k+1$ work as
\[n \mid 1+2+3+\ldots+(2k-2)+(2k-1)+2k=(1+2k)+(2+2k-1)+\ldots+(k+k+1)\]so $T_n\le 2k<2k+1=n$. Another way to see this is that $1+2+\ldots+2k=\frac{2k(2k+1)}{2}=k\cdot (2k+1)$.
Claim 1. If $n>1$ satisfies $n\ge T_n$, then so does $2n\ge T_{2n}$ hold.
Proof claim 1. If $n=2k+1$, with $k$ being odd, then we have
\[2n=4k+2\mid 1+2+\ldots+2k+(2k+1)=\frac{(2k+1)(2k+2)}{2}=(2k+1)(k+1)\]as $k+1$ is even, i.e. $T_{2n}\le 2k+1<2n$. Otherwise, if $k$ is even,
\[2n=4k+2\mid 1+2+\ldots+2k=k(2k+1)=\frac k2(4k+2)\]i.e. $T_{2n}\le 2k<2n$. $\square$
As we have already checked, all odd numbers work, and with this claim all even multiples of odd numbers work, which are exactly all positive integers that are not powers of $2$.
Claim 2: The numbers of the form $n=2^k$, $k>0$ do not satisfy $n\ge T_n$.
Proof of claim 2. If $\ell\le n=2^k$ is even then
\[\nu_2\left(\frac{\ell(\ell+1)}{2}\right)=\nu_2\left(\frac{\ell}{2}\right)=\nu_2(\ell)-\nu_2(2)=\nu_2(\ell)-1<k.\]so $2^k$ cannot divid this sum. We get the same thing when $\ell$ is odd, as $\nu_2{\ell+1}\le k$ as well, so $\nu_2{\ell+1}-1<k.$ $\square$
This finishes the proof. $\blacksquare$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
metricpaper
54 posts
#20
Y by
We claim the set of solutions is $\mathbb{Z}^+ \setminus \{2^e\mid e>1,~ e\in \mathbb{Z}\}$. If $n=2^e$ for an integer $e\geq 2$, then we need $T_n\geq 2^{e+1}-1$ in order for $\nu_2(\tfrac{1}{2}T_n(T_n+1))$ to be at least $e$, since we need either $2^{e+1}\mid T_n$ or $2^{e+1}\mid T_n+1$. Hence none of the powers of $2$ work (other than $1$).

Now suppose that $n=2^e\cdot q$ where $2\nmid q$ and $q>1$ is a positive integer. We want $T_m(T_m+1)\equiv 0\pmod{2^{e+1}}$ and $T_m(T_m+1)\equiv 0\pmod{q}$. Let $q'$ be the inverse of $q \mod 2^{e+1}$. If $q'\leq 2^e$, then we can let $T_n=qq'-1$, since then $2^e\mid \tfrac{1}{2}T_n$ and $q\mid T_n+1$, and furthermore $qq'-1\leq 2^e q-1<n$. If $q'>2^e$, then we can let $T_n=q(2^{e+1}-q')$, since then $q\mid T_n$ and $2^e\mid \tfrac{1}{2}(T_n+1)$, and furthermore $q(2^{e+1}-q')<q\cdot 2^e=n$. Hence all numbers of the form $2^e\cdot q$ work, and we are done.
This post has been edited 1 time. Last edited by metricpaper, Jan 12, 2023, 6:21 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
kamatadu
480 posts
#22 • 1 Y
Y by HoripodoKrishno
Nyess poblam orss :omighty: .

I claim that all non-powers of two work. Let $n=2^k\cdot(2m+1)$. We firstly work with $k\ge 1$. Now I claim that there is a multiple of $2^{k+1}$ among the following,
\begin{align*}
    (2m+1)&\cdot 1\pm 1\\
    (2m+1)&\cdot 3\pm 1\\
    &\vdots\\
    (2m+1)\cdot (&2^k-1)\pm 1
.\end{align*}
First notice that if our claim is actually true, then we will have our proof simply choosing our $T_n$ as the working choice from the above listed for $-1$, otherwise the $T_n=\text{choice}-1$ for $+1$.

Now FTSOC assume that all the ones are non-multiples of $2^{k+1}$. Also notice that all the choices above are even. So we consider their binary representation. So the representation must have its last digit as $0$. Now also notice that all the ones are distinct $\pmod{2^{k+1}}$ which simply follows from a contradiction and some case bashing. Now note that we have at most $2^k-1$ binary representations with $k+1$ digits that are even but are not divisible by $2^{k+1}$ but above, we have $2^{k}$ choices which is a clear contradiction and we are done.

For the case $k=0$, note that taking just taking $T_n=n$ works and we are done. Now for the proof that the powers of $2$ don't work, a simple $\nu_{2}$ contradiction works and we are done.
This post has been edited 1 time. Last edited by kamatadu, Apr 12, 2023, 6:20 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
EpicBird08
1751 posts
#23
Y by
Cool :)
We claim that the answer is $\boxed{\text{all numbers that are not powers of 2 greater than 1.}}$

We will first prove that all such $m$ work. Clearly $m = 1$ works, so assume $m \ne 1.$ Write $m = b \cdot 2^a,$ where $b$ is odd. Obviously $$1 + 2 + \dots + T_n = \frac{T_n (T_n + 1)}{2}.$$Thus we require that $2m| T_m (T_m + 1),$ or, when plugging in values, $2^{a+1} b | T_m (T_m + 1).$ Now, let $p$ be the unique integer between $0$ and $b \cdot 2^{a+1} - 1$ inclusive such that $$p \equiv 0 \pmod{b}$$and $$p \equiv -1 \pmod{2^{a+1}}.$$Such a value for $p$ exists by CRT, and setting $T_m = p$ would work. However, we do not know if $p > b \cdot 2^{a}$ or not. To counter this, we consider the unique integer $q$ between $0$ and $b \cdot 2^{a+1} - 1$ such that $$q \equiv -1 \pmod{b}$$and $$q \equiv 0 \pmod{2^{a+1}}.$$This value of $q$ also exists by CRT, and plugging in $T_m = q$ would also work. We also do not know whether or not $q > b \cdot 2^a.$

The main idea is to add $p$ and $q.$ We end up getting $$p + q \equiv -1 \pmod{b}$$and $$p + q \equiv -1 \pmod{2^{a+1}}.$$Since $p + q \le b \cdot 2^{a+1} \cdot 2 - 2,$ we are forced to have $$p + q = b \cdot 2^{a+1} - 1.$$Say by Pigeonhole, this implies that at least one of $p,q$ is less than or equal to $b \cdot 2^a = m,$ so plugging in that value for $T_m$ will show that all non-powers of two work.

Now we will show that all $m$ of the form $2^k$ where $k \ge 1$ do not work. (Note: the above argument does not work for powers of $2$ since $b = 1$ in that case, and it is illogical to take things modulo $1.$) Once again, we require $2^{k+1} | T_m (T_m + 1).$ At least one of $T_m$ and $T_{m} +1$ is odd, so that forces all of the powers of $2$ to go into one term. But that would mean that $$T_m \ge 2^{k+1} = 2m$$if $T_m$ is even and $T_m \ge 2^{k+1} - 1 = 2m - 1$ if $T_m$ is odd. Since $k \ge 1,$ both yield clear contradictions.

Therefore, the only such $m$ that work are those that are not of the form $2^k,$ where $k > 1,$ as claimed at the beginning.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
john0512
4187 posts
#24
Y by
We claim that the answer is everything that is either not a power of 2 or equal to 1. Let $m=2^a\cdot b$ where $a\geq 0$ and $b\geq 1$ are integers such that $b$ is odd.

The condition is equivalent to the existence of $s\leq 2^a\cdot b$ such that $$s(s+1)\equiv 0\pmod{2^{a+1}\cdot b}.$$By Chinese Remainder Theorem, we can split this into $$s(s+1)\equiv 0\pmod {2^{a+1}}$$$$s(s+1)\equiv 0\pmod b.$$If $b=1$ (e.g. $m$ is a power of 2), then this is clearly not possible, as in the first congruence, $s$ and $s+1$ are opposite parity, so all $a+1$ factors of 2 must come from one of them, which is clearly not possible unless $a=0$ as $s$ is restricted to at most $2^a.$

From now on, assume $b\geq 3$. Call a number $s$ orz if $$s\equiv 0\pmod {2^{a+1}}, s\equiv -1\pmod{b}.$$Call a number $s$ xor if $$s\equiv -1\pmod {2^{a+1}}, s\equiv 0\pmod{b}.$$Note that, modulo $2^{a+1}\cdot b$, there is exactly one orz number, which we call $A$, and one xor number, which we call $B$. Note that $$A\equiv -B-1\pmod{2^{a+1}\cdot b},$$which rearranges to $$A+B\equiv -1\pmod{2^{a+1}\cdot b}.$$Obviously, $2^{a+2}\cdot b-1$ is too high as even if $A$ and $B$ are the largest possible, it is still one away. Thus, we must have $$A+B=2^{a+1}\cdot b-1.$$Thus, by Pidgeonhole, one of $A$ and $B$ is at most $2^a\cdot b-1$. Furthermore, clearly $A$ and $B$ are both nonzero, and both $s=A$ and $s=B$ satisfy $s(s+1)\equiv 0\pmod{2^{a+1}\cdot b},$ hence all non-powers of 2 work as there is some solution at most $m-1$ and we are done. (Amusingly, the part where $b\geq3$ is used is when stating that $A\neq 0$).
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
shendrew7
795 posts
#25
Y by
We claim all positive integers which are not powers of 2 greater than 1 hold.

Clearly, $m=1$ satisfies the condition. We split the rest of the problem into two cases.

Claim: If $m = 2^k$ for a positive integer $k \ge 1$, then $T_m = 2^{k+1} - 1 > 2^k$.

We need $(T_m-1)T_m \equiv 2^{k+1}$. Since $T_m$ and $T_m - 1$ are relatively prime, the least possible value of $T_m$ is $2^{k+1} - 1$, which is greater than $2^k$ for $k \ge 1$. ${\color{blue} \blacksquare}$

Claim: If $m = 2^k \cdot n$ for an odd integer $n \ge 3$, then $T_m < m$.

By CRT, there exist two distant values between $1$ and $m \cdot 2^{k+1}$ such that

\begin{align*}
T_{m_1} &\equiv 0~(\text{mod } n), -1~(\text{mod } 2^{k+1}) \\
T_{m_2} &\equiv -1~(\text{mod } n), 0~(\text{mod } 2^{k+1}). \\
\end{align*}
Note that \[T_{m_1} \equiv 1 - T_{m_2} \implies T_{m_1}~+~T_{m_2} = 2^{k+1} \cdot n - 1 \implies \min(T_{m_1}, T_{m_2}) < 2^k \cdot n - 1 < m,\]
so there exists $T_m$ such that $T_m < m$. ${\color{blue} \blacksquare}$

Thus we know $\boxed{m \text{ can be any positive integer not a power of 2 greater than 1}}$. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
CoolJupiter
925 posts
#26
Y by
A very nice problem. Here is my solution.

We claim that $m \ge T_m$ if and only if $m$ cannot be expressed in the form $2^k$ for some positive integer $k$.

Part I: $m = 2^k$ for positive integers $k$ work.

We begin by showing that if $m = 2^k$, then $m < T_m$. Observe that $S = \sum_{i = 1}^{T_n} i = \frac{T_n(T_n + 1)}{2}$, with $T_n$ and $T_n + 1$ having opposite parities. Hence, $m~|~S$ if and only if $T_n$ or $T_n + 1$ are divisible by $2^{k + 1}$. Thus $T_m = 2^{k + 1} - 1 > 2^k$.

Part II: Integers $m$ that cannot be expressed as $2^k$ where $k$ is a positive integer do not work.

If $\nu_2(m) = 0$, observe that $m~|~\frac{m(m - 1)}{2}$ and $m > m - 1 \ge T_m$. So it is left to consider the case when $m = 2^t \cdot K$ where $2$ does not divide $K$ and $t$ is a positive integer. Then consider the unique integers by Chinese Remainder Theorem $0 \le A, B \le 2^{t + 1} \cdot K$ such that

$$A \equiv 0 \pmod{2^{t + 1}}, -1 \pmod{K}$$$$B \equiv -1 \pmod{2^{t + 1}}, 0 \pmod{K}$$
Then Chinese Remainder Theorem again gives us $A + B \equiv -1 \pmod{2^{t + 1}}$ and $A + B \equiv -1 \pmod{K}$ so $A + B = 2^{t + 1} K - 1$. Now $x = A, B$ both satisfy $n ~ | ~ \frac{x(x + 1)}{2}$ but we can simply choose $\min(A, B) \le m$ and we are done.
This post has been edited 2 times. Last edited by CoolJupiter, Sep 19, 2023, 3:46 PM
Reason: ed
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
RedFireTruck
4223 posts
#27
Y by
Notice that $m|\frac{m(m-1)}{2}$ for all odd $m$. Otherwise, let $m=2^nk$ for some odd $k$. Let odd $b\equiv k^{-1}\pmod{2^{n+1}}$. Then, let $c= bk \equiv 1\pmod{2^{n+1}}$. If $b>2^n$, then let $c= (2^{n+1}-b)k\equiv -1\pmod{2^{n+1}}$. Then, $(2^nk)|\frac{c(c-1)}{2}$ or $(2^nk)|\frac{c(c+1)}{2}$. Notice that if $k=1$, then $c=1\equiv 1\pmod{2^{n+1}}$, but $\frac{0\cdot 1}{2}$ is not a possible sum. Otherwise, $c>1$. Therefore, all integers that aren't $2^z$ for some integer $z>0$ work.
This post has been edited 2 times. Last edited by RedFireTruck, Sep 23, 2023, 7:48 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
joshualiu315
2534 posts
#28
Y by
The answer is $\boxed{\text{all numbers that cannot be written in the form }  2^z, \ z>0}$

First, note that all odd numbers $k$ work since $T_k=k-1$. Now, let $k= a \cdot 2^b$. We would like to have

\[a \cdot 2^{b+1} \mid T_k (T_k+1).\]
Notice for $a>1$, we can let $0 \le p < a \cdot 2^{b+1}$ be a value such that

\[p \equiv 0 \pmod{a}\]\[p \equiv -1 \pmod{2^{b+1}}.\]
This value clearly exists by the Chinese Remainder Theorem, and setting $T_k=p$ works. However, we do not necessarily know that $k \ge p$.

Also, we can let $0 \le q < a \cdot 2^{b+1}$ be a value such that:

\[q \equiv -1 \pmod{a}\]\[q \equiv 0 \pmod{2^{b+1}}.\]
This value exists by CRT, and setting $T_k=q$ works. We still do not know that $k \ge q$, but we have

\[p+q \equiv -1 \pmod{a \cdot 2^{b+1}} \quad \text{and} \quad p+q < 2(a \cdot 2^{b+1})-1\]\[\implies p+q = a \cdot 2^{b+1}-1.\]
Pigeonhole states that at least one of $p,q \le k$.

It now suffices to prove that $k=2^x$ does not work. We must have

\[2^{x+1} \mid T_k(T_k+1).\]
Since $T_k$ and $T_k+1$ are relatively prime, the minimum value is clearly $2^{k+1}-1>2^k$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
dolphinday
1324 posts
#29
Y by
All numbers that aren't perfect powers of $2$ with the exception of $2^0 = 1$ work.

For $m = 2^k$, then $T_m = 2^{k+1} - 1$, so $m \le T_m$.

For $m = n \cdot 2^k$ where $n$ is odd and greater than $3$, we will prove that $T_m \leq m$.

If $k = 0$, then the maximum value of $T_m$ is $m - 1$, so it works.

For $k > 0$, there are two possible values $T_{m_1}$ and $T_{m_2}$ that (could) work.

By CRT, there are values that satisfy
\[T_{m_1} \equiv 0\pmod{n}\]\[T_{m_1} \equiv -1\pmod{2^{k+1}}\]
\[T_{m_2} \equiv -1\pmod{n}\]\[T_{m_2} \equiv 0\pmod{2^{k+1}}\]
For $0 < T_{m_1}, T_{m_2} < n \cdot 2^{k+1}$.

Since both of these values add up to
\[T_{m_1} + T_{m_2} \equiv -1\pmod{n}\]\[T_{m_1} + T_{m_2} \equiv -1\pmod{2^{k+1}}\]\[T_{m_1} + T_{m_2} \equiv -1\pmod{n \cdot 2^{k+1}}\]
So, clearly at least one of $T_{m_1} + T_{m_2}$ is $\leq n \cdot 2^k = m$, so this satisfies our conditions.

Hence, all numbers that aren't perfect powers of $2$ work. (Except for $1$, of course.)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pqr.
174 posts
#30 • 1 Y
Y by dolphinday
Solved with a metric ton of hints

We claim that the answer is every $m$ such that $m$ is not a power of $2$ greater than $1$. It is clear that for all $m$ such that $m=2^k$, $T_m=2^{k+1}-1$ is the smallest possible solution, and this is greater than $m$ for all values of $k \ge 1$.

Now assume that $m$ is not a power of $2$ greater than $1$. We see that in \[x(x+1) \equiv 0 \pmod{2m},\]$T_m$ is the smallest possible value of $x$. Let a solution $T_m$ be $\emph{nontrivial}$ if \[T_m \not\equiv 0 \pmod{2m}\]\[T_m \not\equiv 2m-1 \pmod{2m}.\]Note that if $r$ is a solution, then $(2m-1)-r$ is also a solution. Therefore, if there exists a nontrivial solution, then the condition must be satisfied because $T_m \le \tfrac{2m-1}2=m-\tfrac12$. Then it suffices to show that the number of solutions $x$ to the above congruence is greater than $2$ (or that there exists at least one nontrivial solution).

Because $m$ is not a power of $2$, we write $m=2^a \cdot b$, where $b$ is odd. We have \[x(x+1) \equiv 0 \pmod{2^{a+1} \cdot b}.\]By the Chinese Remainder Theorem, we see that the systems \[x_1 \equiv 0 \pmod{2^{a+1}}\]\[x_1 \equiv -1 \pmod{b}\]and \[x_2 \equiv -1 \pmod{2^{a+1}}\]\[x_2 \equiv 0 \pmod{b}\]produce valid solutions (because $b$ is odd, we can conclude that $2^{a+1}$ and $b$ are relatively prime). In fact, we have \[x_1 \equiv -1-x_2 \pmod{2^{a+1}}\]\[x_1 \equiv -1-x_2 \pmod{b}\]\[\implies x_1 \equiv -1-x_2 \equiv (2m-1)-x_2 \pmod{2m}.\]Therefore there exists at least one nontrivial solution for all such $m$, as desired.
This post has been edited 4 times. Last edited by pqr., Oct 31, 2023, 9:37 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
bjump
1021 posts
#31
Y by
We claim that all $m$ not an even integral power of $2$ work.

Proof they work:
If $m$ is odd, we can just let $T_{m}=m$.
If $m$ is even (and not a power of $2$), let $2^{k}$ be the largest power of $2$ dividing $m$ so that $m=2^{k} \cdot n$.
Consider the $2^{k}$ values all less than $m$:
$$\{n-1, n+1, 3n-1, 3n+1, \dots, (2^{k}-1)n-1, (2^{k}+1)n +1\}$$Note that since $n$ is odd, these numbers are the complete even residue set modulo $2^{k+1}$.
If we take the value call it $a$ in the set such that $2^{k+1}$ divides it, we obtain a value $a$ less than $m$ such that $m \mid 1+ 2 +\dots+a$ concluding this part of the proof.

Proof even power's of $2$ don't work :
Let $m=2^{k}$
$$\frac{T_{m}(T_{m}+1)}{2} \equiv 0 \pmod{2^{k}}$$$$T_{m}(T_{m}+1) \equiv 0 \pmod{2^{k+1}}$$$$T_{m}=2^{k+1}-1$$Which is greater than $2^{k}$, for $k \geq 1$ and we are finished $\square$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Cusofay
85 posts
#32
Y by
We want to show that $m\geq T_m$ for any positive integer $n$ except for powers of $2$ and we ll prove that by CRT. We can easily exclude the case of $m=2^k$ by observing $n\leq 2^{k+1}-1 \Rightarrow v_2(T_n) \leq k-1$.

Now if $m$ isn't a power of $2$. Since $T_n = \frac{n(n+1)}{2}$ it suffices to find an positive integer $n$ for which:

\begin{align}
    n &\equiv 0 \pmod{2^{v_2(m)+1}} \\
    n &\equiv -1 \pmod{\frac{m}{2^{v_2(m)}}}
\end{align}
And since the two numbers are coprime, then such an $n\leq 2m$ exist by CRT. If $n\leq m$ we're done, otherwise oen can see that if $n$ is a solution to the system, so is $2m-n$ and this latter is strictly smaller than $m$.

$$\mathbb{Q.E.D.}$$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
eg4334
637 posts
#33
Y by
Wow, what a cool problem. I believe my solution is different to others posted above.

I claim that the answer is all positive integers other than powers of $2$ greater than $1$.
Let $m=2^n \cdot x$ where $v_2(m) = n$. Then, $T_n$ is the least positive integer such that $$\frac{T_n(T_n+1)}{2^{n+1} \cdot x} \in \text{Z}^{+}$$If $n=0$, then we can set $T_n = m-1$ and the conclusion is true. For the remainder of this proof we will assume $n \geq 1$.
Clearly, if $x=1$ (in other words $m$ is a power of $2$), then the conclusion is false. This is true because either one of $T_n$ or $T_n+1$ cannot have a factor of $2^{n+1}$ without exceeding $m=2^n$.
Note that only one of $T_n$ or $T_n+1$ can have the factors of $2$ in the denominator, and one must hold them all.
Case 1: $T_n$ is the multiple of $2^{n+1}$. Then, we can write $T_n = 2^{n+1} \cdot k$ and then $2^{n+1} \cdot k \leq 2^n \cdot x \Rightarrow k \leq \frac{x}{2}$. Therefore, there is $\frac{x-1}{2}$ possible values of $T_n$ in this scenario.
Case 2: $T_n+1$ is the multiple of $2^{n+1}$. Then by similar reasoning we have that $k \leq \frac{x}{2} + \frac{1}{2^{n+1}}$. Thus, $k$ has $\frac{x-1}{2}$ possible solutions in this case as well, using the fact that $n \geq 1$.
Therefore, we have $x-1$ total possible values of the numerator such that the powers of $2$ cancel out. Clearly, all of the "other" factors (the one without the powers of $2$) have distinct modular residues $\pmod{x}$ (this is simply because $x$ is odd).
Claim: The other factor cannot be equal to $1 \pmod{x}$.
Proof: FTSOC, $k \cdot 2^n + 1 \equiv 1 \pmod{x} \Rightarrow k \equiv 0 \pmod{x}$ which contradicts the bounds on $k$ as said before. The other case follows similarly. $\square$.
Thus, we have $x-1$ distinct modular residues $\pmod{x}$ which cannot be equal to $1 \pmod{x}$. Therefore there must be one equal to $0$, and the result is an integer. We are done. $\square$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
gladIasked
648 posts
#34
Y by
The answer is all $n$ not a perfect power of $2$ (except $1$). For all odd $n$ we see that taking $T_n = n$ works so obviously $T_n\le n$.

To see that powers of $2$ fail, note that we want $2^k \mid \frac{T_n(T_n+1)}{2}$. Thus, we need $2^{k+1}\mid T_n(T_n+1)$. Since $\gcd(T_n, T_n+1) = 1$, we either have $2^{k+1}\mid T_n$ or $2^{k+1}\mid (T_n+1)$. Both of these imply $T_n > 2^k = n$, so we're done.

Now, let $n = 2^k\cdot m$, where $m\ge 3$ is odd. We want $\frac{T_n(T_n+1)}{2}\equiv 0\pmod {2^k\cdot m}\implies T_n(T_n+1)\equiv 0\pmod {2^{k+1}\cdot m}.$ The key is to notice that if there exists a solution $T_n$ to this congruence, then $2^{k+1}\cdot m - T_n - 1$ is also a solution. Therefore, if there exists a solution $T_n\not\equiv 0, -1\pmod {2^{k+1}\cdot m}$, we would be done (either take $T_n$ or take $2^{k+1}\cdot m - T_n - 1$).

Fortunately, this is easy to see. Since $\gcd(m, 2^{k+1})=1$, simply take $T_n \equiv 0\pmod {2^{k+1}}$ and $T_n\equiv -1\pmod m$. There exists an $x$ (by CRT) such that $T_n\equiv x\pmod {2^{k+1}\cdot m}$. We know that $x\ne 0, -1$, so we're done! $\blacksquare$ (Clearly $x(x+1)\equiv 0\pmod {2^{k+1}\cdot m}$).
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
bebebe
992 posts
#35
Y by
We clam that all positive $m \ne 2^a$ for a positive integer $a$ works.


Since $$1+2+\dots+T_n=T_n(T_n+1)/2,$$we know $T_n (T_n+1) \equiv 0 \pmod{2n}.$ Since $(2n-T_n)(T_n+1) \equiv 0 \pmod{2n}$, we know $T_n'=2n-1-T_n$ also satisfies our equation.


By CRT, if $ab=2n$ where $a$ and $b$ are relatively prime, there is a solution to $$T_n \equiv 0 \pmod{a},$$$$T_n+1 \equiv 0 \pmod{b},$$with $T_n \in \{0,1,\dots,ab-1\}=\{0,1,\dots,2n-1\}.$ Note that there are solutions $T_n \ne 0,2n-1$ (this is because $T_n=0$ when $a=2n, b=1$ and $T_n=2n-1$ when $a=1, b=2n$, and there exists $a,b \ne 1$ when $m$ is not a power of $2$). If this $0<T_n \le n,$ we are done. If $2n-1>T_n>n,$ we know $0<2n-1-T_n < n-1$ is also a solution, and we are done. \qed
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
NerdyNashville
13 posts
#36
Y by
Nice Problem with an Elegant Solution
solution
:D
This post has been edited 1 time. Last edited by NerdyNashville, Apr 22, 2025, 5:04 PM
Reason: I forgot to add = solution in hide
Z K Y
N Quick Reply
G
H
=
a