Twin Prime Diophantine

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

Twin Prime Diophantine

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: CMO 2025

The post below has been deleted. Click to close.

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

awesomeming327.

1665 posts

awesomeming327.

#1 h Mar 7, 2025, 8:28 PM

Y by

Determine all positive integers $a$ , $b$ , $c$ , $p$ , where $p$ and $p+2$ are odd primes and
$2^ap^b=(p+2)^c-1.$

Z K Y

The post below has been deleted. Click to close.

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

504 posts

#2 h Mar 7, 2025, 8:33 PM • 1 Y

Y by TrendCrusher

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.

awesomeming327.

1665 posts

awesomeming327.

#3 h Mar 7, 2025, 8:48 PM

Y by

Solution Sketch:

mod $p+1$ gives $p+1$ is a power of $2$ , but $p+1$ is also divisible by $6$ if it's too large due to twin primes, so we just get $p+1=4$ as an option, we have $p=3$ .

Obviously at this point, Zsigmondy just finishes. If you don't like zsigmondy there are other ways as well.

Z K Y

The post below has been deleted. Click to close.

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

alexanderhamilton124

378 posts

alexanderhamilton124

#4 h Mar 7, 2025, 8:49 PM • 1 Y

Y by COCBSGGCTG3

Observe that $p + 1 \mid (p + 2)^c - 1 \implies p + 1 \mid 2^a p^b \implies p + 1 \mid 2^a$ , since $\gcd(p + 1, p) = 1$ . So, $p + 1$ is a power of $2$ . Let $p + 1 = 2^x$ . Note that both $p, p + 2$ are prime, but one of $2^x - 1$ , $2^x + 1$ must be divisible by $3$ , so one of them must be $3$ . Of course, $p \neq 1$ , so $p = 3$ .

We have $2^a 3^b = 5^c - 1$ . Note that $v_2(5^c - 1) = 2 + v_2(c)$ , so $2 + v_2(c) = a \implies a - 2 = v_2(c) \implies 2^{a - 2} \mid c$ . $3 \mid 5^c - 1$ means that $c$ is even, let $c = 2k$ . We have $v_3(5^{2k} - 1) = v_3(5^2 - 1) + v_3(k) = 1 + v_3(c) = b \implies b - 1 = v_3(c) \implies 3^{b - 1} \mid c$ .

So, $2^{a - 2}3^{b - 1} \mid c \implies 2^{a - 2}3^{b - 1} \leq c$ . Note $5^{2^{a - 2}} > 2^a$ for $a \geq 2$ , $5^{3^{b - 1}} > 3^b + 1$ for $b \geq 1$ , by simply inducting. So, we have an obvious contradiction by size and we are reduced to a minimal case check which is left as an excercise to the reader.

Z K Y

The post below has been deleted. Click to close.

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

3439 posts

#5 h Mar 7, 2025, 9:13 PM

Y by

Carried by GrantStar.

The equation modulo $p+1$ gives
$2^a (-1)^b \equiv 0 \pmod{p+1},$ implying $p+1$ is a power of $2$ . At least one of $p$ , $p+1$ and $p+2$ must be a multiple of $3$ , so it must be one of $p$ or $p+2$ . It thus follows that $p=3$ . Now Zsigmondy finishes as it implies $c\leq 2$ . This gives us our only solution of $(a,b,c,p) = (3,1,2,3)$ .

Z K Y

The post below has been deleted. Click to close.

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

676 posts

#6 h Mar 7, 2025, 9:21 PM

Y by

2022 China TST, Test 4 P4 with $(p+2)^c-1$ instead of $(p+2)^c+1$ .

Z K Y

The post below has been deleted. Click to close.

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

302 posts

#7 h Mar 7, 2025, 9:27 PM

Y by

Observe that the left hand side is divisible by $p + 1,$ and so $p = 2^k - 1$ for some $k\in\mathbb Z.$ Clearly, we have that $k$ is a prime. Hence, if $k>2,$ then $3\not\mid 2^k + 1 = p + 2.$ However, we already know that 3 divides one of $p, p +1,p + 2.$ It also can't divide $p + 1$ as this would imply $p = 3.$ Hence, $3\mid p \implies p = 3.$ The rest is trivial by Zsigmondy

This post has been edited 1 time. Last edited by Ilikeminecraft, Mar 7, 2025, 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.

1400 posts

#8 h Mar 7, 2025, 9:34 PM

Y by

No need for fancy Zsigmondy whatsoever.

Using modulo $p+1$ , we find $p+1\mid 2^a (-1)^b$ , i.e., $p+1=2^u$ for a suitable $u$ . Suppose $u\ne 2$ . As $2^u-1$ is a prime, we must have $u$ is a prime. At the same time, $p+2=2^u+1$ is also a prime, which is possible only when $u=2$ . Thus, $p=3$ and $2^a3^b=5^c-1$ . Using modulo 3, we find that $c$ is even, set $c=2k$ and factorize
$2^a 3^b = (5^k-1)(5^k+1).$ Clearly $v_2(5^k+1)=1$ . So, $2^{a-1}\mid 5^k-1$ . Since $5^k\pm 1$ cannot be simultaneously divisible by 3, we must have $5^k+1=2\cdot 3^b$ and $5^k-1=2^{a-1}$ . The cases $a\le 3$ are easy, $(a,b,c)=(3,1,2)$ is the only solution. Let $a\ge 4$ . Then, using modulo 8, we find $k$ is even. Moreover, using modulo 5, we find $a-1\equiv 2\pmod{4}$ . So, $5^k-2^{a-1}=1$ where $k,a-1$ are both even, which doesn't have any solutions.

Z K Y

The post below has been deleted. Click to close.

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

5538 posts

#9 h Mar 7, 2025, 9:59 PM • 1 Y

Y by imagien_bad

Since $p + 1$ divides the RHS, it's clear that $p + 1$ is a power of $2$ . Note that this means $3\nmid p + 1$ , so $3$ divides one of $p, p + 2$ , from which we obviously have $p = 3$ . By Zsigmondy (or just noting that $c$ is even and factoring) we can find that $c = 2$ , so $(a,b,c,p) = (3,1,2,3)$ must hold, and it clearly works.

edit (even easier way to show $p = 3$ ): If $p \ne 3$ , then neither of $p, p + 2$ are $0\pmod 3$ , so $p \equiv 2 \pmod 3$ and $p + 2 \equiv 1 \pmod 3$ , so $3$ divides the RHS, which is absurd as $p \ne 3$ .

This post has been edited 2 times. Last edited by megarnie, Mar 7, 2025, 10:11 PM

Z K Y

The post below has been deleted. Click to close.

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

1457 posts

#10 h Mar 8, 2025, 4:41 PM

Y by

Okay so $\pmod{p+1}$ inmediately gives that $p+1$ is a power of $2$ but also if $p \ge 5$ then $p \equiv -1 \pmod 6$ and thus $3 \mid p+1$ which can't happen so $p=3$ , now by Zsigmondy we have for $c \ge 3$ a contradiction so if $c=1$ then $b=0$ by checking $\nu_3$ so contradiction and if $c=2$ then $b=1$ and $a=3$ thus we are done :cool:

:cool:

.

Z K Y

The post below has been deleted. Click to close.

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

1834 posts

PEKKA

#11 h Mar 8, 2025, 6:58 PM

Y by

Sketch of my in-contest solution:
1. Take mod $p+1$ to get $p+1 \mid 2^k$ for some $k.$
2. Take mod $p$ and by orders we get $c \mid p-1$ which means $\nu_2(c) \le 1$
3. Then by LTE we get $\nu_2(p+1)=a$ or $a-1.$
4. Realize that since $p+1$ is a power of $2,$ then one of $p, p+2$ is a multiple of $3$ which obviously implies $p=3.$
5. If $b \ge 2$ then by mod $9$ we have $6 \mid c$ which gives $2^a3^b \equiv 0 \pmod{7}$ by orders.

I kinda forgot what I did afterwards. If I can get my submission/scratch work from my proctor I will complete the solution.

This post has been edited 4 times. Last edited by PEKKA, Mar 8, 2025, 7:25 PM

Z K Y

The post below has been deleted. Click to close.

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

1198 posts

#12 h Mar 8, 2025, 10:12 PM

Y by

a_507_bc wrote:

2022 China TST, Test 4 P4 with $(p+2)^c-1$ instead of $(p+2)^c+1$ .

The same factoring + mod ideas also appear in Bulgaria JBMO TST 2023 and JBMO 2022/3.

This post has been edited 1 time. Last edited by Assassino9931, Mar 8, 2025, 10:13 PM

Z K Y

The post below has been deleted. Click to close.

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

406 posts

#13 h Mar 9, 2025, 5:34 PM

Y by

awesomeming327. wrote:

Determine all positive integers $a$ , $b$ , $c$ , $p$ , where $p$ and $p+2$ are odd primes and
$2^ap^b=(p+2)^c-1.$

I think that the idea of contraction this problem comes from 2022 China TST, Test 4 P4:
https://artofproblemsolving.com/community/c6h2835394p25099645

JustPostChinaTST wrote:

Find all positive integers $a,b,c$ and prime $p$ satisfying that
$2^a p^b=(p+2)^c+1.$

Z K Y

The post below has been deleted. Click to close.

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

15 posts

Mapism

#14 h Mar 10, 2025, 6:07 PM

Y by

$2^ap^b=(p+2)^c-1 \implies 2^a(-1)^b\equiv 0 \pmod {p+1} \implies p+1\mid 2^a \implies p+1=2^x,\ x\in \mathbb{Z^+}$ Since one of $p,p+1,p+2$ is divisible by $3$ and $3\nmid p+1=2^x;\ p=3,\ p+2=5$ .
$2^a3^b=5^c-1\implies 5^c\equiv1 \pmod {3}\implies 2\mid c$ So,
$a=\nu_2(5^c-1)=\nu_2(4)+ \nu_2(6)+\nu_2(c)-1=2+ \nu_2(c)$ $b=\nu_3(25^{\frac{c}{2}}-1)=\nu_3(24)+ \nu_3(\frac{c}{2})$ Thus,
$2^{2+\nu_2(c)}3^{1+\nu_3(\frac{c}{2})}=5^c-1\implies 2^{2+log_2(c)}3^{1+log_3(\frac{c}{2})}\ge 5^c-1 \implies 6c^2\ge 5^c-1\implies c\le 2 \implies c=2$ It follows that the only solution is $(a,b,c,p)=(3,1,2,3)$ .

This post has been edited 1 time. Last edited by Mapism, Mar 10, 2025, 6:09 PM

Z K Y

The post below has been deleted. Click to close.

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

1198 posts

#15 h Mar 17, 2025, 3:28 AM

Y by

If I am not mistaken, heavy theorems can be very easily avoided?

UPDATE: Actually, mod $p+1$ is also not needed!

By mod $3$ we cannot have $p\not\equiv 1 \pmod 3$ since $p+2$ must be prime. Also, if $p\equiv 2 \pmod 3$ , then the left-hand side is not divisible by $3$ , but the right-hand side is, contradiction. Hence $p=3$ .

The equation now reads $2^a3^b = 5^c - 1$ . By mod $3$ we get that $c$ is even. With $c=2k$ we factor $2^a3^b = (5^k - 1)(5^k + 1)$ and the greatest common divisor of the factors on the right is $2$ . Since $5^k \equiv 1 \pmod 4$ and $5^k + 1 > 2$ , we get $5^k - 1 = 2^{a-1}$ and $5^k + 1 = 2 \cdot 3^b$ . Work only with the former -- if $a=3$ , then $k=1$ and no solution for $a=1,2$ . If $a\geq 4$ , then by mod $8$ we get $k$ is even, so $k = 2t$ , factor $(5^t-1)(5^t+1) = 2^{a-1}$ and $5^t + 1 = 2$ by mod $4$ , contradiction. Therefore, the only solution is $(a,b,c,p) = (3,1,2,3)$ .

This post has been edited 1 time. Last edited by Assassino9931, Mar 18, 2025, 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.

NewtonVieta1729

9 posts

NewtonVieta1729

#16 h Mar 17, 2025, 11:03 AM

Y by

a_507_bc wrote:

2022 China TST, Test 4 P4 with $(p+2)^c-1$ instead of $(p+2)^c+1$ .

YESSSS. The problem looked so familiar to state the least.

Z K Y

The post below has been deleted. Click to close.

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

981 posts

#17 h Mar 17, 2025, 4:39 PM

Y by

awesomeming327. wrote:

Determine all positive integers $a$ , $b$ , $c$ , $p$ , where $p$ and $p+2$ are odd primes and
$2^ap^b=(p+2)^c-1.$

sketch:
p+1 | (p+2)^c - 1 => p = 2^q - 1 for some prime q
p | (p+2)^c - 1 \equiv 2^c - 1 => q | c, c = qd for some positive integer d
do some bashing to show v_p((p+2)^q - 1) = 1
note that for any d and prime r != 2 or p, v_r((p+2)^(qd) - 1) >= v_r((p+2)^d - 1) = 0; therefore, if there exists a solution for a certain value of p, there must also exist a solution for the same value of p when d = 1. this implies b = 1 because v_p((p+2)^q - 1) = 1
v_2(2^a * (2^q - 1)) = v_2((2^q + 1)^q - 1) => a = q + v_2(q)
if q > 2, a = q and 2^q * (2^q - 1) < (2^q + 1)^q - 1, contradiction; therefore, q = 2, so p = 2^2 - 1 = 3. when d = 1, this gives the solution set (3, 1, 2, 3)

if d > 1 is even, 13 | 624 | 25^d - 1 = (p+2)^c - 1, contradiction
otherwise, if d > 1, note that v2((25^d - 1) / (25 - 1)) = 1 0 and v3((25^d - 1) / (25 - 1)) = v3(d) by lte. therefore, there must be another prime r >= 5 that divides 25^d - 1, reaching a contradiction as well
therefore, d = 1, and the solution mentioned above is unique

This post has been edited 1 time. Last edited by scannose, Mar 17, 2025, 4:42 PM

Z K Y

The post below has been deleted. Click to close.

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

snorlax_snorlax

2 posts

snorlax_snorlax

#18 h Mar 19, 2025, 6:15 AM

Y by

This was a frustrating trolling problem. As soon as you realize that if $p+2$ is prime, it simply means that for sufficiently large $p,p+2$ isn’t divisible by three, and that’s all you need. I wasted an hour just to spot this not-suitable-for-IMO property. Once you notice it, it’s basically an obvious application of Zsigmondy’s theorem.

This post has been edited 1 time. Last edited by snorlax_snorlax, Mar 19, 2025, 6:24 AM
Reason: not suitable

Z K Y

The post below has been deleted. Click to close.

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

828 posts

#19 h Mar 19, 2025, 7:05 AM

Y by

Seriously? https://artofproblemsolving.com/community/c6h2835394p25099645

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a