IMO Shortlist 2012, Number Theory 6

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

IMO Shortlist 2012, Number Theory 6

G H J

Reveal topic tags

modular arithmetic

L

G H BBookmark kLocked kLocked NReply

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.

1547 posts

#1 h Jul 26, 2013, 3:36 PM • 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.

4302 posts

#2 h Jul 29, 2013, 7:59 PM • 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.

76 posts

#3 h Jul 29, 2013, 9:25 PM • 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.

55 posts

#4 h Jul 30, 2013, 1:42 PM • 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.

1547 posts

#5 h Jul 30, 2013, 8:48 PM • 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.

487 posts

#6 h Jul 31, 2013, 9:31 AM • 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

hyperbolictangent

#7 h Aug 1, 2013, 2:52 PM • 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.

543 posts

#8 h Aug 2, 2013, 4:34 AM • 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.

2903 posts

#9 h Aug 2, 2013, 5:43 AM • 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.

1547 posts

#10 h Aug 2, 2013, 10:38 AM • 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.

487 posts

#11 h Aug 2, 2013, 11:06 AM • 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.

105 posts

kmh1

#12 h Aug 2, 2013, 3:07 PM • 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.

179 posts

#13 h Nov 20, 2013, 4:31 PM • 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.

339 posts

#14 h Jun 15, 2014, 6:01 PM • 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

sayantanchakraborty

#15 h Oct 23, 2014, 5:10 AM • 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.

15142 posts

#16 h Oct 23, 2014, 5:45 AM • 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

NguyenHungQuangKhai

#17 h Jan 14, 2016, 4:42 PM • 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.

151 posts

JackXD

#18 h Jan 14, 2016, 6:32 PM • 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.

6878 posts

#19 h Mar 29, 2017, 10:50 PM • 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.

1980 posts

#20 h Jan 3, 2018, 10:00 PM • 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.

77 posts

bdbdbd

#21 h Jan 4, 2018, 12:04 AM • 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.

1595 posts

#22 h Jan 4, 2018, 10:18 AM • 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.

1614 posts

yayups

#24 h Sep 5, 2019, 11:48 PM • 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.

452 posts

aops29

#25 h May 6, 2020, 8:03 AM • 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.

558 posts

#28 h Oct 22, 2020, 10:43 AM • 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.

779 posts

#29 h Nov 8, 2020, 5:35 PM • 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.

11386 posts

#30 h Nov 8, 2020, 5:39 PM

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.

1065 posts

Eyed

#31 h Nov 15, 2020, 1:38 AM

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.

1740 posts

#32 h Dec 27, 2020, 1:39 AM

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.

2726 posts

#33 h Sep 6, 2021, 9:25 PM • 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

7357 posts

DottedCaculator

#35 h Mar 5, 2022, 1:32 AM

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.

579 posts

#36 h Mar 15, 2022, 3:51 AM

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.

41 posts

#37 h Jun 18, 2022, 1:43 PM

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}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

287 posts

JG666

#38 h Jul 25, 2022, 1:33 AM

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.

287 posts

JG666

#39 h Jul 25, 2022, 2:36 AM

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.

2320 posts

oty

#40 h Jul 25, 2022, 2:40 AM • 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.

91 posts

#41 h Jul 28, 2022, 4:07 PM

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.

1481 posts

CT17

#42 h Jan 19, 2023, 3:41 PM

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.

5005 posts

#43 h Feb 20, 2023, 9:33 PM

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.

1455 posts

#44 h Jun 10, 2023, 4:13 AM

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.

50 posts

KOMKZ

#45 h Nov 29, 2023, 9:44 AM

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.

8868 posts

#46 h Aug 21, 2024, 4:52 PM

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.

242 posts

#47 h Apr 22, 2025, 12:55 AM

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

=

© 2025 AoPS Incorporated

a