RMM 2013 Problem 1

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

RMM 2013 Problem 1

G H J

Reveal topic tags

modular arithmetic

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

354 posts

#1 h Mar 2, 2013, 10:36 AM • 5 Y

Y by Davi-8191, Mathuzb, ILOVEMYFAMILY, Adventure10, Rounak_iitr

For a positive integer $a$ , define a sequence of integers $x_1,x_2,\ldots$ by letting $x_1=a$ and $x_{n+1}=2x_n+1$ for $n\geq 1$ . Let $y_n=2^{x_n}-1$ . Determine the largest possible $k$ such that, for some positive integer $a$ , the numbers $y_1,\ldots,y_k$ are all prime.

Z K Y

The post below has been deleted. Click to close.

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

354 posts

#2 h Mar 2, 2013, 11:10 AM • 3 Y

Y by ILOVEMYFAMILY, Adventure10, Mango247

Z K Y

The post below has been deleted. Click to close.

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

224 posts

#3 h Mar 2, 2013, 3:03 PM • 2 Y

Y by Adventure10, Mango247

Sorry just a stupid post

!

This post has been edited 2 times. Last edited by siddigss, Mar 18, 2013, 6:55 PM

Z K Y

The post below has been deleted. Click to close.

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

354 posts

#4 h Mar 2, 2013, 3:40 PM • 3 Y

Y by Adventure10, Mango247, Rounak_iitr

siddigss wrote:

Click to reveal hidden text

Your solution is obviously wrong because if $a\equiv 2 \mod 3$ then $4a+3\equiv 2\neq 0 \mod 3$ .

By the way, if you try to find some prime $p$ such that $p\mid x_n$ for some $n$ you will never find such prime letting $a\equiv -1 \mod p$ .

Z K Y

The post below has been deleted. Click to close.

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

1514 posts

ksun48

#5 h Mar 2, 2013, 10:03 PM • 4 Y

Y by Illuzion, CHLORG1, ILOVEMYFAMILY, Adventure10

I claim that the answer is two.
If $x_1 = 2$ , then $x_2 = 5$ , $x_3 = 11$ . $2^2-1 = 3$ and $2^5-1=31$ are primes, but $2^11-1 = 23\cdot 89$ is not a prime. (this achieves $k = 2$ )
Assume $x_1$ is odd from now on.

Lemma: if $2^k-1$ is prime, then $k$ is prime.
Proof: If $p\mid k$ , then $2^p-1 \mid 2^k-1$ .

Now, assume to the contrary that $k > 2$ , so that $2^{x_1}-1$ , $2^{x_2}-1$ , and $2^{x_3}-1$ are all prime. Then $x_3 = 4x_1+3$ , and since $x_1$ is odd, $x_3 \equiv 7 \pmod{8}$ . By the lemma, $x_3$ is prime. Thus $2$ is a quadratic residue mod $x_3$ . Let $2 = k^2 \pmod{x_3}$ . Then $2^{x_2}-1 \equiv k^{2x_2}-1 = k^{x_3-1}-1 \equiv 0 \pmod{x_3}$ by Fermat's Little Theorem. Thus $y_3 \mid 2^{x_2}-1$ , and $2^{x_2}-1 > x_3$ (unless $x_3 = 5$ or $x_3 = 7$ , which don't work), a contradiction to the fact that $2^{x_2}-1$ is prime.

Thus the minimum $k$ is two.

Z K Y

The post below has been deleted. Click to close.

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

541 posts

#6 h Mar 3, 2013, 1:05 AM • 2 Y

Y by Adventure10, Mango247

I do not quite like the fact that quadratic reciprocity is really the only nice way to solve this problem.. there should be a nicer method that does not invoke such mechanics. Does anyone else have a nice more elementary solution to this problem?

Z K Y

The post below has been deleted. Click to close.

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

2903 posts

#7 h Mar 3, 2013, 3:36 AM • 4 Y

Y by Adventure10, Mango247, ehuseyinyigit, and 1 other user

Computing $\left ( \frac{2}{p} \right )$ is rather simple and extremely elementary... the full strength of reciprocity laws is not needed.

Z K Y

The post below has been deleted. Click to close.

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

183 posts

#8 h Apr 2, 2013, 3:32 PM • 2 Y

Y by Adventure10, Mango247

I will use $M_n$ to denote the $n-th$ Mersenne Number which is $2^n-1$

Now observe that a necessary condition for $M_n$ to be prime is that $n$ should be prime.
Now also observe that for primes $p$ and $q=2p+1$ we have $q|M_p$ if $p\equiv 3(mod4)$
So assume $a\equiv 1(mod4)$ .
Now $x_2=2a+1\equiv 3(mod4)$ and it is a prime for $y_2$ to be a prime.
So if $x_3=2(2a+1)+1$ is a prime, $x_3|y_2$ , thus the maximum such $k$ is 2 - added that $x_3$ , and thus $y_3$ is composite.

Z K Y

The post below has been deleted. Click to close.

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

487 posts

#9 h Apr 3, 2013, 6:14 AM • 1 Y

Y by Adventure10

Firstly, $x_n = 2^{n-1}(a+1) -1$
Using basic properties of Mersenne primes, if $y_i$ s are primes, $x_i$ s must also be primes.
Assuming $k>2$ , $x_1, x_2, x_3$ are all primes.
So, $a$ is a prime, $2a+1$ is a prime and also $4a+3$ is a prime.

Then by using Euler's criterion,
$2^{2a+1}-1 \cong 2^{\frac{(4a+3)-1}{2}}\cong \left( \frac{2}{4a+3} \right)(mod$ $4a+3)$
Suppose now that $a=2$ . Then, we see that $y_3= 2^{11} -1= 2047=23.89$ , contradiction.
So, $a$ must be odd. Therefore $4a+3 \cong 7(mod$ $8)$ .
So we have $2^{2a+1} \cong \left( \frac{2}{4a+3} \right) \cong 1(mod$ $4a+3)$ , since $2$ is a quadratic residue modulo any prime of the form $8m+7$ .

Z K Y

The post below has been deleted. Click to close.

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

243 posts

#10 h Oct 19, 2016, 8:12 AM • 2 Y

Y by Adventure10, Mango247

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

#11 h Dec 13, 2018, 1:41 PM • 1 Y

Y by Adventure10

Hmm, I feel this is a bit too hard for a #1, though not sure. The key lemma took me a while to find.

The answer is $k=2$ . Suppose we had a chain of length $3$ . Clearly, if $y_n$ is prime, then so is $x_n$ (because $2^a-1\mid 2^b-1$ if $a\mid b$ ). We have the following miraculous lemma:

Lemma: All the $x_i$ for $i\le k$ except potentially $x_1$ are not $1$ or $7$ mod $8$ .

Proof of Lemma: Note that if $x_{n+1}\equiv 1,7\pmod{8}$ , then $2$ is a QR mod $x_{n+1}$ . Therefore, $2^{(x_{n+1}-1)/2}\equiv 1\pmod{x_{n+1}}$ , so $x_{n+1}\mid 2^{x_n}-1=y_n$ . But $y_n$ is prime, so we must have $x_{n+1}=y_n$ , so $2x+1=2^x-1$ for $x=x_n$ . It is easy to see that $2x+1=2^x-1$ has no solutions for positive integers $x$ . Therefore, we have the desired contradiction. $\blacksquare$

Now, note that the action of $2x+1$ mod $8$ is given by
$\begin{align*} 0&\mapsto 1\\ 1&\mapsto 3\\ 2&\mapsto 5\\ 3&\mapsto 7\\ 4&\mapsto 1\\ 5&\mapsto 3\\ 6&\mapsto 5\\ 7&\mapsto 7.\\ \end{align*}$ Since our chain of length $3$ can't have anything that's $1$ or $7$ except the start, the last element can only be $1,2,5,6$ , so only $5$ . Therefore, the chain is $2,5,3$ . Now, if $x_1\equiv 2\pmod{8}$ then $x_1=2$ (because its has to be prime), which we can verify doesn't work. $\blacksquare$

This post has been edited 1 time. Last edited by yayups, Dec 13, 2018, 4:31 PM

Z K Y

The post below has been deleted. Click to close.

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

1218 posts

#12 h Dec 14, 2018, 7:52 AM • 2 Y

Y by Adventure10, Mango247

Nice problem. Although it's easily doable if one knows what are Mersenne Primes. Anyway, here's my solution: Let $M_s=2^s-1$ denote the $s^{th}$ Mersenne Number. It is well known that if $M_s$ is a prime then $s$ must also be a prime. We claim that $k=2$ is the largest possible value of $k$ . To see this, take $x_1=a=3$ . Then $x_2=7$ and $x_3=15$ , which works as $y_1=M_3=7$ and $y_2=M_7=127$ are primes, while $y_3=M_{15}=32767=7 \times 4681$ is not. Now, we'll show that $k=3$ doesn't work. To see this, assume to the contrary that for some value of $a$ , $k=3$ works. Then $x_1=a,x_2=2a+1,x_3=4a+3$ must all be primes. We use the following well-known lemma to supplement our proof-

LEMMA If $p \equiv 3 \pmod{4}$ and $q=2p+1$ are both primes, then $q \mid M_p$ .

PROOF: By FLT, we get that $\begin{align*} 2^{q-1} \equiv 1 \pmod{q} \Rightarrow 2^{2p} \equiv 1 \pmod{q} &\Rightarrow 2^p \equiv +1 \pmod{q} \\ &\text{OR } 2^p \equiv -1 \pmod{q} \end{align*}$ Suppose the latter holds true. Then, using the fact that $p=\frac{q-1}{2}$ , and from Euler's Criterion, we get that $2$ is a quadratic non-residue modulo $q$ . But, as $q=2p+1 \equiv 7 \pmod{8}$ , using the Second Supplement to the Quadratic Reciprocity Theorem, we get that $2$ is in fact a quadratic residue modulo $q$ , which is a contradiction! Thus, the former result must be true, i.e. $2^p-1 \equiv 0 \pmod{q} \Rightarrow q \mid M_p$ $\Box$

Return to the problem at hand. It's easy to see that $a=2$ doesn't work (as $M_{4a+3}=M_{11}=2047=23 \times 89$ is not a prime). So from now on we assume that $a>2$ . As $a$ is a prime number, it must be of the form $2t+1$ . This gives $x_2=4t+3$ . By our Lemma, we get that $x_3=2x_2+1$ (which is a prime) divides $M_{x_2}$ , as $x_2 \equiv 3 \pmod{4}$ is a prime, which contradicts the fact that $y_2$ is a prime number. Hence, done. $\blacksquare$

This post has been edited 2 times. Last edited by math_pi_rate, Dec 14, 2018, 7:53 AM

Z K Y

The post below has been deleted. Click to close.

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

830 posts

niyu

#13 h Feb 18, 2019, 9:04 PM • 1 Y

Y by Adventure10

We claim the answer is $k = 2$ , which is achieved by $a = 3$ .

Lemma 1: If $2^m - 1$ is prime for some positive integer $m$ , $m$ must itself be prime.

Proof of Lemma 1: Suppose not, and write $m = ab$ for some $a, b > 1$ . But $2^a - 1 \mid 2^m - 1$ , contradicting the fact that $2^m - 1$ is prime. $\blacksquare$

Lemma 2: Suppose $p, 2p + 1$ are both odd primes. If $2^p - 1$ and $2^{2p + 1} - 1$ are both also prime, $p \equiv 1 \pmod{4}$ .

Proof of Lemma 2: Consider
$\begin{align*} 2^p \pmod{2p + 1}. \end{align*}$ This is the Jacobi symbol $\left(\frac 2{2p + 1}\right)$ . If $\left(\frac 2{2p + 1}\right) = 1$ , we have
$\begin{align*} 2p + 1 &\mid 2^p - 1, \end{align*}$ contradicting the fact that $2^p - 1$ is prime. Hence, we must have $\left(\frac 2{2p + 1}\right) = -1$ . This is equivalent to
$\begin{align*} (-1)^{\frac{(2p + 1)^2 - 1}{8}} &= -1 \\ \iff (-1)^{\frac{2p(2p + 2)}{8}} &= -1 \\ \iff (-1)^{\frac{p + 1}{2}} &= -1. \end{align*}$ Thus, we must have $p \equiv 1 \pmod{4}$ , proving the lemma. $\blacksquare$

We now return to the original problem. Suppose $y_1, y_2, y_3$ are all prime. By Lemma 1, $x_1, x_2, x_3$ are also all prime, so by definition $a, 2a + 1, 4a + 3$ are all prime. Now, by Lemma 2, $a \equiv 1 \pmod{4}$ , and also $2a + 1 \equiv 1 \pmod{4}$ , which is clearly impossible. Therefore, $k \leq 2$ , with equality demonstrated by $a = 3$ . This completes the proof. $\Box$

This post has been edited 3 times. Last edited by niyu, Mar 1, 2019, 4:05 AM

Z K Y

The post below has been deleted. Click to close.

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

mastermind.hk16

143 posts

mastermind.hk16

#14 h Feb 28, 2019, 11:04 PM • 2 Y

Y by Adventure10, Mango247

I claim $k=2$ . Construction: $x_1=2$ .
Lemma 1: If $2^t -1$ is prime, then $t$ must be prime.
Proof: Clearly, it $t=uv$ , then both $2^u -1$ and $2^v -1$ divide $t$ .

Lemma 2: For any prime $p \equiv 7 \mod 8$ , $\ \ 2^{\frac{p-1}{2}} \equiv 1 \mod p$
Proof: We have $\left( \frac{2}{p} \right) = (-1)^{\frac{p^2-1}{2}} = 1$ . Hence $1\equiv \left( \frac{2}{p} \right) \equiv 2^{\frac{p-1}{2}} \mod p$ .

Now back to the problem. By Lemma 1, $x_i$ 's must be prime for $y_i$ 's to be prime.
AFSOC, we have $y_1, y_2, y_3$ are all prime. Let $x_1 =a$ , where $a$ is an odd prime.
Then clearly $x_3 \equiv 7 \mod 8$ . Applying Lemma 2, $2^{x_2}-1 \equiv 0 \mod x_3$ .
But $a \geq 3 \longrightarrow 2^{2a +1}-1 > 4a+3$ because $2^{2a-1} > 2^a +1 > a+1$ . So $y_2 =2^{x_2}-1$ is composite. Contradiction.

Lastly, if $x_1=2$ then $x_2 =5, x_3 =11, x_4 =23$ . Again by Lemma 2, $23 \mid 2^{11}-1$ and $2^{11}-1>23$ , so it's composite. Therefore, $k=2$ .

This post has been edited 2 times. Last edited by mastermind.hk16, Feb 28, 2019, 11:23 PM

Z K Y

The post below has been deleted. Click to close.

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

206 posts

#15 h Apr 10, 2020, 1:42 AM • 2 Y

Y by Nathanisme, Mango247

The key observation is the following lemma:

Incredible

We can finish by considering the possible chain of $x_n$ modulo 8, and the answer is 2, which could be achieved by $a=3$ .

This post has been edited 2 times. Last edited by Idio-logy, Apr 10, 2020, 1:52 AM

Z K Y

The post below has been deleted. Click to close.

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

GeronimoStilton

1521 posts

GeronimoStilton

#16 h Jun 5, 2020, 9:22 PM

Y by

The maximum value of $k$ is $k=2$ . Construction is easy; take $a=2$ , for example.

The following proof of maximality is due to awang11.

Suppose that $k=3$ was attainable. Note that $a,2a+1,4a+3$ must all be primes. If $a=2$ , we get a contradiction because $2^{4a+3}-1=2^{11}-1=2047=23\cdot 89$ . Thus, we can assume $a\equiv 1\pmod{2}$ . Then, note that
$2^{(4a+3-1)/2} \equiv 1\pmod{4a+3}$ because $2$ is a quadratic residue modulo $4a+3\equiv -1\pmod{8}$ . This implies
$4a+3\mid 2^{2a+1}-1=y_2.$ It remains to deal with the case
$4a+3=2^{2a+1}-1.$ Then, we can rewrite as
$a+1=2^{2a-1}.$ Note that equality holds at $a=1$ , then note that increasing $a$ by $1$ increases the RHS by $1$ and the LHS by more than $1$ , so equality can never hold for prime $a$ .

Z K Y

The post below has been deleted. Click to close.

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

algebra_star1234

2467 posts

algebra_star1234

#17 h Jun 13, 2020, 11:39 PM

Y by

We claim that that the maximum is $k=2$ . We can achieve this with $a=2$ .

For the sake of contradiction, assume there is a sequence of length at least $3$ . First, note that $2^x - 1$ is prime only if $x$ is also prime. Therefore, we have $a$ , $2a+1$ , and $4a+3$ are prime. Note that when $a$ is even, $y_1$ is prime if and only if $a=2$ . We already know the $a=2$ case yields $k=2$ , so we can assume $a$ is odd or $a = 2k+1$ . Therefore, we have $2k+1$ , $4k+3$ , and $8k+7$ are prime. Note that for a prime of the form $8k+7$ , the number $2$ is a quadratic residue because
$\left(\frac{2}{p}\right) = (-1)^{\frac18 (p^2-1)} = 1 .$ Let $m^2 = 2 \pmod{8k+7}$ . We assumed $y_2$ is prime, but
$2^{4k+3} -1 \equiv m^{8k+6} - 1 \equiv 0 \pmod{8k+7}$ by FLT. Therefore, we must have $2^{4k+3}-1 = 8k+7$ , which does not provide any solutions. Therefore, we have a contradiction, and we are done.

Z K Y

The post below has been deleted. Click to close.

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

626 posts

#18 h Dec 30, 2020, 9:25 PM

Y by

The answer is $k=2$ ; this can be achieved, for instance, when $a=3$ . Now we show this is the best possible.

Assume otherwise that we could achieve three consecutive primes $y_1, y_2, y_3$ ; for obvious reasons, $x_1=a, x_2=2a+1, x_3=4a+3$ must also be prime. However, by quadratic reciprocity we have $\left( \frac{2}{4a+3} \right) = (-1)^{(4a+4)(4a+2)/8} = (-1)^{(a+1)(2a+1)} = 1$ and so by Fermat's little theorem we have $2^{2a+1} \equiv 1 \pmod{4a+3}$ . This contradicts the assumption that $y_2=2^{2a+1}-1$ is prime, because $2^{2a+1}-1>4a+3$ when $a \ge 2$ .

This post has been edited 1 time. Last edited by VulcanForge, Dec 30, 2020, 9:28 PM

Z K Y

The post below has been deleted. Click to close.

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

386 posts

#19 h Dec 31, 2020, 12:11 AM

Y by

Ultra nice problem and a great exercise for quadratic residues

$\color{black}\rule{25cm}{1pt}$
The maximal possible $k$ is $k=2$ .

Because of the primality condition on $y$ we must have that all of the $x$ 's must be prime as well.

Now we easily find a formula for $x$ , by subtracting the $(n+1)^{th}$ equation from the $(n+2)^{nd}$ equation we have that the characteristic polynomial is $t^2-3t+2=0$ , this implies that $x_n = A+B.2^n$ .
Plugging in the what we got for $x$ we get that $A=-1$ , and setting $n=1$ we have that $B=\frac{a+1}{2}$ , thus we have that $x_n=2^{n-1}(a+1)-1$ .
Thus we must have that the numbers $a,2a+1,4a+3,8a+7$ are all prime numbers.

But notice the following, we have that $2^{2a+1}=2^{\frac{4a+3-1}{2}}$ , since $4a+3$ is prime from Euler's criterion we must have that $2^{2a+1} \equiv \left(\frac{2}{4a+3}\right)\pmod{4a+3}$ .
We have that $\left(\frac{2}{4a+3}\right) \equiv (-1)^{\left\lfloor \frac{4a+3+1}{4} \right\rfloor} \equiv (-1)^{a+1} \pmod{4a+3}$ .
Now if $a > 2$ we have that $y_3$ isn't prime, so we have that $a=2$ .
But now we have that $y_3=2^{11}-1=23.89$ , thus we have that $k=2$ .

Z K Y

The post below has been deleted. Click to close.

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

2726 posts

#21 h Dec 31, 2020, 3:31 AM • 2 Y

Y by VulcanForge, itslumi

why are we all doing heavynt

Our answer is $k = 2$ , which can be achieved when $a = 2$ . Note that in general, $y_n$ prime implies that $x_n$ is prime; if $y_n$ is prime but $x_n$ is not, then $y_n = 2^{x_n} - 1$ is divisible by $2^m - 1$ for some $m \neq 1, x_n$ satisfying $m \mid x_n$ , which is impossible.

We will prove that the maximum $k$ for which $x_1, \ldots , x_k$ are all prime is $2$ , which finishes the problem. Suppose $(x_1, x_2, x_3) = (a, 2a+1, 4a+3)$ are all prime. We know $a = 2$ yields $k = 2$ so assume $a$ is an odd prime. Write $2^{2a+1} \equiv 2^{\tfrac12(4a + 3 - 1)} = \left(\tfrac{2}{4a+3}\right) = (-1)^{\tfrac{1}{8}((4a + 3)^2 - 1)} \pmod{4a + 3}$ Since $a$ is odd write $a = 2b+1$ , so $\tfrac18((4a + 3)^2 - 1) = \tfrac18((8b + 7)^2 - 1) = (8b+6)(b+1)$ hence it follows that $2^{2a+1} \equiv 1 \pmod{4a+3}$ . Clearly $4a + 3 < 2^{2a+1} - 1$ so $4a+3 \mid 2^{2a+1} - 1$ thus it follows that $2^{x_2} - 1$ has a prime factor, a contradiction.

Hence, we can have $k = 2$ at maximum, as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

1671 posts

pad

#22 h Feb 24, 2021, 8:40 AM

Y by

We claim $k=2$ is the maximum. Firstly, $k=2$ works since taking $a=2$ gives $2^2-1=3$ and $2^5-1=31$ , both primes. Now we show $k=3$ fails.

Let $S=\{a,2a+1,4a+3\}$ and suppose $2^s-1$ is prime for all $s\in S$ . If $s$ is composite, then so is $2^s-1$ due to the well-known fact that $x\mid y \iff 2^x-1\mid 2^y-1$ . Hence all elements of $S$ are prime.

Claim: We have $4a+3\mid 2^{2a+1}-1$ .

Proof: Since $a$ is prime, $a\equiv 1\pmod2$ , so $4a+3\equiv 7\pmod8$ . Also, $4a+3$ is prime, so $\left(\frac{2}{4a+3}\right)=1 \implies 2^{2a+1}\equiv 1 \pmod{4a+3},$ as claimed. $\blacksquare$

However, the claim is a contradiction since $2^{2a+1}-1$ is prime.

Remarks

Z K Y

The post below has been deleted. Click to close.

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

651 posts

#23 h Jun 24, 2021, 2:13 AM

Y by

dr_Civot wrote:

Solution.

dr_Civot wrote:

Solution.

Why a>2 then a is odd?

Z K Y

The post below has been deleted. Click to close.

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

277 posts

#24 h Aug 27, 2021, 11:33 AM

Y by

Cool problem.

We claim that the largest $k$ is $2$ which is possible if $x_1 = 2, x_2 = 5$ .
$\textbf{Claim:}$ $k < 2$
$\textbf{Proof)}$
Assume that $2^{x_1}-1, 2^{x_2}-1, 2^{x_3}-1$ are all primes from which we get that $x_1, x_2, x_3$ are all primes as well because if we let $x_i = a \cdot b$ for some $i \in \{1,2,3\}$ , then $2^{a}-1 \mid 2^{ab}-1$ We therefore have that $p = x_1, 2p+1, 4p+3$ are all primes such that $2^p-1, 2^{2p+1}-1, 2^{4p+3}-1$ are all primes, as well with $p \neq 2$ as $2^11-1$ is not prime.
Notice that $2^p-1 \equiv 2^{\frac{(2p+1)-1}{2}} - 1 \equiv 0 \pmod{2p+1}$ if $2$ is a quadratic residue $\pmod{2p+1}$ which is not possible, consequently, $2$ has to be a quadratic non-residue $\pmod{2p+1}$ and $\pmod{4p+3}$ .
Then $2p+1 \equiv 3,5 \pmod{8}$ , yet if $2p+1 \equiv 5 \pmod{8}$ , then $p$ has to be even meaning that $2p+1 \equiv 3 \pmod{8}$ .
Then $4p+3 \equiv 2(2p+1)+1 \equiv 2\cdot 3 +1 \equiv 7 \pmod{8}$ meaning that $2$ is a quadratic residue $\pmod{4p+3}$ which is a contradiction. $\blacksquare$

This post has been edited 1 time. Last edited by bora_olmez, Aug 27, 2021, 11:33 AM

Z K Y

The post below has been deleted. Click to close.

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

1492 posts

#25 h Oct 2, 2021, 3:03 AM

Y by

The answer is $k = 2.$

Remark that since $2^{m}-1 \mid 2^{n}-1$ when $m \mid n,$ it follows that all of $\{x_1, \dots, x_k \}$ must be prime. Now, assume we had three primes $a, 2a+1, 4a+3$ such that $2^{a}-1, 2^{2a+1}-1$ , and $2^{4a+3}-1$ are all prime.

Claim: $4a+3 \mid 2^{2a+1}-1.$

We have $\left( \frac{2}{4a+3} \right) = (-1)^{1/8 ((4a+3)^2-1)} = (-1)^{(2a+1)(a+1)} = 1$ if $a$ is an odd prime. If $a = 2,$ then $y_1 = 2^2-1 = 3, y_2 = 2^5-1 = 31$ and $y_3 = 2^11-1 = 2047,$ which is not prime. Hence, as we also have $\left( \frac{2}{4a+3} \right) = 2^{2a+1} \equiv 1 \pmod{4a+3}$ under the assumption that $4a+3$ is prime, we thus have $4a+3 \mid 2^{2a+1}-1.$

Hence, it is impossible to have three primes $a, 2a+1,$ and $4a+3$ such that all of $2^{a}-1, 2^{2a+1}-1,$ and $2^{4a+3}-1$ are prime, meaning we can have at most $k=2,$ which holds by taking $a=2.$

Z K Y

The post below has been deleted. Click to close.

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

8866 posts

#26 h Apr 23, 2023, 2:54 AM

Y by

The answer is $k=2$ . For construction, take $a=2$ .

Now suppose $k \geq 3$ . I will show one of the first three terms is composite. Assume for the sake of contradiction that $a, 2a+1, 4a+3$ are all primes.

Assume that $a$ is odd; $a=2$ can be quickly checked. Now note that $4a+3 \equiv -1 \pmod 8$ , thus $\left(\frac 2{4a+3}\right) = 1$ and thus $4a+3 \mid 2^{x_2} - 1 = 4a+3$ as by assumption $2^{x_2} - 1$ is prime. But this obviously impossible for size reasons.

This post has been edited 1 time. Last edited by HamstPan38825, Apr 23, 2023, 2:54 AM

Z K Y

The post below has been deleted. Click to close.

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

210 posts

egxa

#27 h Aug 7, 2023, 10:42 AM

Y by

Easy to see if $a=1,2$ $k=2$ .
Let $a\ge3$
Obvious that all of $x_i$ are prime.
Let $x_1=p$ . From quadratic residue we get $(\frac{-2}{4p+3})=1=(\frac{-1}{4p+3}).(\frac{2}{4p+3})$ so
$(\frac{2}{4p+3})=-1$ and $p$ must be even. Contradiction. $\blacksquare$

This post has been edited 1 time. Last edited by egxa, Aug 7, 2023, 2:49 PM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

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

419 posts

#28 h Apr 7, 2024, 7:07 AM

Y by

We know that if $2^t-1$ is a prime, then $t$ itself must be a prime, because if $t'\mid t$ then $2^{t'}-1\mid 2^t-1$ . Hence, $x_1, x_2, \ldots, x_k$ must be prime. Note that if $2^{\text{odd}}-1$ is a prime $p$ , then $2$ is Quadratic Residue $\pmod{p}$ and hence $p\equiv \pm1\pmod{8}$ . Note that $x_3=4x_1+3$ and $x_3\equiv 7\pmod{8}$ . Note that $2^{\frac{x_3-1}2}\equiv1\pmod{x_3}$ as $x_3\equiv-1\pmod{8}$ . This means that $x_3\mid y_2$ and hence $x_3=y_2$ which is possible only if $x_3=7$ but then $7\mid y_4=2^{15}-1$ . So, largest possible $k$ is $2$ because $2^1-1,2^3-1,2^7-1$ are not all prime because first term is 1. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

796 posts

#29 h Apr 20, 2024, 7:43 PM

Y by

Notice we must have $x_1, x_2, \ldots$ prime. Our main claim states that if $x_i \equiv 3 \pmod 4$ and $x_{i+1} = 2x_i+1 \equiv 3 \pmod 4$ are prime, we have $x_{i+1} \mid 2^{x_i}-1 = y_i$ . This holds, as
$2^{x_i} \equiv 2^{\frac{x_{i+1}-1}{2}} \equiv \left(\frac{2}{x_{i+1}}\right) \equiv 1 \pmod{x_{i+1}}.$
Thus we can consider cases using this claim, and denote $K$ as the maximum possible value of $k$ in that case.

$a=2$ : $K=2$ .
$a \equiv 3 \pmod 4$ : Then $x_1 \equiv x_2 \equiv 3 \pmod 4$ . If $x_2$ is prime, then $x_1$ is composite, so $K=0$ . If $x_2$ is composite, then $K=1$ .
$a \equiv 1 \pmod 4$ : Then $x_2 \equiv x_3 \equiv 3 \pmod 4$ , so we can find $K \leq 2$ in a similar fashion.

Thus our answer is $k = \boxed{2}$ , which can be achieved using $a=2$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

150 posts

Markas

#30 h Jul 13, 2024, 3:03 PM

Y by

Let a = 2, $x_1 = 2$ , $y_1 = 3$ , $y_2 = 31$ , $y_3 = 2047 = 23.89$ $\Rightarrow$ this is an example for k = 2. We will prove that $k < 3$ . For this, assume that $y_1$ , $y_2$ and $y_3$ are prime. If $b \mid a$ then $2^b - 1 \mid 2^a - 1$ - impossible $\Rightarrow$ a is prime $\Rightarrow$ all $x_i$ are prime. Now let $x_1$ be an odd prime since we checked the case for a = 2. Since $x_1$ is odd we get that $x_3 \equiv 7 \pmod 8$ . We will show that for any prime $p \equiv 7 \pmod 8$ , $2^{\frac{p-1}{2}} \equiv 1 \pmod p$ . Thats true because $\left( \frac{2}{p} \right) = (-1)^{\frac{p^2-1}{2}} = 1$ and $1 \equiv \left( \frac{2}{p} \right) \equiv 2^{\frac{p-1}{2}} \pmod p$ . Using this we get $2^{x_2}-1 \equiv 0 \pmod {x_3}$ $\Rightarrow$ $x_3 \mid y_2$ $\Rightarrow$ $x_3 = y_2$ , but for $a \geq 3$ we have that $2^{2a +1}-1 > 4a+3$ since $2^{2a-1} > 2^a +1 > a+1$ . So $y_2 = 2^{x_2}-1$ is composite, which is impossible and we get our contradiction $\Rightarrow$ k = 2.

Z K Y

The post below has been deleted. Click to close.

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

1745 posts

OronSH

#31 h Sep 30, 2024, 3:45 AM • 2 Y

Y by megarnie, Funcshun840

The answer is $k=2$ .

Check $a=1,2$ . Next suppose $k=3$ is possible. We may assume $a=p$ is an odd prime and so are $2p+1,4p+3$ . If $p\equiv 1\pmod 2$ then $4p+3\equiv 7\pmod 8$ so $2$ is a quadratic residue $\pmod{4p+3}$ . Now consider the order of $2 \pmod{4p+3}$ . It divides $4p+2$ but must be odd, so it is $2p+1$ and $4p+3\mid 2^{2p+1}-1$ so it is not prime, contradiction.

This post has been edited 1 time. Last edited by OronSH, Oct 1, 2024, 1:33 PM

Z K Y

The post below has been deleted. Click to close.

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

268 posts

L13832

#32 h Jan 20, 2025, 7:36 AM • 2 Y

Y by alexanderhamilton124, Nobitasolvesproblems1979

solution

Z K Y

The post below has been deleted. Click to close.

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

cursed_tangent1434

634 posts

cursed_tangent1434

#33 h Apr 30, 2025, 10:16 AM

Y by

We claim that the answer is $k=2$ which is easily achieved when $a=2$ since $2^2-1=3$ and $2^5-1=31$ are both prime. We now show that it is impossible to have $k>2$ . If there exists some positive integer $a$ for which $k>2$ note that $a>2$ as well, since $a=1$ and $a=2$ yield $k=0$ (since apparently one is not a prime) and $k=2$ respectively.

By assumption $y_1,y_2$ and $y_3$ are all prime and hence $x_1,x_2$ and $x_3$ are also all prime since if $t <x_i \mid x_i$ then,
$2^t-1 \mid 2^{x_i}-1=y_i$ making it non-prime. However we may write $x_i = 2^{i-1}a+(2^{i-1}-1)$ for all positive integers $i$ . Since $a>2$ and prime, $a$ must be odd. Hence,
$x_3=2^{2}a+(2^2-1) = 4a+3 =4(2a'+1)+3 = 8a'+7 \equiv -1 \pmod{8}$ But now, if $x_3 \equiv -1 \pmod{8}$ is a prime, the Law of Quadratic Reciprocity states that $2$ is a quadratic residue $\pmod{x_3}$ . Thus,
$y_2 = 2^{x_2}-1 \equiv (r^2)^{x_2}-1 = r^{2x_2}-1 \equiv 0 \pmod{2x_2+1}$ since $2x_2+1=x_3$ is prime. But this means $2x_2+1 \mid 2^{x_2}-1$ . Also, for all $x_2 \ge 4$ ,
$2x_2+1 < 2^{x_2}-1$ which implies that we must have $x_2 <4$ . However since $x_2=4a+3 \ge 4(1)+3=7 >3$ this is a clear contradiction so it is indeed impossible for $y_1,y_2$ and $y_3$ to all be prime for any choice of $a$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a