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.

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)

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

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

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.

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

In mikeshadow's proof for lemma 2 would we get full points if we one-line it with kobayashi's theorem?

Kobayashi's theorem does not give you the $p \equiv -1 \pmod{4}$ part, which is crucial for the solution to work.

@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$.

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.

$ 2^\frac{p-1}{2}\equiv-1\pmod p $ doesn't mean 2 is a primitive root of p...

Incomplete proof; hidden now.

Incorrect solution.

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.

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

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 ?

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

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.)

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$

What does number 6 indicate in "number theory 6" ?

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.

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.

I think this is a different approach.

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.

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$

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

Cool proof! Primes congruent to $3\pmod4$ are usually called Gaussian primes iirc.

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

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.

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

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

\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$.

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

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

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.

Nice problem

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.

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$

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.

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$

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.