Problem 2

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

Problem 2

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Polish Math Olympiad 2025 Finals P2

The post below has been deleted. Click to close.

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

70 posts

blug

#1 h Apr 4, 2025, 11:49 AM

Y by

Positive integers $k, m, n ,p$ integers are such that $p=2^{2^n}+1$ is prime and $p\mid 2^k-m$ . Prove that there exists a positive integer $l$ such that $p^2\mid 2^l-m$ .

Z K Y

The post below has been deleted. Click to close.

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

75 posts

#2 h Apr 4, 2025, 12:19 PM

Y by

Let $ord_{p^2}^2 = d$ . Obviously $ord_p^2 = 2^{n+1}$ . Now by LTE we have, $p^2|2^d-1\Rightarrow 2^{n+1}|d \Rightarrow v_p(2^d-1) = v_p(2^{2^{n+1}}-1)+v_p(\frac{d}{2^{n+1}}) \ge 2 \Rightarrow 2^{n+1}p|d$ and by minimality we get $d = 2^{n+1}p$ .
Let $a_j = k+2^{n+1}j$ for $0\le j \le p-1$ . we have $\forall j: p|2^{a_j}-m$ . Suppose $p^2 \not | 2^{a_i}-m$ for all $i$ . Since there are $p$ indices, we have that there exists two indices like $s,t$ such that $2^{a_s}-m \equiv 2^{a_t}-m \mod p^2 \Rightarrow p^2 | 2^{a_s-a_t}-1 \Rightarrow d=2^{n+1}p | a_s-a_t$ but $|a_s-a_t| \le 2^{n+1}(p-1)+k - k = 2^{n+1}(p-1) < 2^{n+1}p$ which is a contradiction.

Z K Y

The post below has been deleted. Click to close.

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

179 posts

#3 h Apr 5, 2025, 8:20 AM

Y by

Note that $p-1$ is a power of two.
We will consider numbers of the form $2^k (p-1)^{2r} -m$ , here $l=k+2^{n+1}r$ . Using Newtons binomial expansion we get $2^l-m \equiv 2^k (-2pr+1) -m \equiv 2^k-m - 2^{k+1}pr \pmod {p^2}$ Clearly since $p \neq 2$ we can choose $r$ such that the thing above is divisible by $p^2$ .

Z K Y

The post below has been deleted. Click to close.

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

9031 posts

#4 h Apr 7, 2025, 10:12 AM

Y by

The general situation is as follows:
When $p$ is an odd prime and $a$ is coprime to $p$ and $k$ is the order of $a$ modulo $p$ , then there are two cases:
1) Either $p^2 \mid a^k-1$ , in which case the order of $a$ modulo $p^2$ is also $k$ .
2) Either $p^2 \nmid a^k-1$ , in which case the order of $a$ modulo $p^2$ is $pk$ .
This can be easily seen by LTE (or direct binomial expansion, which is the same).
Now, clearly in case 1) any power of $a$ modulo $p$ lifts to a unique power of $a$ modulo $p^2$ , while in case 2) any power of $a$ modulo $p$ lifts to $p$ powers of $a$ modulo $p^2$ .
So the problem is equivalent to showing that in our case $a=2, p=2^{2^n}+1$ , case 2) must occur, i.e. we need to check that $p^2 \nmid 2^{2^{n+1}}-1$ which is trivial.

This post has been edited 1 time. Last edited by Tintarn, Apr 7, 2025, 10:17 AM

Z K Y

The post below has been deleted. Click to close.

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

32 posts

Avron

#5 h Apr 7, 2025, 3:27 PM

Y by

Let the order of $2$ mod $p$ be $a$ . Note that $a>2^n$ as $2^{2^n}-1<p$ , but also $2^{2^{n+1}}=(2^{2^n})^2=(p-1)^2\equiv 1$ mod $p$ so also $a$ divides $2^{n+1}$ thus $a=2^{n+1}$ . From this we get that:
$(2^a)^c=((p-1)^2)^c\equiv (1-2p)^c\equiv 1-2pc \text{ mod } p^2$ therefore if we let $b$ be an integer such that $2^k\equiv m+bp$ mod $p^2$ we get:
$(2^a)^c\cdot 2^k\equiv (1-2pc)(m+bp)\equiv m+p(b-2mc) \text{ mod } p^2$ so it is enough to prove that there exists such $c$ that $b-2mc$ is divisble by $p$ , but this is obvious as $gcd(2m,p)$ is clearly $1$ , so we're done.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a