Restricted primes

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

Restricted primes

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2025 Macedonian Balkan Math Olympiad TST Problem 4

The post below has been deleted. Click to close.

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

267 posts

#1 h Apr 14, 2025, 11:11 AM

Y by

Let $n$ be a positive integer. Prove that for every odd prime $p$ dividing $n^2 + n + 2$ , there exist integers $a, b$ such that $p = a^2 + 7b^2$ .

Z K Y

The post below has been deleted. Click to close.

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

1413 posts

#2 h Apr 14, 2025, 12:34 PM

Y by

Let's nail this. Check that $p\ne 3,5$ . Furthermore, $p\mid n^2+n+2\Leftrightarrow p\mid (2n+1)^2+7$ . Thus, $(-7/p)=1$ : there is a $u$ such that $u^2\equiv -7\pmod{p}$ . Applying now Thue's lemma, we deduce there exists $a,b$ such that $a\equiv ub\pmod{p}$ and that $0<a,b<\sqrt{p}$ . Notice that $a^2+7b^2\equiv (u^2+7)b^2\equiv 0\pmod{p}$ . Furthermore, $a^2+7b^2<8p$ . So, $a^2+7b^2\in\{p,2p,\dots,7p\}$ .

The rest is a (non-trivial) casework. If $a^2+7b^2=7p$ then $7\mid a$ . Setting $a=7a'$ , we find $p=b^2+7(a')^2$ . Next, if $a^2+7b^2\in\{3p,6p\}$ , we have $3\mid a^2+b^2$ , so $3\mid a,b$ . But then $9\mid a^2+7b^2$ , a contradiction. Similarly, if $a^2+7b^2=5p$ , then $5\mid a^2+2b^2$ , so $5\mid a,b$ , but then $25\mid 5p$ . Now, suppose $a^2+7b^2\in\{2p,4p\}$ . If $a,b$ are both odd, then $a^2+7b^2\equiv 0\pmod{8}$ , a contradiction. So, $a,b$ are both even. In this case, setting $a=2a'$ and $b=2b'$ , we see the case $2p$ is impossible, whereas if $a^2+7b^2=4p$ then $(a')^2+7(b')^2=p$ . We have exhausted all cases, finishing the proof.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a