Classical NT using modular arithmetic

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

Classical NT using modular arithmetic

G H J

Reveal topic tags

modular arithmetic

number theory proposed

Diophantine equation

L

G H BBookmark kLocked kLocked NReply

Source: 2022 Turkey TST P1 Day 1 + 2023 Dutch BxMO TST, Problem 5

The post below has been deleted. Click to close.

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

479 posts

#1 h Mar 13, 2022, 11:17 AM • 4 Y

Y by oralayhan, sohere, rightways, tiendung2006

Find all pairs of prime numbers $(p,q)$ for which
$2^p = 2^{q-2} + q!.$

This post has been edited 1 time. Last edited by Amir Hossein, Mar 12, 2024, 8:51 PM
Reason: Fixed the wording and added an extra source

Z K Y

The post below has been deleted. Click to close.

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

479 posts

#2 h Mar 13, 2022, 11:17 AM • 2 Y

Y by hef4875, Stuffybear

Hint
Solution

Z K Y

The post below has been deleted. Click to close.

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

406 posts

#3 h Mar 13, 2022, 2:03 PM • 1 Y

Y by anh1110004

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

Z K Y

The post below has been deleted. Click to close.

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

131 posts

#4 h Jan 4, 2023, 1:01 AM

Y by

electrovector wrote:

Hint
Solution

What does $s_2(q)=2$ stand for? I do not see this symbol before.

Z K Y

The post below has been deleted. Click to close.

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

40 posts

#5 h Jan 4, 2023, 1:21 AM

Y by

hef4875 wrote:

electrovector wrote:

Hint
Solution

What does $s_2(q)=2$ stand for? I do not see this symbol before.

It's the binary digit sum of q

Z K Y

The post below has been deleted. Click to close.

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

F10tothepowerof34

195 posts

F10tothepowerof34

#6 h Sep 17, 2023, 7:51 PM • 1 Y

Y by anirbanbz

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

Z K Y

The post below has been deleted. Click to close.

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

31 posts

#7 h Mar 24, 2025, 5:39 PM • 1 Y

Y by Funcshun840

It is possible to solve the more general equation of $2^a-2^b=n!$ . We have that $b=v_2(n!)<n$ , and by zsigmondy, if $a-b\geq n>6$ then $2^{a-b}-1$ is divisible by a prime s.t. the order of $2$ mod it is exactly $a-b$ so the prime is at least $a-b+1>n$ . For $n>6$ we have that $a\leq2n-2$ meaning $2^{2n-2}>n!$ , but that is not true starting with $n=7$ , so $n\leq 6$ .
Now to solve remaining cases:
$n=1: 2^1-2^0=1!$
$n=2: 2^2-2^1=2!$
$n=3: 2^3-2^1=3!$
$n=4: 2^5-2^3=4!$
$n=5: 2^7-2^3=5!$
$n=6:$ sadly no solution.
For the problem, only the cases of $n=3, 5$ apply.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a