Nordic 2025 P2

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

Nordic 2025 P2

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Nordic 2025

The post below has been deleted. Click to close.

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

24 posts

#1 h Mar 25, 2025, 12:35 PM

Y by

Let $p$ be a prime and suppose $2^{2p} \equiv 1 (\text{mod}$ $2p+1)$ is prime. Prove that $2p+1$ is prime $^{1}$

$^{1}$ This is a special case of Pocklington's theorem. A proof of this special case is required.

This post has been edited 3 times. Last edited by anirbanbz, Mar 25, 2025, 1:46 PM

Z K Y

The post below has been deleted. Click to close.

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

19 posts

#2 h Mar 25, 2025, 2:30 PM

Y by

If $p=2$ this is clear since $2\cdot 2 + 1 = 5$ . Let the order of $2$ modulo $2p+1$ be $g$ . This exists by the given congruence. We have $g\mid 2p\implies g \in \{1,2,p,2p\}$ . $g=1$ and $g=2$ obviously fail, and if $g=2p$ , then $2p\mid \varphi(2p+1)\implies \varphi(2p+1)=2p$ , so $2p+1$ is prime. So suppose $g=p$ . Let $2p+1 = p_1^{\alpha_1}\dots p_{k}^{\alpha_k}$ be the canonical factorization of $2p+1$ so that
$\varphi\left(2p+1\right)=p_1^{\alpha_1-1}\left(p_1-1\right)\dots p_k^{\alpha_k-1}\left(p_k-1\right)$ Since $p$ divides this and $p\nmid 2p+1$ , we have $p\mid p_i-1$ for some $i\in\{1,2,\dots,k\}$ so that $p<p_i$ . Let $2p+1=mp_i$ . If $m\ge 2$ , then
$2p+1 = mp_i\ge m\left(p+1\right)\ge 2p+2$ contradiction. So $m=1$ . So $2p+1=p_i$ , 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.

13 posts

#3 h Mar 25, 2025, 2:31 PM

Y by

Bravo!

:first:

Z K Y

The post below has been deleted. Click to close.

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

1405 posts

#4 h Mar 25, 2025, 2:33 PM • 2 Y

Y by AlexCenteno2007, ehuseyinyigit

Suppose that $2p+1$ is not a prime. Then, it has a prime divisor $2p+1>q>\sqrt{2p+1}$ . Using Fermat's theorem, we have $q\mid 2^{q-1}-1$ . Let $d$ be the smallest positive integer for which $q\mid 2^d-1$ . Then $d\mid 2p$ , forcing $d\in\{1,2,p,2p\}$ . The case $d=1$ is impossible. Likewise, it is evident $q<p$ so $d=p,2p$ are both impossible either, leaving $d=2$ . In this case, we have $q=3$ . As $q>\sqrt{2p+1}$ , we get $p<4$ . For $p=2,3$ $2p+1$ is prime. Otherwise, we have a contradiction that no such $q$ exists, i.e., $2p+1$ is a prime.

Z K Y

The post below has been deleted. Click to close.

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

DottedCaculator

7322 posts

DottedCaculator

#5 h Mar 25, 2025, 2:37 PM • 1 Y

Y by ehuseyinyigit

As $2p+1\geq5$ , the order of $2$ modulo $2p+1$ is a multiple of $p$ , so $p\mid\phi(2p+1)$ . If $p=2$ , $2p+1$ is prime. Otherwise, $\phi(2p+1)$ must be even, so $2p\mid\phi(2p+1)$ , implying $2p+1$ is prime.

Z K Y

The post below has been deleted. Click to close.

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

123 posts

KAME06

#6 h Mar 25, 2025, 4:44 PM

Y by

(1)Easy to see that $2p+1>1$ . Let $q$ a prime such that $q \mid 2p+1$ . Note that $q \neq p$ .
Is well known that $ord_{2p+1}(2)$ must divide $2p$ , so $ord_{2p+1}(2) \in \{1, 2, p, 2p\}$ .
-If $ord_{2p+1}(2)=1$ , then $2^1 \equiv 1 (\text{mod } 2p+1) \Rightarrow 1 \equiv 0 (\text{mod } 2p+1)$ , contradiction.
-If $ord_{2p+1}(2)=2$ , then $2^2 \equiv 1 (\text{mod } 2p+1) \Rightarrow 3 \equiv 0 (\text{mod } 2p+1)$ but $2p+1>2+1=3$ . Contradiction.
-If $ord_{2p+1}(2)=p$ , then $2^p \equiv 1 (\text{mod } 2p+1) \Rightarrow 2^p \equiv 1 (\text{mod } q)$ . Is well known that $ord_{q}(2)$ must divide $p$ , so $ord_{q}(2)=p$ (trivial that the order can't be 1).
Using Fermat's Little Theorem, $2^{q-1} \equiv 1 (\text{mod } q) \Rightarrow p \mid q-1$ . This last idea and (1) tell us that $p \le q-1 \le 2p+1-1=2p \Rightarrow q-1 \in \{ p, 2p\}$ .
$q-1=2p \Rightarrow q=2p+1$ and we're done. $q-1=p \Rightarrow q=p+1 \mid 2p+1 \Rightarrow p+1 \mid p$ . Contradiction.
-If $ord_{2p+1}(2)=2p$ , then $2^{2p} \equiv 1 (\text{mod } 2p+1) \Rightarrow 2^{2p} \equiv 1 (\text{mod } q)$ . We've already seen what happens if $ord_{q}(2) \in \{1, p\}$ .
-- $ord_{q}(2)=2 \Rightarrow 2^{2} \equiv 1 (\text{mod } q) \Rightarrow q=3$ . If $9 \mid 2p+1$ , $2^{2p} \equiv 1 (\text{mod } 9)$ . An easy check tell us that $ord_{9}(2)=6$ , so $p=3$ , but $9$ doesn't divide $2(3)+1=7$ . Contradiction. That implies that $2p+1=3$ .
-- $ord_{q}(2)=2p$ . Using Fermat's Little Theorem, $2^{q-1} \equiv 1 (\text{mod } q) \Rightarrow 2p \mid q-1$ . As before, $2p \le q-1 \le 2p+1-1=2p \Rightarrow q=2p+1$ and we're done.

Z K Y

The post below has been deleted. Click to close.

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

SimplisticFormulas

84 posts

SimplisticFormulas

#7 h Mar 26, 2025, 5:56 PM

Y by

soln

This post has been edited 1 time. Last edited by SimplisticFormulas, Mar 26, 2025, 7:00 PM

Z K Y

The post below has been deleted. Click to close.

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

1443 posts

#10 h Mar 26, 2025, 6:46 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

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

alexanderhamilton124

381 posts

alexanderhamilton124

#11 h Mar 27, 2025, 11:25 AM • 1 Y

Y by Nobitasolvesproblems1979

For $p = 3$ , we are done so assume $p \neq 3$ . Suppose, FTSOC, $2p + 1$ is not prime. If $2p + 1$ is a power of $3$ , note that $v_3(2^{2p} - 1) = 1 + v_3(p) = 1 \implies 2p + 1 = 3 \implies p = 1$ , a contradiction so assume $2p + 1$ is not a power of $3$ .

Consider a prime $q$ such that $q \mid 2p + 1$ , where $q \neq 3$ . Note that $q \mid 2^{2p} - 1 \implies \text{ord}_q(2) \mid 2p$ . So, $\text{ord}_q(2) = 1, 2, p, 2p$ . If $\text{ord}_q(2) = p$ , we have that $p \mid q - 1$ , but since $2p + 1$ isn't prime, $q \leq \frac{2p + 1}{3}$ (since $2p + 1$ is odd), and so $q - 1 < p$ , a contradiction. Similarly for $\text{ord}_q(2) = 2p$ . $\text{ord}_q(2) = 2$ means that $q = 3$ , another contradiction and $\text{ord}_q(2) = 1 \implies q = 1$ . So, $2p + 1$ has to be prime.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a