Find all pairs of prime numbers $(p,q)$ for which \[2^p = 2^{q-2} + q!.\]
Problem
Source: 2022 Turkey TST P1 Day 1 + 2023 Dutch BxMO TST, Problem 5
Tags: number theory, modular arithmetic, number theory proposed, Diophantine equation
electrovector
13.03.2022 14:17
mod 7 and $v_2$
It is easy to see that $(p, q)=(3, 3)$ and $(p, q)=(7, 5)$ are solutions. Now assume that $q \ge 7$ and $p\ge 13$. $\text{mod 7}$ gives us $p \equiv q-2 \pmod{3}$. Since both $p$ and $q$ are different from $3$ we have $p \equiv 2 \pmod{3}$ and $q \equiv 1 \pmod{3}$. If we compare $v_2$s of both sides we have $q-2=v_2(q!)=q-s_2(q) \Rightarrow s_2(q)=2$ which means $q$ is in the form of $2^k+1$. If we use $q \equiv 1 \pmod{3}$, then we have $3|2^k$ a clear contradiction.
P2nisic
13.03.2022 17:03
For $q=2$ no sullotion For $q=3$ we have $p=5$ For $q=5$ we have $p=7$ Let now $q>=7$ then: we have that $U_2(q!)=q-2$ where $q=odd$ we can prove using intruction that $q=2^a+1$ also $q>3$which means that $a=even$ so $q=2^{2b}+1$ This means that $3|q-2$ and taking $mod7$ gives $p=3$ contradictions
hef4875
04.01.2023 04:01
electrovector wrote:
mod 7 and $v_2$
It is easy to see that $(p, q)=(3, 3)$ and $(p, q)=(7, 5)$ are solutions. Now assume that $q \ge 7$ and $p\ge 13$. $\text{mod 7}$ gives us $p \equiv q-2 \pmod{3}$. Since both $p$ and $q$ are different from $3$ we have $p \equiv 2 \pmod{3}$ and $q \equiv 1 \pmod{3}$. If we compare $v_2$s of both sides we have $q-2=v_2(q!)=q-s_2(q) \Rightarrow s_2(q)=2$ which means $q$ is in the form of $2^k+1$. If we use $q \equiv 1 \pmod{3}$, then we have $3|2^k$ a clear contradiction.
What does $s_2(q)=2$ stand for? I do not see this symbol before.
dragon-YBW
04.01.2023 04:21
hef4875 wrote: electrovector wrote:
mod 7 and $v_2$
It is easy to see that $(p, q)=(3, 3)$ and $(p, q)=(7, 5)$ are solutions. Now assume that $q \ge 7$ and $p\ge 13$. $\text{mod 7}$ gives us $p \equiv q-2 \pmod{3}$. Since both $p$ and $q$ are different from $3$ we have $p \equiv 2 \pmod{3}$ and $q \equiv 1 \pmod{3}$. If we compare $v_2$s of both sides we have $q-2=v_2(q!)=q-s_2(q) \Rightarrow s_2(q)=2$ which means $q$ is in the form of $2^k+1$. If we use $q \equiv 1 \pmod{3}$, then we have $3|2^k$ a clear contradiction.
What does $s_2(q)=2$ stand for? I do not see this symbol before. It's the binary digit sum of q
F10tothepowerof34
17.09.2023 22:51
Clearly the case when $p<q$ yields a contradiction If $p=q$ The equation is transformed into $2^p=2^{p-2}+p!\Longleftrightarrow2^p-2^{p-2}=p!\Longrightarrow3\cdot2^{p-2}=p!$ However notice that $3\cdot2^{p-2}\equiv3,5\text{ or }6\pmod 7$ while $p!\equiv1\pmod 7$ for $p=5$ and $p!\equiv0\pmod 7$ for $p>5$. Thus $p<5$. $p=2$ yields $3\cdot2^0=2\Longrightarrow3=2$ which is clearly a contradiction. $p=3$ yields $3\cdot2=6$ which is true. Therefore $(p,q)=(3,3)$ is a solution. So from now on assume that $p>q$ Now notice that taking $\nu_2$ yields $\nu_2(2^p-2^{q-2})=\nu_2(q!)$ Furthermore $\nu_2(q!)=q-S_2(q)$ by $\text{Legendre's}$ and $\nu_2(2^p-2^{q-2})=\nu_2(2^{q-2}(2^{p-q+2}-1))=\nu_2(2^{q-2})+\nu_2(2^{p-q+2}-1)=q-2$ Thus $q-S_2(q)=q-2\Longrightarrow S_2(q)=2$ which forces $q$ to be of the form $2^t+1$. Therefore $q=2^t+1$ Moreover $\text{FTSOC}$ assume that $t\ge3$ which indirectly implies $p\ge11\text{ and }q\ge7$ Now for $q\ge7$ we have that $q!\equiv0\pmod 7$ which forces $2^p-2^{q-2}\equiv0\pmod 7$ However notice that $2^p\equiv2\text{ or }4\pmod 7$ and $2^{q-2}\equiv1,2\text{ or }4\pmod 7$ thus $2^{q-2}\equiv1\text{ or }4\pmod 7$ Which is only the case when $q$ is of the form $3k+1$ or equivalently $q\equiv 1\pmod 3$ Now recall that $q=2^t+1$ thus $2^t+1\equiv1\pmod 3\Longrightarrow 2^t\equiv0\pmod 3$ which is a contradiction.Thus $t\le2$, checking both of these cases yields $(p,q)=(7,5)$ In conclusion $\boxed{(p,q)=(3,3)\text{ and }(7,5)\text{ are the only solutions for }p,q\in\mathbb{P}}$ $\blacksquare$.