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
Both a and a+1997 are roots of P, Q(P(x))=1 has no solutions
WakeUp   2
N 35 minutes ago by Rohit-2006
Source: Baltic Way 1997
Let $P$ and $Q$ be polynomials with integer coefficients. Suppose that the integers $a$ and $a+1997$ are roots of $P$, and that $Q(1998)=2000$. Prove that the equation $Q(P(x))=1$ has no integer solutions.
2 replies
WakeUp
Jan 28, 2011
Rohit-2006
35 minutes ago
greatest volume
hzbrl   1
N 38 minutes ago by hzbrl
Source: purple comet
A large sphere with radius 7 contains three smaller balls each with radius 3 . The three balls are each externally tangent to the other two balls and internally tangent to the large sphere. There are four right circular cones that can be inscribed in the large sphere in such a way that the bases of the cones are tangent to all three balls. Of these four cones, the one with the greatest volume has volume $n \pi$. Find $n$.
1 reply
hzbrl
Yesterday at 9:56 AM
hzbrl
38 minutes ago
Gheorghe Țițeica 2025 Grade 9 P2
AndreiVila   5
N 40 minutes ago by sqing
Source: Gheorghe Țițeica 2025
Let $a,b,c$ be three positive real numbers with $ab+bc+ca=4$. Find the minimum value of the expression $$E(a,b,c)=\frac{a^2+b^2}{ab}+\frac{b^2+c^2}{bc}+\frac{c^2+a^2}{ca}-(a-b)^2.$$
5 replies
+2 w
AndreiVila
Mar 28, 2025
sqing
40 minutes ago
Geometry Parallel Proof Problem
CatalanThinker   4
N an hour ago by CatalanThinker
Source: No source found, just yet, please share if you find it though :)
Let M be the midpoint of the side BC of triangle ABC. The bisector of the exterior angle of point A intersects the side BC in D. Let the circumcircle of triangle ADM intersect the lines AB and AC in E and F respectively. If the midpoint of EF is N, prove that MN || AD.
I have done some constructions, but still did not quite get to the answer, see diagram attached below
4 replies
CatalanThinker
2 hours ago
CatalanThinker
an hour ago
Circle and square
Marrelia   1
N Apr 10, 2025 by sunken rock
Given a circle with center $O$, and square $ABCD$. Point $A$ and $B$ are on the circle, and $CD$ is tangent to the circle at point $E$. Let $M$ represent the midpoint of $AD$ and $F$ represent the intersection between $AD$ and circle. Prove that $MF = FD$.
1 reply
Marrelia
Apr 10, 2025
sunken rock
Apr 10, 2025
Two geometry and algebra problems
Kempu33334   5
N Apr 9, 2025 by joeym2011
Here are two problems I made...

1) Let there be a triangle $ABC$ such that $AB = 5$, $AC = 6$, and $BC = 7$. Then, let the circumcenter of $\triangle ABC$ be $O$. Furthermore, let the reflections of $A$, $B$, and $C$ across $O$, be $A'$, $B'$, and $C'$ respectively. Find $[AB'CA'BC']$.

2) If \[\underbrace{\dfrac{v_2(4!)}{v_2(8!)}\cdot\dfrac{v_2(16!)}{v_2(32!)}\dots}_\text{50 terms} = \dfrac{1}{2^n}\]find $\left\lceil \dfrac{n}{3} \right\rceil$.

@2below Yes, that’s the intended product.
5 replies
Kempu33334
Apr 8, 2025
joeym2011
Apr 9, 2025
Simple Combinatorics on seating in a circle
duttaditya18   6
N Mar 6, 2025 by S_14159
Five persons wearing badges with numbers $1, 2, 3, 4, 5$ are seated on $5$ chairs around a circular table. In how many ways can they be seated so that no two persons whose badges have consecutive numbers are seated next to each other? (Two arrangements obtained by rotation around the table are considered different)
6 replies
duttaditya18
Aug 11, 2019
S_14159
Mar 6, 2025
Ellipse not parallel to x- or y-axis
chess64   9
N Mar 4, 2025 by daijobu
An ellipse has foci at $(9,20)$ and $(49,55)$ in the $xy$-plane and is tangent to the $x$-axis. What is the length of its major axis?
9 replies
chess64
Jan 1, 2006
daijobu
Mar 4, 2025
[PMO25 Qualifying I.14] Grid Division
kae_3   0
Feb 23, 2025
How many ways are there to divide a $5\times5$ square into three rectangles, all of whose sides are integers? Assume that two configurations which are obtained by either a rotation and/or a reflection are considered the same.

$\text{(a) }10\qquad\text{(b) }12\qquad\text{(c) }14\qquad\text{(d) }16$

Answer Confirmation
0 replies
kae_3
Feb 23, 2025
0 replies
Reflection Geometry
Kempu33334   1
N Feb 17, 2025 by Kempu33334
Let there be a triangle $ABC$, and a point $P$. In addition, let the reflections of $P$ across the sides of $\triangle ABC$ be $X,Y,Z$.

1) Prove that $P$ is in the interior of $\triangle XYZ$ if and only if it is in the interior of $\triangle ABC$.

2.1) Prove that it is impossible for $X$, $Y$, $Z$ to all lie inside (not on) $(ABC)$ or provide a counterexample.

2.2) Prove that it is impossible for $A$, $B$, $C$ to all lie inside (not on) $(XYZ)$ or provide a counterexample.

3) Let all points $P$ such that they lie on a singular circle be the set $\mathcal{P}$. Prove that for every point in $\mathcal{P}$, the locus of the corresponding $X$, $Y$, $Z$ are circles.

4) Let all points $P$ such that they lie on a singular line be the set $\mathcal{L}$. Prove that for every point in $\mathcal{L}$, the locus of the corresponding $X$, $Y$, $Z$ is a line.

5.1) Let all points $P$ such that they lie on a singular ellipse be the set $\mathcal{E}$. Prove that for every point in $\mathcal{E}$, the locus of the corresponding $X$, $Y$, $Z$ is an ellipse.

5.2) Let all points $P$ such that they lie on a singular ellipse be the set $\mathcal{E}$. Prove that for every point in $\mathcal{E}$, the locus of the corresponding $X$, $Y$, $Z$ is an ellipse congruent to $\mathcal{E}$.

Note, 3) and 4) are corollaries of 5), so proving that suffices.

6) Generalize.
1 reply
Kempu33334
Feb 16, 2025
Kempu33334
Feb 17, 2025
Geometry
hn111009   0
Feb 17, 2025
Let triangle $ABC.$ $K$ and $H$ be the reflection of $B$ through $CA$ and $C$ through $BA$. Let $E$ be the center of Euler circle of triangle $ABC.$ Prove that $AE$ passed through the center of $\odot(AKH).$
0 replies
hn111009
Feb 17, 2025
0 replies
intermediate algebra
ANGEW   2
N Jan 28, 2025 by ANGEW
Find all pairs of real numbers (a, b) such that (x - a)^2 + (2x - b)^2 = (x - 3)^2 + (2x)^2 for all x.
The answer is (a,b)=(3,0) and (-9/5, 12/5)
By graphing y=2x and plotting these two points, we can see that the two points are reflections upon the line y=2x. Why?
2 replies
ANGEW
Jan 22, 2025
ANGEW
Jan 28, 2025
Questions about angle notation
tsun26   2
N Jan 13, 2025 by AbhayAttarde01
What's the difference between writing $\angle BAL \cong \angle DAC$ and $\angle BAL = \angle DAC$?
2 replies
tsun26
Jan 13, 2025
AbhayAttarde01
Jan 13, 2025
Properties of Reflections
Dachel2018   3
N Dec 28, 2024 by Mathzeus1024
In Cartesian coordinates, prove that it is impossible to map the point $(0,0)$ to the point $(0,1)$ only by using reflections through lines passing through at least 2 lattice points. Clarifications
3 replies
Dachel2018
Dec 27, 2024
Mathzeus1024
Dec 28, 2024
IMO Shortlist 2012, Number Theory 6
mathmdmb   42
N Apr 22, 2025 by ihategeo_1969
Source: IMO Shortlist 2012, Number Theory 6
Let $x$ and $y$ be positive integers. If ${x^{2^n}}-1$ is divisible by $2^ny+1$ for every positive integer $n$, prove that $x=1$.
42 replies
mathmdmb
Jul 26, 2013
ihategeo_1969
Apr 22, 2025
IMO Shortlist 2012, Number Theory 6
G H J
Source: IMO Shortlist 2012, Number Theory 6
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mathmdmb
1547 posts
#1 • 9 Y
Y by Davi-8191, tenplusten, anantmudgal09, Limerent, paccongnong19hy, rightways, Adventure10, Mango247, and 1 other user
Let $x$ and $y$ be positive integers. If ${x^{2^n}}-1$ is divisible by $2^ny+1$ for every positive integer $n$, prove that $x=1$.
This post has been edited 1 time. Last edited by Amir Hossein, Jul 29, 2013, 5:49 PM
Reason: Edited Title and Changed Format of The Problem.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
math154
4302 posts
#2 • 7 Y
Y by sco0orpiOn, IsaacJimenez, Nathanisme, AFSA, Kobayashi, Adventure10, and 1 other user
Suppose $x>1$ for contradiction. Let $S$ be the set of primes dividing $2^n y+1$ for some $n$.

First note that if $p^\ell\mid 2^n y+1$ for prime $p$ and $n,\ell>0$, then $p^\ell\mid x^{2^n}-1$ yields $p\perp x$ and thus $p^\ell\mid x^{\gcd(2^n,\phi(p^\ell))}-1$. But $p$ is odd, so in fact $p^\ell\mid x^{\gcd(2^n,p-1)}-1$. Since $x>1$, we immediately deduce the following:

(1) For fixed $p\in S$, there exists $t_p>0$ such that $v_p(2^n y+1)\le t_p$ for all $n$. (Otherwise, $x^{p-1}-1$ has infinitely many factors of $p$.)

(2) For fixed $k$, the set $S_k$ of $p\in S$ with $v_2(p-1) \le k$ is finite. (Otherwise, $x^{2^k}-1$ has infinitely many prime factors.)

Now let $T = \{ q: q\mid 2y+1\} \subseteq S$ and fix a positive integer $N$ (to be fully determined later). Then
\begin{align*}
A = A(N) &= 2^{1+(N+1)\prod_{p\in S_N}(p-1)}y+1\\
&= \prod_{\substack{p\mid A \\p\in S_N}} p^{v_p(A)}\prod_{\substack{p\mid A \\p\notin S_N}} p^{v_p(A)} \\
&\equiv \prod_{\substack{p\mid 2y+1 \\p\in S_N}} p^{v_p(A)} = \prod_{p\in T\cap S_N}p^{v_p(A)} \pmod{2^{N+1}}.
\end{align*}Note that $v_p(A) > 0$ for all $p\in T$. But $A\equiv 1\pmod{2^{N+1}}$ by construction, so for sufficiently large $N$, we have $T\subseteq S_N$ and
\[ N \ge \max_{1\le k_p\le t_p\forall p\in T} v_2(-1 + \prod_{p\in T} p^{k_p}). \]Thus $v_2(A - 1) \le N < N+1$, which is absurd. (Alternatively, we can take $N$ such that $2^{N+1} > -1+\prod_{p\in T} p^{t_p}$.)

Comment. The key is finding (1) and (2); the rest is working out details.

Edit. Darn, the solutions below are much more efficient (we can easily show $S_1$ has to be infinite), but I guess I'll leave this here anyway.
This post has been edited 1 time. Last edited by math154, Jul 31, 2013, 3:18 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
sco0orpiOn
76 posts
#3 • 5 Y
Y by math154, Kobayashi, Adventure10, Mango247, and 1 other user
there is different approach ( :)i hope i am not wrong)

let $A= 2^{1+t\prod_{p \in S_N \cup T}(\phi(p^{t_{p}+1}))}y+1=\prod_{\substack{p\mid A\\p\in S_N}}p^{v_p(A)}\prod_{\substack{p\mid A\\p\notin S_N}}p^{v_p(A)}\\ \&\equiv\prod_{\substack{p\mid 2y+1\\p\in S_N}}p^{v_p(A)} =2y+1$ (mod $2^{N+1}$)

the las one is because $V_P(A)=V_P(2y+1)$ is true for every $P \in S_N \cup T$
so this is a contradiction because $1 \equiv A \equiv 2y+1 (mod 2^{N+1}) $because we can put $N$ big enough that $2^{N+1}>2y$

and i hope we are done :)

(sorry for typo issues ,i am trying to learn latex)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mikeshadow
55 posts
#4 • 20 Y
Y by Burii, sco0orpiOn, math154, mad, leader, ThirdTimeLucky, bcp123, tenplusten, pavel kozlov, pablock, Kanep, Kobayashi, mijail, aqua4689, rcorreaa, myh2910, richrow12, Adventure10, Mango247, and 1 other user
I have a slightly different approach.

Consider the following Lemmas:

Lemma 1: Consider the integers $x,y$, if for some prime $p$ we have that $p|x^2+y^2$ and $p\equiv -1 \pmod 4$ then $p|x$ and $p|y$.
Proof:Suppose that $p\not |x$ and $p \not |y$. Because $x^2 \equiv -y^2 \pmod p$ we get that $\left ( \dfrac{-1}{p}  \right ) = 1$, but we also have that $\left ( \dfrac{-1}{p}  \right ) = (-1)^{\dfrac{p-1}{2}} = -1$ , thus a contradiction, so $p|x$ and $p|y$.

Lemma 2: For a fixed positive integer $y$,there are infinitely many primes $p$ such that $p \equiv -1 \pmod 4$ and $p|2^ny+1$ for some positive integer $n$.
Proof: First suppose that $y$ is odd (because we can take $n:=n-v_2(y)$ throughout the proof). Now suppose that there are only finitely many $p$ that satisfy the condition, we include all of them in the set $P$, also take $Q$ to be the set of primes $p$ such that $p|2y+1$. If we let $n=\phi( \prod_{p \in P \cup Q} p)\phi(2y+1)+1$ then $2^ny+1 \equiv 2y+1 \pmod{ (2y+1)\prod_{p \in P \cup Q} p} $ so $2^ny+1=k(2y+1)( \prod_{p \in P \cup Q} p) + 2y+1 = (2y+1)( (\prod_{p \in P \cup Q} p)k+1)$, because $n>1$ and $2y+1 \equiv -1 \pmod 4$ we have that $(\prod_{p \in P \cup Q} p)k+1 \equiv -1 \pmod 4$, so there exists a prime $q$ such that $q \equiv -1 \pmod 4$ and $q|(\prod_{p \in P \cup Q} p)k+1$, but $q \not \in P\cup Q$, so we get a contradiction.

Main Proof:Suppose that there is a prime $q$ such that $q|2^ny+1$ and $q \equiv -1 \pmod 4$, then we get that $q | x^{2^{n}}-1=(x-1)(x+1)(x^2+1)(x^4+1)...(x^{2^{n-1}}+1)$, from our Lemma 1 we get that $q$ cannot divide $x^{2^{m}}+1$ for any positive integer $m$, so $q|x^2-1$, but from Lemma 2 we get that there are infinitely many $q$ so $x^2-1=0$ or $x=1$.
This post has been edited 1 time. Last edited by mikeshadow, Aug 2, 2013, 3:54 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mathmdmb
1547 posts
#5 • 1 Y
Y by Adventure10
My solution is same but the proof for lemma 2 is different. First note that, $2$ is a primitive root for any prime $p$ of the form $8k+5$. That is, for every $r$, there is an $x$ s.t. $2^x\equiv r\pmod p$. Now, since the number of prime factors of $y$ of this form is finite, take any prime $q$ of this form greater than the greatest prime factor of $y$ of this form and greater than $x-1$ as well. Then, there is an $n$ s.t. $2^n\equiv(q-1)e\mod q$ where $ye\equiv1\mod q$. This implies there is an $n$ with $q|2^ny+1$ implying $q|x-1$. This gives $x-1=0$ or $x=1$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
dibyo_99
487 posts
#6 • 2 Y
Y by Adventure10, Mango247
mathmdmb wrote:
First note that, $2$ is a primitive root for any prime $p$ of the form $8k+5$.

I don't think this is true. I know that for every prime of the form $8k+5$ where $2k+1$ is prime, $2$ is a primitive root but I never heard of this. As far as I know, the infinitude of primes such that $2$ is a primitive root modulo them is a special case of the unsolved Artin's conjecture.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
hyperbolictangent
961 posts
#7 • 2 Y
Y by Adventure10, Mango247
This is probably not essentially too different from the other solutions here, but I feel like it might be a little less confusing:

Write $2y + 1 = p_1^{e_1}p_2^{e_2} \dots p_r^{e_r}$. Let $N = v_2(2y + 1) + 1$, so that $2y + 1$ and all its prime divisors are not $1$ modulo $2^N$. Call a number $a$ good if $a \not \equiv 1 \pmod{2^N}$.

We claim the sequence $\{2^ny + 1\}_{n \in \mathbb{N}}$ has infinitely many good prime divisors. Suppose, for the sake of contradiction, there were finitely many of them. Let the ones distinct from the $p_i$ be $q_1, q_2, \dots, q_s$. Choose $M$ such that \[\text{ord}{}_q{}_i(2) | M\] \[\text{ord}_{(p_i)^{e_i + 1}}(2) | M\] \[M \ge N\] and consider $2^{M + 1}y + 1$. Notice that $2y + 1 | 2^{M + 1}y + 1$ and that $2^{M + 1}y + 1$ is not good. But $2y + 1$ is good, so \[Q = \frac{2^{M + 1}y + 1}{2y + 1}\] must be good as well. In particular, it must have a good prime divisor. But $p_i \nmid Q$, since \[2^{M + 1}y + 1 \equiv 2y + 1 \pmod{p_i^{e_i + 1}}\] and $p_1^{e_i} || 2y + 1$. Similarly, $q_i \nmid Q$ since \[2^{M + 1}y + 1 \equiv 2y + 1 \pmod{q_i}\] and $q_i \nmid 2y + 1$. Then $2^{M + 1}y + 1$ has a prime divisor distinct from all the $p_i$ and $q_i$, contradiction.

Now remark that \[{x{}^{2{}^n} - 1 = (x - 1)\prod_{j = 1}^{n - 1}{x{}^{2{}^j} + 1}}\] and all odd prime factors of $x{}^{2{}^k} + 1$ are $1 \pmod{2^k}$. Then if $g$ is a good prime divisor of $2^{n}y + 1$ for some $n$, \[g | (x - 1) \prod_{j = 1}^{N - 1}{x{}^{2{}^j} + 1} \; \; \; \; (1) \]
However, we have established there are infinitely many good prime divisors of the sequence $\{2^ny + 1\}$ and so the RHS is a bounded quantity divisible by infinitely many primes, which is impossible unless it equals zero; that is, $x = 1$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Wolstenholme
543 posts
#8 • 2 Y
Y by Adventure10, Mango247
In mikeshadow's proof for lemma 2 would we get full points if we one-line it with kobayashi's theorem?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
dinoboy
2903 posts
#9 • 4 Y
Y by tenplusten, Adventure10, Mango247, and 1 other user
Kobayashi's theorem does not give you the $p \equiv -1 \pmod{4}$ part, which is crucial for the solution to work.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mathmdmb
1547 posts
#10 • 2 Y
Y by Adventure10, Mango247
@dibyo, My construction at this part was wrong. But $2$ indeed is a primitive root for all prime $p\equiv5pmod8$. I hadn't shown $2^ny+1$ has an infinite prime divisor of the form $4k+3$ as it was required.
$\left(\dfrac2p\right)=-11$, so $2^\frac{p-1}2\equiv-1\pmod p$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
dibyo_99
487 posts
#11 • 2 Y
Y by Adventure10, Mango247
http://mathoverflow.net/questions/8345/reference-of-primitive-root-mod-p

But, this doesn't say so. I also looked up at Wikipedia and even there, it is mentioned that this is not known whether there are infinitely many primes such that $2$ is a primitive root modulo them. A counter-example is the prime $109$ which is of the form $8k+5$ but $ord_{109}(2)=36$.

Actually, I had the same idea in the beginning so I did a lot of research on this topic and found my idea wrong.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
kmh1
105 posts
#12 • 2 Y
Y by Adventure10, Mango247
$ 2^\frac{p-1}{2}\equiv-1\pmod p $ doesn't mean 2 is a primitive root of p...
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Particle
179 posts
#13 • 2 Y
Y by mad, Adventure10
Incomplete proof; hidden now.
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.
AnonymousBunny
339 posts
#14 • 1 Y
Y by Adventure10
Incorrect solution.
This post has been edited 1 time. Last edited by AnonymousBunny, Jun 24, 2016, 6:54 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
sayantanchakraborty
505 posts
#15 • 2 Y
Y by Adventure10, Mango247
Note that the sequence $(2^ny)_{n \ge 1}$ only has finitely many primes dividing its terms, namely $2$ and all the prime factors of $y$. This sequence is also unbounded.
Hence by Kobayashi's theorem the sequence $(2^ny+1)_{n \ge 1}$ has infinitely many prime factors dividing its terms. Now since $x$ is fixed we are assured that there can only be finitely many prime factors of $x$. So there are infinitely many prime factors in the sequence not dividing $x$. Take such an odd prime $p$. Then $p\mid x^{2^m}-1$ for some $m$ and $p\mid x^{p-1}-1$ imply $p\mid x^{\gcd(2^m,p-1)}-1$, so $p\mid x^2-1$. Thus there exist infinitely many prime factors of $x^2-1$, which is impossible unless $x=1$.

EDIT:Oops here a proof that there are infinitely many primes $\equiv 3\pmod{4}$ is needed.Sorry and thanks for pointing out my mistake.
This post has been edited 1 time. Last edited by sayantanchakraborty, Oct 23, 2014, 8:54 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mavropnevma
15142 posts
#16 • 3 Y
Y by FlakeLCR, Adventure10, and 1 other user
Since $2^ny+1 \mid x^{2^n} - 1$, any prime factor of $2^ny+1$ does not divide $x$, so some part of your argument is not needed.
Unfortunately, it is not true that $p\mid x^{\gcd(2^m,p-1)}-1$ implies $p\mid x^2-1$, since of course $\gcd(2^m,p-1)$ is not always equal to $2$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
NguyenHungQuangKhai
16 posts
#17 • 1 Y
Y by Adventure10
how we can thinking like that
i do not good at number theory . Do anybody have some experience about way of thinking in number theory ?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JackXD
151 posts
#18 • 2 Y
Y by Adventure10, Mango247
The main idea is to prove that there exists infinitely many primes $\equiv 3\pmod{4}$ dividing some number of form $2^ny+1$.
If we show this for odd $y$,it automatically follows for any even $y$.(as $x^2+1 \equiv 0\pmod{p}$ has a solution if and only if $p \equiv 1\pmod{4}$)
An obvious approach is contradiction.Suppose there are finitely many primes $q_1,q_2,\cdots,q_r \equiv 3\pmod{4}$ which divide some number of form $2^ny+1$ (and doesn't divide $2y+1$ )
Let $2y+1={p_1}^{\alpha_1}{p_2}^{\alpha_2}\cdots {p_s}^{\alpha_s}$
Take $n=1+\phi({p_1}^{\alpha_1+1}{p_2}^{\alpha_2+1}\cdots {p_s}^{\alpha_s+1}{q_1}{q_2}\cdots{q_r})$
Then $2^ny+1 \equiv 2y+1 \pmod{{p_1}^{\alpha_1+1}{p_2}^{\alpha_2+1}\cdots {p_s}^{\alpha_s+1}{q_1}{q_2}\cdots{q_r}}$
This forces ${p_i}^{\alpha_i} || 2^ny+1$ and ${q_j}$ doesn't divide $2^ny+1$ for all $i,j$.
Thus $2^ny+1 \equiv 2y+1  \equiv 3\pmod{4}$
But this contradicts the fact that $n \ge 2$,so $2^ny+1 \equiv 1\pmod{4}$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6877 posts
#19 • 6 Y
Y by karitoshi, mijail, v4913, nguyennam_2020, myh2910, Adventure10
Let $c=2y+1$ and $r$ such that $2^r > c + 1$. We say a prime $p$ is lawful if $p \equiv 1 \pmod{2^r}$ and chaotic otherwise. Then it will be sufficient to prove that:

Lemma: Infinitely many chaotic primes divide $2^n y + 1$ for some $n$.

Proof. Assume for contradiction only finitely many chaotic primes, and select a large odd integer $M$ such that $\nu_p(M) > \nu_p(c)$ for every such prime $p$. Then \[ z \overset{\text{def}}{=} 2^{1 + \varphi(M)} y + 1 \equiv 2y + 1 \pmod M. \]So $\nu_p(z) = \nu_p(c)$ for all chaotic primes $p$. But $z \equiv 1 \pmod{2^r}$ and $c \not\equiv -1 \pmod{2^r}$, contradiction. $\blacksquare$

(In fact one can show in more or less the same way there are infinitely many $3 \pmod 4$ primes, as many users did above.)
This post has been edited 1 time. Last edited by v_Enhance, Jan 4, 2023, 4:32 AM
Reason: typo
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
anantmudgal09
1980 posts
#20 • 1 Y
Y by Adventure10
mathmdmb wrote:
Let $x$ and $y$ be positive integers. If ${x^{2^n}}-1$ is divisible by $2^ny+1$ for every positive integer $n$, prove that $x=1$.

Let $x>1$. Fix $N, M>0$ sufficiently large. Let $S$ be the set of all primes $p$ with $p \mid 2^ny+1$ for some $n>M$ and $p \not \equiv 1 \pmod{2^N}$.

Claim. $S$ is infinite.

(Proof) Suppose $S=\{p_1, \dots, p_k\}$ is finite. Let $A=\left(\prod^k_{j=1} p_j\right)^s$ for some $s$ sufficiently large. Let $n \equiv 1 \pmod{\phi(A)}$. Then $2^ny+1 \equiv 2y+1 \pmod A$. Consequently $\gcd(2^ny+1, A)=d$ is fixed for all such $n$.

Now any prime divisor of $2^ny+1$ other than elements of $S$ is $1 \pmod{2^N}$. Hence $1 \equiv 2^ny+1 \equiv d \pmod{2^N}$. However $(d-1)<2^N$ yields $d=1$, a contradiction! $\blacksquare$

Now pick a prime $p \not \equiv 1 \pmod{2^N}$ with $p>x^{2^N}$ and $p \mid 2^ny+1$ for some huge $n$ (do lifting if necessary). If $p \mid x^{2^n}-1$ and $r=\text{ord}_p(x)$ then $r=2^b$ for some $b \ge 0$. However $x^r-1 \ge p$ so $r \ge 2^N$ hence $r \mid p-1 \implies 2^N \mid p-1$ a contradiction! $\blacksquare$
This post has been edited 1 time. Last edited by anantmudgal09, Jan 3, 2018, 10:05 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
bdbdbd
77 posts
#21 • 1 Y
Y by Adventure10
What does number 6 indicate in "number theory 6" ?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MarkBcc168
1595 posts
#22 • 1 Y
Y by Adventure10
It was 6th problem in the Shortlist booklet. The shortlisted problems in each subjects were sorted by increasing order of difficulty but sometimes it may not accurate.
This post has been edited 1 time. Last edited by MarkBcc168, Jan 4, 2018, 10:19 AM
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
#24 • 3 Y
Y by aops29, mijail, Adventure10
We claim that the sequence $2^ny+1$ has infinitely many prime factors that are $3\pmod{4}$. Suppose for sake of contradiction that there were only finitely many. Letting $y=z2^r$ where $z$ is odd, we have that
\[Z:=(2z+1,4z+1,\ldots,2^nz+1,\ldots)\]also has only finitely many prime factors that are $3\pmod{4}$. Note that $2z+1\equiv 3\pmod{4}$, so let $p_1^{e_1}\cdots p_k^{e_k}\mid z$ be the part of the prime factorization of $2z+1$ that includes only the $3\pmod{4}$ primes (the fact that $2z+1\equiv 3\pmod{4}$ ensures that $k\ge 1$). Also, let $q_1,\ldots,q_\ell\equiv 3\pmod{4}$ denote all the other prime factors that are $3\pmod{4}$ that appear in the sequence $Z$.

Let
\[n=p_1^{e_1}(p_1-1)\cdots p_k^{e_k}(p_k-1)(q_1-1)\cdots(q_\ell-1).\]We see that $2^n\equiv 1\pmod{p_i^{e_i+1}}$ for all $i$ and $2^n\equiv 1\pmod{q_j}$ for all $j$. Thus, $p_1^{e_1}\cdots p_k^{e_k}$ fully divides $2^{n+1}y+1$ and $q_1,\ldots,q_\ell$ don't divide $2^{n+1}y+1$. Thus, the $3\pmod{4}$ part of the prime factorization of $2^{n+1}y+1$ is the same as it is for $2y+1$, so
\[2^{n+1}y+1\equiv 2y+1\equiv 3\pmod{4},\]which is our desired contradiction.

Now, if $p\equiv 3\pmod{4}$, then $p\mid x^{2^n-1}\implies p\mid x^2-1$ by looking at the order of $x$ mod $p$. So we have arbitrarily large $p\equiv 3\pmod{4}$ dividing $2^ny+1$, which divides $x^{2^n}-1$, so $p\mid x^2-1$ for arbitrarily large $p$. Thus, $x^2-1=0$, so $x=1$, as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
aops29
452 posts
#25 • 2 Y
Y by AmirKhusrau, Mango247
I think this is a different approach.

Solution

EDIT: This is a fakesolve. It is not known whether there are infinitely many such primes. If there are only finitely many such primes, and we take \(y\) to be the product of all these primes, my proof fails. Accordingly, I would be very pleased if someone did show this.
This post has been edited 2 times. Last edited by aops29, May 6, 2020, 8:27 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Aryan-23
558 posts
#28 • 2 Y
Y by Nathanisme, Mango247
Call a prime to be "asdf" if it not $1\pmod {2^N}$ for some large integer $N$ such that $2^N>2y+1$.

Claim : Infinitely many asdf primes divide $2^n\cdot y+1$ for some $n>N$.

Proof : Assume that there are only finitely many such asdf primes $p_1,p_2,\dots, p_k$ and define $P$ to be their product. Consider a integer $r > \operatorname{max} \{\nu_{p_i}(2y+1)\}$ and set :

$$ a = 2^{\varphi (P^r)+1}\cdot y+1 \equiv 2y+1 \pmod {P}$$
Since $\nu_{p_i}a = \nu_{p_i}(2y+1)$ , this means that $a\equiv 2y+1$ modulo all asdf primes . However then we have :

$$ a \equiv 2y+1 \neq -1 \pmod {2^N}$$
So we have a contradiction.

Note that for all asdf primes $p$ we have, by orders that $p \mid x-1$. Take $p$ to be huge and conclude. $\blacksquare$
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
#29 • 4 Y
Y by JG666, Mango247, Mango247, Mango247
Solution with hint from GeronimoStilton.

Say a prime is $\emph{quaint}$ if it is congruent to $3$ mod $4.$

$\textbf{Key Claim: }$ There are arbitrarily large quaint primes that divide some term of the sequence $\{2^{i}y+1\}_{i\ge 2}.$

$\emph{Proof: }$ If the claim is true for $y=2c,$ then it is clearly true for $y=c$ as well. Hence we may assume $y$ is odd, so $2y+1\equiv 3\pmod{4}.$

Assume the only quaint primes dividing some term of the sequence are $p_1,p_2,\dots,p_m,$ and let $2y+1=p_{1}^{e_1}p_{2}^{e_2}\dots p_{m}^{e_m}.$ Since $2y+1\equiv 3\pmod{4},$ we know $e_1+e_2+\dots+e_m$ is odd.

Let $N=1+\prod_{i=1}^{m}\varphi(p_{i}^{e_i+1}).$ By Euler's Totient Theorem, we have $2^{N}y+1\equiv 2y+1\pmod{p_i^{e_{i+1}}}$ for all $i.$ Therefore, $p_{i}^{e_i}$ divides $2^{N}y+1$ if and only if it divides $2y+1.$

But this implies that an odd number of quaint primes divide $2^{N}y+1,$ which is a contradiction as $2^{N}y+1\equiv 1\pmod{4}.$ $\blacksquare$

Now take a quaint prime $q>x^{2}-1$ dividing $2^{n}y+1$ for some $n.$ Note that $$q\mid 2^{n}y+1\mid x^{2^{n}}-1\implies q\mid (x^2-1)\prod_{i=1}^{n}(x^{2^i}+1).$$By Fermat's Christmas Theorem, $q$ cannot divide $x^{2^{i}}+1$ for any $i\ge 1,$ so we must have $q\mid x^2-1.$ This is impossible unless $x^2-1=0,$ so $x=1.$
This post has been edited 1 time. Last edited by amuthup, Nov 8, 2020, 10:09 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jasperE3
11310 posts
#30
Y by
Cool proof! Primes congruent to $3\pmod4$ are usually called Gaussian primes iirc.
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
#31
Y by
Hopefully this works:

FTSOC, assume $x > 1$. Fix $y$.

Consider some $p | 2^{i}y + 1$. Then, since $p | x^{2^{i}} - 1$, this implies the order of $x\mod p$ is a power of $2$, so let $ord_{p}(x) = 2^{j}$. Denote $f(i) = 2^{i}y + 1$ Then, observe that
\[2^{j}(2^{i}y + 1) \equiv 2^{i+j}y + 2^{j} \equiv 2^{i+j}y + 1 \equiv 0\mod p\]This means that if $p | f(i)$ and $ord_{p}(x) = 2^{j}$, then $p | f(i+j)$.

I claim that if $2^{n}y + 1 | x^{2^{n-i}} - 1$, then we also have $2^{n}y + 1 | x^{2^{n-i-1}} - 1$. For any $p | f(n)$, if $p | x^{2^{n-i-1}} + 1$, then
\[x^{2^{n-i-1}} \equiv -1 \mod p \Rightarrow ord_{p}(x) = 2^{n-i} \Rightarrow 2^{n-i} | p-1\]Furthermore, since $p | f(n)$, we have $p | f(n + n - i) = f(2n-i)$. This means $p | gcd(f(n), f(2n-i))$, so
\[p | gcd(2^{2n-i}y + 1, 2^{n}y + 1) = gcd(2^{n}y + 1, 2^{n-i} - 1) \Rightarrow p | 2^{n-i} - 1\]Since $2^{n-i} | p-1, p | 2^{n-i} - 1$, we have $2^{n-i} \leq p-1 < p \leq 2^{n-i} - 1$, a contradiction. Therefore, we cannot have $p | x^{2^{n-i-1}} + 1$, which means $gcd(f(n), x^{2^{n-i-1}} + 1) = 1$. Since $f(n) | x^{2^{n-i}} - 1 = (x^{2^{n-i-1}} - 1)(x^{2^{n-i-1}} + 1)$, we must have $f(n) | x^{2^{n-i-1}} - 1$.

Observe that $f(n) | x^{2^{n-0}} - 1$. This means that $f(n) | x^{2^{n-1}} - 1, x^{2^{n-2}} - 1, \ldots x^{2^{n-(n-1)}} - 1$, so $f(n) | x^{2} - 1$. Taking large enough $n$ will give $f(n) > x^{2} - 1$, the desired contradiction. Therefore, the only possible value of $x$ is $1$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
TheUltimate123
1740 posts
#32
Y by
Solved with Th3Numb3rThr33. Let \(N=\nu_2(y)+2\). I contend:

Claim: There are infinitely many primes not of the form \(1\pmod{2^N}\) in the sequence \(2y+1\), \(2^2y+1\), \(2^3y+1\), \ldots.

Proof. Assume for contradiction there are finitely many such primes \(p_1\), \ldots, \(p_k\). Select (possibly zero) exponents \(e_1\), \ldots, \(e_k\) such that \(p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\parallel2y+1\); that is, so that \[\frac{2y+1}{p_1^{e_1}\cdots p_k^{e_k}}\equiv1\pmod{2^N}.\tag{1}\]
Consider \[M=1+k\varphi\left(p_1^{e_1+1}p_2^{e_2+1}\cdots p_k^{e_k+1}\right),\]where \(k\) is chosen such that \(M\ge N\).

Then \(2^My+1\equiv2y+1\pmod{p_i^{e_i+1}}\), i.e.\ \(\nu_{p_i}(2^My+1)=e_i\), for each \(i\), so we must have \[\frac{2^My+1}{p_1^{e_1}\cdots p_k^{e_k}}\equiv1\pmod{2^N},\tag{2}\]
Combining \((1)\) and \((2)\), we have \[2y+1\equiv p_1^{e_1}\cdots p_k^{e_k}\equiv2^My+1\equiv1\pmod{2^N},\]contradiction since \(2y\equiv2^{N-1}\pmod{2^N}\) by design. \(\blacksquare\)

Finally, write \[x^{2^n}-1=\left(x^{2^{n-1}}+1\right)\left(x^{2^{n-2}}+1\right)\cdots\left(x^2+1\right)(x+1)(x-1).\]Select one of the (infinitely many) primes \(p\not\equiv1\pmod{2^N}\) that divides \(2^ny+1\) for some \(n\) but does not divide \[\left(x^{2^{N-2}}+1\right)\left(x^{2^{N-2}}+1\right)\cdots(x+1)(x-1).\]
Then \(p\) must divide \[\left(x^{2^{n-1}}+1\right)\left(x^{2^{n-2}}+1\right)\cdots\left(x^{2^{N-1}}+1\right),\]i.e.\ \(p\) divides \(x^{2^k}+1\) for some \(k\ge N-1\). But \(x^{2^k}\equiv-1\pmod p\) implies \(\operatorname{ord}_p(x)=2^{k+1}\), i.e.\ \(2^{k+1}\mid p-1\). This is a contradiction.
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
#33 • 1 Y
Y by mijail
We prove that the sequence $\{2^ky + 1\}_{k = 1}^{\infty}$ has infinitely many $3 \pmod 4$ prime divisors.

FTSoC that all prime factors of all $2^ky + 1$ (fixed $y$, varying $k$) come from a finite set of primes $\{p_1, p_2, \ldots , p_{\ell}\}$. WLOG $y$ is odd, since if it even and equal to $2^ry'$ where $y'$ is odd it suffices to show the result for $y'$. Say\[2y + 1 = p_1^{e_1}\ldots p_{\ell}^{e_{\ell}} \equiv 3 \pmod 4\]where $e_i$ are nonnegative. Choose\[A = 1 + \phi((2y+1)p_1\ldots p_{\ell}) = 1 + \phi(p_1^{e_1 + 1}\ldots p_{\ell}^{e_{\ell} + 1})\]and note that $2^{A} \equiv 2 \pmod{p_i^{e_i+1}}$ hence $2^Ay + 1 \equiv 2y + 1 \pmod{p_i^{e_i+1}}$ for each $i$. This tells us that $v_{p_i}(2^Ay + 1) = v_{p_i}(2y + 1)$ for all $p_i$, and since we know that only the $p_i$ can divide $2^Ay + 1$, we have $2^Ay + 1 = 2y+1$, size contradiction.

This would allow us to pick an arbitrarily large $n = N$ for which some arbitrarily large prime $p \equiv 3 \pmod 4$ satisfies $p \mid 2^Ny + 1$ while $2^Ny + 1 \mid x^{2^N} - 1$, indicating that the order of $x$ modulo $p$ is $\gcd(2^N, p - 1) = 2$. This would imply $p \mid x^2 - 1$ but since we can choose $p$ to be arbitrarily large, this implies $x^2 - 1 = 0 \implies x = 1$.
This post has been edited 1 time. Last edited by jj_ca888, Sep 6, 2021, 9:25 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
DottedCaculator
7351 posts
#35
Y by
Let $y=2^am$ where $m$ is odd. Then, since $2m+1\equiv3\pmod4$, this means that the number of primes $3$ mod $4$ that divide $2m+1$ is odd. Let these primes be $p_1$, $p_2$, $\ldots$, $p_k$. Suppose that the number of $3$ mod $4$ primes that divide a number of the form $2^ny+1$ is finite, then let these primes be $q_1=p_1$, $q_2=p_2$, $\ldots$, $q_k=p_k$, $q_{k+1}$, $\ldots$, $q_b$. Then, let $n=-m+1+z(q_1-1)(q_2-1)\ldots(q_b-1)$ for sufficiently large $z$. We have $2^ny+1\equiv2^{-m+1}y+1\equiv2m+1\pmod{q_i}$. Therefore, $q_i\mid2^ny+1$ if and only if $1\leq i\leq k$. Since $n>1$ for sufficiently large $z$, this means that it is equivalent to $1$ mod $4$. However, $p_1p_2\ldots p_k\equiv3\pmod4$, which is a contradiction.

Therefore, there exists infinitely many primes equivalent to $3$ mod $4$ that divide a number of the form $2^ny+1$, so it must divide a number of the form $x^{2^n}-1=(x^2-1)(x^2+1)(x^4+1)\ldots(x^{2^{n-1}}+1)$. Since all prime factors of $x^{2^k}+1$ are $1$ mod $4$ or equal to $2$, this means that all of the primes must divide $x^2-1$, which is only possible when $x=1$.
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
#36
Y by
\textbf{Claim: } There are infinitely many primes $\equiv 3 \pmod{4}$ that divide $2^ny+1$.

WLOG remove all factors of 2 from $y$. This only adds a finite number of new factors. Now, AFTSOC that there's a finite number of such primes: $p_1,\ldots, p_N$. Then select $M$ divisible by $p^{e_i-1}(p-1)$ where $v_{p}(2y+1) < e_i$. Thus, we have
\[2^{M+1}y +1 \equiv 2y+1 \pmod{p^{e_i}}\]and the same set and multiplicity of $\equiv 3\pmod{4}$ primes divide both terms. However, the RHS is $\equiv 3\pmod{4}$ while the LHS is $\equiv 1 \pmod{4}$, contradiction. Thus, there are an infinite number of primes dividing $2^ny+1$. $\square$.

Note that we can factor $x^{2^n}-1 = (x-1)(x+1)(x^2+1)\cdots (x^{2^{n-1}}+1)$. Consider the infinite number of $p\equiv 3\pmod{4}$, by Fermat's Christmas Theorem they all divide either $x-1$ or $x+1$. However, if $x>1$, this is clearly impossible because both are finite, and thus the only option is to set $x=1$ and we're done. $\blacksquare$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
myh2910
41 posts
#37
Y by
v_Enhance wrote:
$z \equiv -1 \pmod{2^r}$ and $c \not\equiv -1 \pmod{2^r}$
I guess there's a typo, it should be $z\equiv 1\pmod{2^r}$ and $c\not\equiv 1\pmod{2^r}$ :P
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JG666
287 posts
#38
Y by
Here is a harder version of this problem:

Let $x,y$ be positive integers. Given that for any positive integer $n$, the following holds:
$$(ny)^2+1\mid x^{\varphi(n)}-1$$Show that $x=1$.
This post has been edited 1 time. Last edited by JG666, Jul 25, 2022, 1:34 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JG666
287 posts
#39
Y by
Solution to the above harder version:

Take $n=3^k$. We have
$$(3^ky)^2+1\mid x^{2\cdot 3^{k-1}}-1$$
Pick any prime $p\equiv 2\pmod 3$ and let $\delta_p(x)=d$. This gives
$$d\mid \gcd (2\cdot 3^{k-1}, p-1)\mid 2\implies d=2 \implies p\mid x^2-1$$Henceforth we wish the set $A:=\{(3^ky)^2+1\mid k\in \mathbb {N_+}\}$ produces infinitely many prime factors which are $\equiv 2\pmod 3$. We proceed by assuming the contrary.

Denote $y^2+1=\prod_{i=1}^s p_i^{e_i}$, where $p_1, \cdots, p_s$ are from the finite set of prime factors $\equiv 2\pmod 3$ in $A$. Suppose there are $q_1, \cdots, q_t$ left in $A$. To reach the desired contradiction, we wish to construct a new $(3^ky)^2+1$ that misses all $q_1, \cdots, q_t$. The idea is like the classical proof to the infinitude of primes by Euclid. Specifically, pick
\begin{align*}
(3^ky)^2+1 &\equiv \prod_{i=1}^s p_i^{e_i}\pmod {M = p_1^{e_1+1}\cdots p_s^{e_s+1}\cdot q_1\cdots q_t} \\ 
&= y^2+1 \\ 
\end{align*}which is equivalent to $3^{2k}\equiv 1\pmod M$. ETT tells us this is possible. The end.

Remark: If one chooses $n=2^k$, then use primes of $8k+5$ to reach the desired contradiction similar to the above process.
This post has been edited 3 times. Last edited by JG666, Jul 25, 2022, 3:05 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
oty
2314 posts
#40 • 1 Y
Y by Mango247
Nice problem
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Number1048576
91 posts
#41
Y by
solution
This post has been edited 1 time. Last edited by Number1048576, Jul 28, 2022, 4:22 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
CT17
1481 posts
#42
Y by
Assume $x > 1$. Let $2^a$ be the least power of $2$ greater than $2y + 1$, let $P$ be the product of all primes less than $x^{2^a}$, and let $r$ be the maximum $v_p(2y+1)$ over all $p | 2y + 1$. Consider the number $2^{N+1}y + 1$ where $N = a\varphi(P^{r+1})$. We have $v_p(2^{N+1}y+1) = v_p(2y + 1)$ for all $p < x^{2^a}$ and $2^{N+1}y + 1\equiv 1\not\equiv 2y+1\pmod{2^a}$, so $2^{N+1}y + 1$ is divisible by some prime $q > x^{2^a}$ such that $q\not\equiv 1\pmod{2^a}$. Then we should have

$$q | x^{\gcd (q-1,2^{N+1})} - 1| x^{2^a} - 1$$
a size contradiction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IAmTheHazard
5001 posts
#43
Y by
Let $a_n=2^ny+1$. Most of the problem is the following claim.

Claim: There exist infinitely many $3 \pmod{4}$ primes which divide some $a_i$.
Proof: WLOG let $y$ be odd. Then $a_1=2y+1 \equiv 3 \pmod{4}$ so we can write
$$2y+1=p_1^{e_1}\ldots p_k^{e_k}A,$$where all $p_i$ are $3 \pmod{4}$ primes, $e_i\geq 1$ for all $i$, and $A$ is the product of $1 \pmod{4}$ primes only, so $A \equiv 3 \pmod{4}$. Define
$$P=\prod_{i=1}^k \mathrm{ord}_{p_i^{e_i+1}}(2).$$Then we have $\nu_{p_i}(a_{1+nP})=e_i$ for all $i$ and positive integers $n$. Hence there must also be some $3 \pmod{4}$ prime not equal to one of $p_1,\ldots,p_k$ which divides $a_{1+mP}$, for each $m$ separately, else $a_{1+mP} \equiv 3 \pmod{4}$ which is false.
Suppose that there are finitely many such primes and call them $q_1,\ldots,q_a$. Let
$$Q=\prod_{i=1}^a \mathrm{ord}_{q_i}(2).$$Then there exists some $q_i$ dividing $a_{1+QP}$, but then $q_i \mid a_1$ as well, which contradicts our construction. Thus there must be infinitely many such primes, which implies the desired result. $\blacksquare$

To finish, note that $p \mid 2^ny+1 \mid x^{2^n}-1 \implies \mathrm{ord}_p(x) \mid 2^n$. On the other hand $\mathrm{ord}_p(x) \mid p-1$ in general, so if $p \equiv 3 \pmod{4}$ then we must have $\mathrm{ord}_p(x) \in \{1,2\} \implies p \mid x^2-1$. By our claim, there are infinitely many such $p$, so we must actually have $x^2-1=0 \implies x=1$, as desired. $\blacksquare$
This post has been edited 3 times. Last edited by IAmTheHazard, Feb 20, 2023, 9:36 PM
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
#44
Y by
Nice problem! Interesting to view generators and such.

Notice if large $p \equiv 3 \pmod 4$ divides any $y2^n+1$, the game is over by orbits and a million other equivalent methods. So it suffices to find these big primes. Remove all factors of $2$ from $y$ for ease.

Now assume there are finitely many such primes. Then let the primes be $p_1, p_2, \ldots, p_k$.

Notice that $p \mid y2^n+1 \Longleftrightarrow p \mid 2^m + y$ for some $m$.

Now if $y \equiv 1 \pmod 4$, then notice that $y+2$ is $3 \pmod 4$, so noting that $2^m+y = (2^m - 2)+(2+y)$, simply choose $m$ such that all the $v_{p_i}$ in $2^m - 2$ are greater than the $v_{p_i}$ in $y+2$ and we are done. This choice of $m$ is always possible by LTE.

A similar argument applies if $y \equiv 3 \pmod 4$ by noting $y+4$ is $3 \pmod 4$, and then repeating the same LTE argument.
This post has been edited 2 times. Last edited by Inconsistent, Jun 10, 2023, 4:15 AM
Reason: edit
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
KOMKZ
50 posts
#45
Y by
If my solution is wrong tell please
Ok lets fix $y$ and we can take $n$ such that ,$n$ huge and $(x-1;2^ny+1)=1$ from one lemma we can see for every prime divisors of $2^ny+1$ we have $\equiv 1 \pmod{2^n}$ lets take two prims divisors $p,q$ but $p\cdot q \geq (2^n+1)(2^n+1)>2^ny+1$ so its mean for huge $n$ we have $2^ny+1$ is prime and its easy to sea its impossible
P.s. after we did $(x-1;2^ny+1)=1$ we can have
$\dfrac{x^{2^{n}}-1}{x-1}$ divisble by $2^ny+1$
This post has been edited 3 times. Last edited by KOMKZ, Nov 29, 2023, 9:48 AM
Reason: Latex
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
HamstPan38825
8861 posts
#46
Y by
The main claim of the problem is the following:

Claim: Infinitely many primes $p \equiv 3 \pmod 4$ divide some term of the sequence $\{2^n y + 1\}_{n=1}^\infty$.

Proof. we may assume $y$ is odd. Suppose that only finitely many $p_1, p_2, \dots, p_k$ do. We fix a large $N$ such that $\nu_{p_i}(N) > \nu_{p_i} (2y+1)$ for each $i$; decomposing $2y+1$ into its $1$ mod $4$ and $3$ mod $4$ parts as $2y+1 = A_1A_3$, consider
\[2^{1+\varphi(N)} y + 1 \equiv 2y+1 \pmod N \implies 2^{1+\varphi(N)}y + 1 = B_1A_3\]for some $B_1$ a product of $1$ mod $4$ primes.

It so follows that $2^{1+\varphi(N)}y + 1 \equiv 2y+1 \equiv 3 \pmod 4$, which is clearly impossible. $\blacksquare$

However, all such infinitely many primes $p_i$ must divide $x^2 - 1$ by orders or Fermat Christmas, which is a clear contradiction.

Remark: The analytic approach is motivated by the fact that looking at any particular prime $p$ (whether ad-hoc constructing a $p \mid 2^ny+1$ or analyzing invariants mod $p$) doesn't quite work. The main difficulty of the problem is realizing that looking at $3$ mod $4$ primes on a general scope actually works; the mod $4$ contradiction is honestly pretty cute.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ihategeo_1969
235 posts
#47
Y by
This is the main claim.

Claim: $P=\mathbb{P} \{(2^ny+1)_{n \ge 0} \}$ contains infinitely many $3 \bmod 4$ primes.
Proof: Assume not. WLOG let $y$ be odd then $2y+1 \equiv 3 \pmod 4$ so there are some $q \equiv 3 \pmod 4$ primes such that $\nu_q(2y+1)$ is odd. Let $q_1$, $\dots$, $a_t$ be all such primes (see that $t$ is odd).

Let $p_1$, $\dots$, $p_\ell$ be all other $3 \bmod 4$ primes which are still in $P$. Let \[N :=\prod p_i \cdot \prod q_i^{\nu_{q_i}(2y+1)+1}\]Hence see that \[z_k := 2^{1+k \varphi(N)}y+1 \equiv 2y+1 \pmod N\]Say a prime $p \equiv 3 \pmod 4$ divides $z_k$ then it divides $2y+1$ and so it must be one of the $q_i$ (conversely all $q_i \mid z_k$) but $\nu_{q_i}(z_k)=\nu_{q_i}(2y+1)$ by construction but remembering thr fact that $t$ is odd we get \[z_k=(4A+1) \prod_{i=1}^t q_i^{\nu_{q_i}(2y+1)}=(4A+1)(4B+3) \equiv 3 \pmod 4\]But obviously $z_k \equiv 1 \pmod 4$ for large $k$, so we get a contradiction. $\square$

Hence let $p \equiv 3 \pmod 4$ be a prime factor of $2^ny+1$ and hence \[p \mid x^{2^n}-1 \iff \operatorname{ord}_p(x) \mid \gcd(2^n,p-1)=2 \iff p \mid x^2-1\]But $p$ can be really massive so this forces $x=1$.
Z K Y
N Quick Reply
G
H
=
a