Start the New Year strong with our problem-based courses! Enroll today!

G
Topic
First Poster
Last Poster
k a January Highlights and 2025 AoPS Online Class Information
jlacosta   0
Jan 1, 2025
Happy New Year!!! Did you know, 2025 is the first perfect square year that any AoPS student has experienced? The last perfect square year was 1936 and the next one will be 2116! Let’s make it a perfect year all around by tackling new challenges, connecting with more problem-solvers, and staying curious!

We have some fun new things happening at AoPS in 2025 with new courses, such as self-paced Introduction to Algebra B, more coding, more physics, and, well, more!

There are a number of upcoming events, so be sure to mark your calendars for the following:

[list][*]Accelerated AIME Problem Series classes start on January 6th and 7th. These AIME classes will run three times a week throughout the month of January. With this accelerated track, you can fit three months of contest tips and training into four weeks finishing right in time for the AIME I on February 6th.
[*]Join our Math Jam on January 7th to learn about our Spring course options. We'll work through a few sample problems, discuss how the courses work, and answer your questions.
[*]RSVP for our New Year, New Challenges webinar on January 9th. We’ll discuss how you can meet your goals, useful strategies for your problem solving journey, and what classes and resources are available.
Have questions? Our Academic Success team is only an email away, write to us at success@aops.com.[/list]
AoPS Spring classes are open for enrollment. Get a jump on 2025 and enroll in our math, contest prep, coding, and science classes today! Need help finding the right plan for your goals? Check out our recommendations page!

Don’t forget: Highlight your AoPS Education on LinkedIn!
Many of you are beginning to build your education and achievements history on LinkedIn. Now, you can showcase your courses from Art of Problem Solving (AoPS) directly on your LinkedIn profile! Don't miss this opportunity to stand out and connect with fellow problem-solvers in the professional world and be sure to follow us at: https://www.linkedin.com/school/art-of-problem-solving/mycompany/ Check out our job postings, too, if you are interested in either full-time, part-time, or internship opportunities!

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
Sunday, Jan 5 - Apr 20
Wednesday, Jan 15 - Apr 30
Monday, Feb 3 - May 19
Sunday, Mar 2 - Jun 22
Friday, Mar 28 - Jul 18
Sunday, Apr 13 - Aug 10

Prealgebra 1 Self-Paced

Prealgebra 2
Wednesday, Jan 8 - Apr 23
Sunday, Jan 19 - May 4 (1:00 - 2:15 pm ET/10:00 - 11:15 am PT)
Monday, Jan 27 - May 12
Tuesday, Jan 28 - May 13 (4:30 - 5:45 pm ET/1:30 - 2:45 pm PT)
Sunday, Feb 16 - Jun 8
Tuesday, Mar 25 - Jul 8
Sunday, Apr 13 - Aug 10

Prealgebra 2 Self-Paced

Introduction to Algebra A
Tuesday, Jan 7 - Apr 22
Wednesday, Jan 29 - May 14
Sunday, Feb 16 - Jun 8 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)
Sunday, Mar 23 - Jul 20
Monday, Apr 7 - Jul 28

Introduction to Algebra A Self-Paced

Introduction to Counting & Probability
Wednesday, Jan 8 - Mar 26
Thursday, Jan 30 - Apr 17
Sunday, Feb 9 - Apr 27 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)
Sunday, Mar 16 - Jun 8
Wednesday, Apr 16 - Jul 2

Introduction to Counting & Probability Self-Paced

Introduction to Number Theory
Tuesday, Jan 28 - Apr 15
Sunday, Feb 16 - May 4
Monday, Mar 17 - Jun 9
Thursday, Apr 17 - Jul 3

Introduction to Algebra B
Tuesday, Jan 28 - May 13
Thursday, Feb 13 - May 29
Sunday, Mar 2 - Jun 22
Monday, Mar 17 - Jul 7
Wednesday, Apr 16 - Jul 30

Introduction to Geometry
Wednesday, Jan 8 - Jun 18
Thursday, Jan 30 - Jul 10
Friday, Feb 14 - Aug 1
Tuesday, Mar 4 - Aug 12
Sunday, Mar 23 - Sep 21
Wednesday, Apr 23 - Oct 1

Intermediate: Grades 8-12

Intermediate Algebra
Friday, Jan 17 - Jun 27
Wednesday, Feb 12 - Jul 23
Sunday, Mar 16 - Sep 14
Tuesday, Mar 25 - Sep 2
Monday, Apr 21 - Oct 13

Intermediate Counting & Probability
Monday, Feb 10 - Jun 16
Sunday, Mar 23 - Aug 3

Intermediate Number Theory
Thursday, Feb 20 - May 8
Friday, Apr 11 - Jun 27

Precalculus
Wednesday, Jan 8 - Jun 4
Tuesday, Feb 25 - Jul 22
Sunday, Mar 16 - Aug 24
Wednesday, Apr 9 - Sep 3

Advanced: Grades 9-12

Olympiad Geometry
Wednesday, Mar 5 - May 21

Calculus
Friday, Feb 28 - Aug 22
Sunday, Mar 30 - Oct 5

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Tuesday, Feb 4 - Apr 22
Sunday, Mar 23 - Jun 15
Wednesday, Apr 16 - Jul 2

MATHCOUNTS/AMC 8 Advanced
Sunday, Feb 16 - May 4
Friday, Apr 11 - Jun 27

Special AMC 8 Problem Seminar A
Sat & Sun, Jan 11 - Jan 12 (4:00 - 7:00 pm ET/1:00 - 4:00 pm PT)

Special AMC 8 Problem Seminar B
Sat & Sun, Jan 18 - Jan 19 (4:00 - 7:00 pm ET/1:00 - 4:00 pm PT)

AMC 10 Problem Series
Sunday, Feb 9 - Apr 27
Tuesday, Mar 4 - May 20
Monday, Mar 31 - Jun 23

AMC 10 Final Fives
Sunday, Feb 9 - Mar 2 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)

AMC 12 Problem Series
Sunday, Feb 23 - May 11

AMC 12 Final Fives
Sunday, Feb 9 - Mar 2 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)

AIME Problem Series A
Tue, Thurs & Sun, Jan 7 - Feb (meets three times each week!)

AIME Problem Series B
Mon, Wed & Fri, Jan 6 - Jan 31 (meets three times each week!)

Special AIME Problem Seminar A
Sat & Sun, Jan 25 - Jan 26 (4:00 - 7:00 pm ET/1:00 - 4:00 pm PT)

Special AIME Problem Seminar B
Sat & Sun, Feb 1 - Feb 2 (4:00 - 7:00 pm ET/1:00 - 4:00 pm PT)

F=ma Problem Series
Wednesday, Feb 19 - May 7

Programming

Introduction to Programming with Python
Friday, Jan 17 - Apr 4
Sunday, Feb 16 - May 4
Monday, Mar 24 - Jun 16

Intermediate Programming with Python
Tuesday, Feb 25 - May 13

USACO Bronze Problem Series
Sunday, Jan 5 - Mar 23
Thursday, Feb 6 - Apr 24

Physics

Introduction to Physics
Friday, Feb 7 - Apr 25
Sunday, Mar 30 - Jun 22

Physics 1: Mechanics
Sunday, Feb 9 - Aug 3
Tuesday, Mar 25 - Sep 2

Relativity
Sat & Sun, Dec 14 - Dec 15 (4:00 - 7:00 pm ET/1:00 - 4:00pm PT)
0 replies
jlacosta
Jan 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
When lcm is equal to factorial?
YLG_123   3
N 3 minutes ago by Perelman1000000
Source: Olimphíada 2024 - Problem 1
Find all pairs of positive integers $(m,n)$ such that
$$lcm(1,2,\dots,n)=m!$$where $lcm(1,2,\dots,n)$ is the smallest positive integer multiple of all $1,2,\dots n-1$ and $n$.
3 replies
YLG_123
Jan 29, 2024
Perelman1000000
3 minutes ago
Geometry with point P inside triangle
Asyrafr09   1
N 21 minutes ago by vanstraelen
Given a triangle $ABC$ with $AB=13$, $BC=14$, $CA=15$. A point P lies inside a triangle $ABC$ such that
$$\angle PAB = \angle PBC=\angle PCA =\alpha$$
Find the value of tan $\alpha$ so it can be define in the form of $\frac{m}{n}$ so that gcd($m,n$)= 1. Determine the value of $m\ +\ n.$
1 reply
Asyrafr09
Dec 27, 2024
vanstraelen
21 minutes ago
2015 solutions for quotient function!
raxu   46
N 28 minutes ago by HamstPan38825
Source: TSTST 2015 Problem 5
Let $\varphi(n)$ denote the number of positive integers less than $n$ that are relatively prime to $n$. Prove that there exists a positive integer $m$ for which the equation $\varphi(n)=m$ has at least $2015$ solutions in $n$.

Proposed by Iurie Boreico
46 replies
1 viewing
raxu
Jun 26, 2015
HamstPan38825
28 minutes ago
easy substitutions for a functional in reals
Circumcircle   8
N 31 minutes ago by AshAuktober
Source: Kosovo Math Olympiad 2025, Grade 11, Problem 2
Find all functions $f:\mathbb{R}\rightarrow\mathbb{R}$ with the property that for every real numbers $x$ and $y$ it holds that
$$f(x+yf(x+y))=f(x)+f(xy)+y^2.$$
8 replies
Circumcircle
Nov 16, 2024
AshAuktober
31 minutes ago
IMO 2010 Problem 4
mavropnevma   122
N 32 minutes ago by Siddharthmaybe
Let $P$ be a point interior to triangle $ABC$ (with $CA \neq CB$). The lines $AP$, $BP$ and $CP$ meet again its circumcircle $\Gamma$ at $K$, $L$, respectively $M$. The tangent line at $C$ to $\Gamma$ meets the line $AB$ at $S$. Show that from $SC = SP$ follows $MK = ML$.

Proposed by Marcin E. Kuczma, Poland
122 replies
mavropnevma
Jul 8, 2010
Siddharthmaybe
32 minutes ago
Clutched problem
mathscrazy   7
N an hour ago by SimplisticFormulas
Source: STEMS 2025 Category A1
Alice and Bob play a game. Initially, they write the pair $(1012,1012)$ on the board. They alternate their turns with Alice going first. In each turn the player can turn the pair $(a,b)$ to either $(a-2, b+1), (a+1, b-2)$ or $(a-1, b)$ as long as the resulting pair has only nonnegative values. The game terminates, when there is no legal move possible. Alice wins if the game terminates at $(0,0)$ and Bob wins if the game terminates at $(0,1)$. Determine who has the winning strategy?

Proposed by Shashank Ingalagavi and Krutarth Shah
7 replies
mathscrazy
Dec 29, 2024
SimplisticFormulas
an hour ago
Sum of digits
EtacticToe   3
N an hour ago by cubres
Source: Own
Let $n$ be a natural number and $s(n)$ denote its sum of digits. Find all $n$ such that $n + s(n) = 2016$.
3 replies
EtacticToe
3 hours ago
cubres
an hour ago
Only consecutive terms are coprime
socrates   33
N 2 hours ago by HamstPan38825
Source: 7th RMM 2015, Problem 1
Does there exist an infinite sequence of positive integers $a_1, a_2, a_3, . . .$ such that $a_m$ and $a_n$ are coprime if and only if $|m - n| = 1$?
33 replies
socrates
Feb 28, 2015
HamstPan38825
2 hours ago
A hard geometry problem related to tangents
Dftioscjg   3
N 2 hours ago by Ianis
Let A and B be two distinct points on a circle (C). The tangents to (C) at A and B intersect at E. Let M be the midpoint of [BE]. The line (AM) intersects the circle (C) at another point C and (EC) intersects it at D. Show that the lines (AD) and (BE) are parallel.
3 replies
Dftioscjg
Today at 1:04 AM
Ianis
2 hours ago
Trigo Manipulation
S.Ragnork1729   2
N 2 hours ago by vanstraelen
P1. If $$\frac{f(x)+1}{f(x)-1}=\frac{sin(x)+2sin(3x)+sin(5x)}{sin(3x)+2sin(5x)+sin(7x)}$$Find $\prod_{r=0}^{3}f(\frac{4^r\pi}{257})$ .
P2. Evaluate $$\prod_{r=1}^{19} \frac{sin(\frac{r\pi}{80})}{sin(\frac{r\pi}{80})-cos(\frac{r\pi}{80})}$$
2 replies
S.Ragnork1729
Dec 27, 2024
vanstraelen
2 hours ago
Two circles, a tangent line and a parallel
Valentin Vornicu   95
N 2 hours ago by optimusprime154
Source: IMO 2000, Problem 1, IMO Shortlist 2000, G2
Two circles $ G_1$ and $ G_2$ intersect at two points $ M$ and $ N$. Let $ AB$ be the line tangent to these circles at $ A$ and $ B$, respectively, so that $ M$ lies closer to $ AB$ than $ N$. Let $ CD$ be the line parallel to $ AB$ and passing through the point $ M$, with $ C$ on $ G_1$ and $ D$ on $ G_2$. Lines $ AC$ and $ BD$ meet at $ E$; lines $ AN$ and $ CD$ meet at $ P$; lines $ BN$ and $ CD$ meet at $ Q$. Show that $ EP = EQ$.
95 replies
Valentin Vornicu
Oct 24, 2005
optimusprime154
2 hours ago
Geometry with orthocenter midpoints and lines being perpendicular
wizixez   1
N 2 hours ago by bluelinfish
Source: Own
Let $ABC$ be an acute triangle with an orthocenter $H$ and altitudes $BB'$ and $CC'$.Let $D=BC \cap B'C'$.If $M$ is the midpoint of $BC$,Show that $DH$ is perpendicular to $AM$.
1 reply
wizixez
2 hours ago
bluelinfish
2 hours ago
An eventually periodic recursive sequence involving floor function
Photaesthesia   9
N 3 hours ago by Fibonacci_math
Source: 2025 China Mathematical Olympiad Day 1 Problem 1
Let $\alpha > 1$ be an irrational number and $L$ be a integer such that $L > \frac{\alpha^2}{\alpha - 1}$. A sequence $x_1, x_2, \cdots$ satisfies that $x_1 > L$ and for all positive integers $n$, \[ x_{n+1} = \begin{cases} \left \lfloor \alpha x_n \right \rfloor & \textup{if} \; x_n  \leqslant L \\\left \lfloor \frac{x_n}{\alpha} \right \rfloor & \textup{if}  \; x_n  > L \end{cases}. \]Prove that
(i) $\left\{x_n\right\}$ is eventually periodic.
(ii) The eventual fundamental period of $\left\{x_n\right\}$ is an odd integer which doesn't depend on the choice of $x_1$.
9 replies
Photaesthesia
Nov 27, 2024
Fibonacci_math
3 hours ago
NT from Ukrainian TST
mshtand1   19
N 3 hours ago by AshAuktober
Source: Ukrainian TST for IMO 2021 P4
Initially, some positive integer greater than 1 is written on the board. Every second one erases number $n$ written on the board at this moment and writes number $n + \dfrac{n}{p}$ where $p$ is some prime divisor of $n$ and this process lasts indefinitely. Prove that number $3$ was chosen as a prime number $p$ infinitely many times.
Proposed by Mykhailo Shtandenko
19 replies
mshtand1
May 2, 2021
AshAuktober
3 hours ago
Strange NT
magicarrow   19
N Nov 30, 2023 by asdf334
Source: Romanian Masters in Mathematics 2020, Problem 6
For each integer $n \geq 2$, let $F(n)$ denote the greatest prime factor of $n$. A strange pair is a pair of distinct primes $p$ and $q$ such that there is no integer $n \geq 2$ for which $F(n)F(n+1)=pq$.

Prove that there exist infinitely many strange pairs.
19 replies
magicarrow
Mar 1, 2020
asdf334
Nov 30, 2023
Strange NT
G H J
G H BBookmark kLocked kLocked NReply
Source: Romanian Masters in Mathematics 2020, Problem 6
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
magicarrow
146 posts
#1 • 11 Y
Y by DPS, pinetree1, amar_04, Loppukilpailija, NJOY, Math-wiz, Idio-logy, MathbugAOPS, centslordm, MatBoy-123, megarnie
For each integer $n \geq 2$, let $F(n)$ denote the greatest prime factor of $n$. A strange pair is a pair of distinct primes $p$ and $q$ such that there is no integer $n \geq 2$ for which $F(n)F(n+1)=pq$.

Prove that there exist infinitely many strange pairs.
This post has been edited 1 time. Last edited by magicarrow, Mar 1, 2020, 11:19 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Loppukilpailija
155 posts
#2 • 19 Y
Y by Dem0nfang, p_square, amar_04, NJOY, fjm30, Supercali, leibnitz, Math-wiz, bumjoooon, Polynom_Efendi, mijail, Mathhunter1, centslordm, ILOVEMYFAMILY, Kobayashi, Kingsbane2139, LoloChen, pavel kozlov, Mango247
Solution.

Remark 1.

Remark 2.
This post has been edited 7 times. Last edited by Loppukilpailija, Mar 1, 2020, 2:05 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Dem0nfang
478 posts
#3 • 1 Y
Y by Mango247
Well, what I will say might seem weird, but $n$ and $n+1$ are co-prime, so their largest prime factors will be different.

Doesn't this imply that $\exists$ infinitely many 'strange' pairs?

@2below What is Kobayashi?
This post has been edited 3 times. Last edited by Dem0nfang, Mar 1, 2020, 10:56 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Sugiyem
115 posts
#4 • 2 Y
Y by trololo23, Mango247
I only found 304 pairs during contest tho :(
This post has been edited 1 time. Last edited by Sugiyem, Mar 1, 2020, 12:16 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ubermensch
820 posts
#5
Y by
Perhaps(rather probably) I’m wildly misinterpreting the problem, but why shouldn’t $n=p^{\alpha}$ with Kobayashi’s finish this off?
What am I saying, just choosing $n=p$ kills this... there’s probably a typo in the problem...
This post has been edited 1 time. Last edited by ubermensch, Mar 1, 2020, 10:45 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
YII.I.
94 posts
#6
Y by
I don't understand the question. Since $(n,n+1)=1$, $F(n)F(n+1)$ must be a product of two distinct primes. So trivial?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
_el_doopa
62 posts
#7 • 1 Y
Y by centslordm
The problem statement is obviously wrong. I think that you need to proof that the complement of strange pairs is infinite. Or the definition should be adjusted.
This post has been edited 1 time. Last edited by _el_doopa, Mar 1, 2020, 10:46 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
WypHxr
189 posts
#8
Y by
Are you sure your statement is right?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
p_square
442 posts
#9 • 4 Y
Y by YII.I., Rg230403, amar_04, aops29
actual problem wrote:
For each integer $n \geq 2$, let $F(n)$ denote the greatest prime factor of $n$. A strange pair is a pair of distinct primes $p$ and $q$ such that there is $\textbf{no}$ integer $n \geq 2$ for which $F(n)F(n+1)=pq$.

Prove that there exist infinitely many strange pairs.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
magicarrow
146 posts
#10
Y by
Corrected problem statement; thanks @above
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
heron1000
138 posts
#13
Y by
https://mathoverflow.net/questions/332901/greatest-prime-factor-of-n-and-n1 has a bit more on this problem.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
rmtf1111
698 posts
#14
Y by
Let $p$ and $q$ be primes such that $q \mid 2^p-1$ and $q\neq F(2^p-1).$ Clearly, there are infinitely many such primes $q.$ Suppose there exists an integer $m$ such that $F(m)F(m+1)=2q,$ then $m$ must be equal to $2^u-1$ for some $u.$ Now, $q$ divides $2^u-1$ iff $p$ divides $u,$ which would imply that $F(m)\neq q,$ hence we achieve a contradiction.


EDIT: Whoops, this is wrong, we do not know if there are infinitely many composite numbers of the form $2^p-1$ for $p$ prime, see #2.
This post has been edited 2 times. Last edited by rmtf1111, Mar 3, 2020, 4:15 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IndoMathXdZ
691 posts
#15 • 3 Y
Y by Sugiyem, Awesome_guy, Aryan-23
Should have spent more effort on problem 6 rather than problem 5 in the contest. Huge mistake :(
Here's a solution with motivation:
The condition of the problem somehow forces us to take either $p$ or $q$ being $2$. Otherwise, it is really hard to deal with something like $2^a \cdot 3^b \pm 1$.
We will prove that the sufficient condition $o_p(2) = o_q(2)$ for two distinct primes $p > q$ implies that $(2,q)$ is strange.
Claim 01. If $p$ and $q$ are distinct odd primes such that $o_p (2) = o_q (2)$ and $p > q$, then $(2,q)$ is strange.
Proof. Notice that since either $F(n)$ or $F(n+1)$ is $2$, then we would have $n = 2^k$ or $n = 2^k - 1$. We would like to prove that for any $q$ such that $q | 2^k - 1$, then $F(2^k - 1) \not= q$, and for any $q$ such that $q | 2^k + 1$, we would have $F(2^k + 1) \not= q$.
If $o_p (2) = o_q (2)$, then we would have $p | 2^k - 1$ as well if $q | 2^k - 1$. Hence, $F(2^k - 1) \ge p > q$.
Furthermore, if $q | 2^k + 1$, then $q | 2^{2k} - 1$. Suppose $p | 2^k - 1$, then we would have $q | 2^k - 1$, as well, forcing $q | 2$, which is a contradiction. Hence, $p | 2^k + 1$ as well, which forces $F(2^k + 1) \ge p > q$.
It suffices to prove that there are infinitely many distinct odd primes $p,q$ such that $o_p (2) = o_q (2)$. This is equivalent to finding infinitely many numbers $i$ such that $2^i - 1$ (or $2^i + 1$) have two distinct primes that doesn't appear in any $2^j - 1$, $j < i$ ($2^j + 1$).
Now, dealing with order and stuffs motivates us to consider $i$ having as least divisors as possible.
Playing with $2^i + 1$ has an advantage instead of $2^i - 1$ because it restricts the order of the primes, which is why I consider $2^i + 1$. Playing with $2^p + 1$ isn't helpful, as we can't factorized it (since we want something such that $2^i + 1$ produces at least 2 new prime, so factoring is a nice option.)
Now, consider $2^{2p} + 1$. Since $p$ is odd. Then, by Sophie Germain Identity, we have
\[ 2^{2p} + 1 = (2^p + 2^{\frac{p + 1}{2}} + 1)(2^p - 2^{\frac{p + 1}{2} } + 1) \]Now, consider the following lemma.
$\textbf{Lemma 02.}$ If an odd prime $q$ satisfy $q | 2^{2p} + 1$, and $q \not= 5$, then $o_q (2) = 4p$.
Proof. Notice that $q | 2^{4p} - 1$. Hence, $o_q (2) | 4p$. But if $o_q (2) | 2p$, then $q | 2^{2p} - 1$, which forces $q | 2$, a contradiction.
Hence, we would have $o_q (2) \in \{ 4, 4p \}$. But if $o_q (2) = 4$, then we would have $q | 2^2 + 1 = 5$. But we assume that $q \not= 5$, hence we would have $o_q (2) = 4p$.
Now, it's tempting to consider $p$ modulo $20$ since we would like to see the behavior of $2^{2p} + 1$ in modulo $25$. Now, notice that if $p \equiv 1 \ (\text{mod} \ 20)$, then we would have $2^{\frac{p + 1}{2}} \equiv 2, -2 \ (\text{mod} \ 25)$.
Hence, one of $2^p + 2^{\frac{p + 1}{2}} + 1$ or $2^p - 2^{\frac{p + 1}{2}} + 1$ is $5$ modulo $25$, and the other is $1$ modulo $25$.
Confirming that $2^p + 2^{\frac{p + 1}{2}} + 1 > 2^p - 2^{\frac{p + 1}{2}} + 1 > 5$ for any prime $p \equiv 1 \ (\text{mod} \ 20)$, and notice that both factors can't have the same odd prime divisor, since it would divide $2 \cdot 2^{\frac{p + 1}{2}}$. Then, each of these factors contribute a new prime $q$ with order $4p$. Therefore, we would have two distinct primes $q_1$ and $q_2$ such that
\[ o_{q_1} (2) = o_{q_2} (2) = 4p \]We are hence finished.

Remark. In the contest, my friend found a solution using $(2, G(2^{2^n} - 1))$ where $G(n)$ is the smallest prime factor of $n$, and $2^{2^n} - 1$ is composite. But unfortunately, the number of composite Fermat number remains open till now.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
PedroBigMan
14 posts
#17
Y by
rmtf1111 wrote:
Let $p$ and $q$ be primes such that $q \mid 2^p-1$ and $q\neq F(2^p-1).$ Clearly, there are infinitely many such primes $q.$ Suppose there exists an integer $m$ such that $F(m)F(m+1)=2q,$ then $m$ must be equal to $2^u-1$ for some $u.$ Now, $q$ divides $2^u-1$ iff $p$ divides $u,$ which would imply that $F(m)\neq q,$ hence we achieve a contradiction.


EDIT: Whoops, this is wrong, we do not know if there are infinitely many composite numbers of the form $2^p-1$ for $p$ prime, see #2.

Am i being dumb or doesnt Catalan Conjecture say this?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
i3435
1347 posts
#18
Y by
Catalan's conjecture says that no perfect powers are 1 apart, except for $8$ and $9$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
TheUltimate123
1739 posts
#19
Y by
Solved with Th3Numb3rThr33.

We will show there are infinitely many strange pairs of the form \((2,q)\).

Claim: For primes \(q<r\), if \(\operatorname{ord}_q(2)=\operatorname{ord}_r(2)\) then \((2,q)\) is a strange pair.

Proof. First note that for \(F(n)F(n+1)\) to be even, there must be a power of two among \(n\), \(n+1\), so \(n\) is either of the form \(2^k-1\) or \(2^k\). Therefore it suffices to show whenever \(q\mid2^k\pm1\) that \(F(2^k\pm1)\ne q\).

Let \(d\) be the common order. Then:
  • If \(q\mid2^k-1\), observe from \(2^d-1\mid2^k-1\) that \(F(2^k-1)\ge F(2^d-1)\ge r>q\).
  • Suppose \(q\mid2^k+1\). Observe that for general primes \(p\), we have \(p\mid2^k+1\) if and only if \(\operatorname{ord}_p(2)\) is even and \(k\equiv\frac12\operatorname{ord}_p(2)\pmod{\operatorname{ord}_p(2)}\).
    Thus \(q\mid 2^k+1\iff k\equiv\frac12d\pmod d\iff r\mid2^k+1\), so \(F(2^k+1)\ge r>q\).
Thus \((2,q)\) is strange. \(\blacksquare\)

Select a large prime \(p\). First I claim we can find prime divisors \(5<q<r\) of \(2^{2p}+1\). Note that \(2^{2p}+1\) is not a multiple of three and \[\nu_5\left(2^{2p}+1\right)=\nu_5\left(4^p-(-1)^p\right)=1.\]By Sophie-Germain we have \[2^{2p}+1=\left(2^p-2^{(p+1)/2}+1\right)\left(2^p+2^{(p+1)/2}+1\right).\]These two factors are relatively prime. One of these factors is divisible by 5, so divide 5 out. Then what remains are two relatively prime divisors each with prime factors greater than 5, so \(q\) and \(r\) exist.

Now note that \(\operatorname{ord}_q(2)=\operatorname{ord}_r(2)=4p\) (since neither order equals 4). We have exhibited infinitely many \(p\), and therefore infinitely many \(q\). This completes the proof.
This post has been edited 1 time. Last edited by TheUltimate123, Dec 24, 2020, 8:22 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
GeronimoStilton
1521 posts
#20 • 1 Y
Y by Mango247
Solution with awang11.

We generate infinitely many primes $q$ for which $F(n)F(n+1)=2q$ has no solution.

Let $p$ be a particular odd prime congruent to $3$ modulo $8$ (of which there are infinitely many by Dirichlet's Theorem on Arithmetic Progressions). Observe the factorization
\[2^{2p}+1=(2^p-2^{(p+1)/2}+1)(2^p+2^{(p+1)/2}+1).\]Moreover, note the two factors are relatively prime, as they have difference $2^{(p+3)/2}$ which certainly divides neither. Since $p\equiv 3\pmod{8}$, we have $5\mid 2^p-2^{(p+1)/2}+1$ and $5\nmid 2^p+2^{(p+1)/2}+1$. Additionally, $5$ divides the expression exactly once by LTE. So let $q$ be the minimal prime divisor of $2^{2p}+1$ that is not $5$. Clearly $q$ is not also the largest prime factor of $2^{2p}+1$.

Claim: $q\mid 2^k+1$ iff $2p\mid k,4p\nmid k$ and $q\mid 2^k-1$ iff $4p\mid k$.

Solution: For the latter case, apply the Euclidean algorithm to see we get $q\mid 2^{\gcd(k,4p)}-1$. Clearly $\gcd(k,4p)=1,2,4$ cannot occur and neither can $\gcd(k,4p)=p,2p$ by assumption, so $4p\mid k$. For the former case, note $q\mid 2^{2k}-1$ so by the second part of the claim this implies $4p\mid 2k$, and clearly $4p\nmid k$. $\fbox{}$

Now, we argue that $F(n)F(n+1)=2q$ cannot occur. If $n=2^k$ for some $k$ then the claim suffices by showing $F(n+1)\ge F(2^{2p}+1)>q$ and similarly if $n=2^k-1$ for some $k$ then $F(n)\ge F(2^{2p}+1)>q$, since either way we get $q$ divides the $2^k\pm1$ term or we are automatically done. The primes $q$ generated are clearly distinct for each such prime $p$ because of the claim, 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.
squareman
966 posts
#21 • 3 Y
Y by rama1728, Catsaway, centslordm
Solved with rama1728.

Claim: If for two odd primes $p < q$ we have $\operatorname{ord}_q(2) = \operatorname{ord}_p(2)$ then $(p,2)$ is strange.

Proof: If $F(n)F(n+1)=2p,$ then either $(n,n+1)$ is either $(2^k, 2^k+1)$ or $(2^k-1, 2^k)$ for some positive integer $k.$ In the latter case, note $p \mid 2^{k}-1 \implies \operatorname{ord}_p(2) \mid k \implies \operatorname{ord}_q(2) \mid k \implies q \mid 2^k-1.$ In the former case, $p \mid 2^{k}+1 \implies \operatorname{ord}_p(2) =\operatorname{ord}_q(2) = 2k \implies q \mid 2^{2k}-1,$ and since $q \nmid 2^k-1$ because $\operatorname{ord}_q(2) \ne k,$ we have $q \mid 2^k+1.$ $\square$

It suffices to show there are infinitely many distinct pairs of odd primes $p,q$ where $\operatorname{ord}_q(2) =  \operatorname{ord}_p(2).$ Take any prime $P = 2k+1 > 5$ (obviously infinitely many) and note
\begin{align*}
2^{2P} + 1 &=4\cdot 2^{4k} + 1\\
&=(2^{2k+1}+2^{k+1}+1)(2^{2k+1}-2^{k+1}+1).
\end{align*}Note $\gcd(2^{2k+1}+2^{k+1}+1, 2^{2k+1}-2^{k+1}+1)=\gcd(2^{k+2}, 2^{2k+1}-2^{k+1}+1)=1,$ $3 \nmid 2^{2P}+1,$ and $25 \nmid 2^{2P}+1$ since $10 \nmid 2P.$ So we can take two distinct primes $p,q > 5$ dividing $2^{2P}+1,$ so $\operatorname{ord}_q(2), \operatorname{ord}_p(2) \mid 4P.$ Obviously now $\operatorname{ord}_q(2), \operatorname{ord}_p(2) > 4,$ so $\operatorname{ord}_q(2) = \operatorname{ord}_p(2) = 4P$ as desired. $\blacksquare$
This post has been edited 2 times. Last edited by squareman, Jan 12, 2022, 2:25 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IAmTheHazard
4993 posts
#22 • 1 Y
Y by centslordm
stupid silly problem. got all the right ideas until i didnt remember SOPHIE GERMAIN so i am dead lmao fascinating

Consider numbers of the form $2^{2p}+1$ for $p$ an odd prime. Note that this number is always divisible by $5$ and never by $3$.

Claim: For sufficiently large $p$, $2^{2p}+1$ has at least two prime divisors other than $5$.
Proof: We use SOPHIE GERMAIN:
$$2^{2p}+1=4\cdot (2^{\frac{p-1}{2}})^4+1^4=(2^p+2^{\frac{p+1}{2}}+1)(2^p-2^{\frac{p+1}{2}}+1).$$Both of these factors are integers, which are coprime (since their gcd divides $2^{\frac{p+3}{2}}$ by using the Euclidean algorithm) and larger than $5$ for all large enough $p$, which implies the desired result. $\blacksquare$

Now, in general, if $p \neq q$ are odd primes, then
$$\gcd(2^{2p}+1,2^{2q}+1) \mid \gcd(2^{4p}-1,2^{4q}-1)=2^{\gcd(4p,4q)}-1=2^4-1=15,$$which implies that it is $5$. Therefore, we can find infinitely many primes $p>5$ such that $p$ divides $2^{2q}+1$ for some (unique) $q$ but $F(2^{2q}+1) \neq p$ by taking the smaller of the two prime divisors supplied by the above claim across all large $q$. I claim that, for these $p$, $(2,p)$ is always a strange pair.

First note that $\mathrm{ord}_p(2)$ is either $4$ or $4q$, but the former would imply that $p \in \{3,5\}$, so it must equal $4q$. Now, if $F(n)F(n+1)=2p$ for some $n$, then either $n$ or $n+1$ is a power of $2$. In the first case, we would have $F(2^k+1)=p$ for some $k$. It is necessary (and sufficient) to have $k \equiv 2q \pmod{4q}$, but this implies that the other prime $p'>p$ dividing $2^{2q}+1$ also divides $2^k+1$: contradiction. In the second, we have $F(2^k-1)=p$ for some $k$. It is necessary (and sufficient) to have $k \equiv 0 \pmod{4q}$, but this again implies that $p'$ (as defined before) also divides $2^k-1$. This implies the desired result. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
asdf334
7562 posts
#23
Y by
Well that was interesting. like @above, I got all the right ideas but focused on $2^p-1$ for prime $p$. I guess I didn't look at the big picture and realize that I needed an explicit factorization trick (new hard skill in the toolkit!)
Z K Y
N Quick Reply
G
H
=
a