Greatest prime divisor of n^2+1

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

Greatest prime divisor of n^2+1

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: India Postals 2015 Set 2

The post below has been deleted. Click to close.

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

2280 posts

#1 h Nov 7, 2015, 12:04 PM • 2 Y

Y by Adventure10, Mango247

For every positive integer $n$ , let $P(n)$ be the greatest prime divisor of $n^2+1$ . Show that there are infinitely many quadruples $(a, b, c, d)$ of positive integers that satisfy $a < b < c < d$ and $P(a) = P(b) = P(c) = P(d)$ .

Z K Y

The post below has been deleted. Click to close.

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

Satyaprakash2009rta

506 posts

Satyaprakash2009rta

#2 h Nov 7, 2015, 3:18 PM • 6 Y

Y by Alcumus526, freefrom_i, laegolas, Adventure10, Mango247, Photaesthesia

Clearly, for fixed $p$ , the numbers $n$ for which $p|n^2+1$ are in two residue classes: $a\mod p$ and $-a\mod p$ .
(1a) $P(x^2+x+1)=\max\{P(x),P(x+1)\}$
(1b) $P(2x^2)=\max\{P(2x-1),P(2x+1)\}$
(these follow from factorizations)
(2) We have $P(2n-1)\le P(2n+1)\ge P(2n+3)$ for infinitely many $n$ .
(If there were finitely many such $n$ , then the sequence $p_n=P(2n-1)$ would be increasing after a while; but $p_n$ can be $2$ or of the form $4k+1$ because it divides a number of the form $N^2+1$ , hence in this case, we'd have $p_n\sim 4n$ . But this contradicts (1a) for large $n$ .)

Next idea: if $P(2n-1)\le P(2n+1)\ge P(2n+3)$ , then using (1b), we get $P(2n^2)=P(2(n+1)^2)=P(2n+1)=:p$ .
Also, take the smallest $a$ such that $p|a^2+1$ , then if $a$ and $p-a$ aren't among $2n+1,2n^2,2(n+1)^2$ , then we have found four numbers with $P(\cdot)=p$ . Exception: $a=2n+1$ , $p-a=2n^2$ , so $p=2n^2+2n+1$ .

Now we still can do more. If $P(2n)\le P(2n+1)$ , then from (1a), we also have $P(4n^2+2n+1)=p$ , done. Similarly done if $P(2n+2)\le P(2n+1)$ .

The remaining case: $P(2n),P(2n+2)>P(2n+1)$ .
So now we can get using the previous idea that
$P(2n) = P(4n^2-2n+1) = P(4n^2+2n+1) = q$
$P(2n+2)=P((2n+2)(2n+1)+1)=P((2n+2)(2n+3)+1)= q'$

Similarly, we are not done only when $4n^2+1=q$ and $(2n+2)^2+1=q'$ .

Finishing idea: for large $n$ , surely $p,q,q'>5$ . But we have $(2n)^2+1=q$ , $(2n+1)^2+1=2p$ , $(2n+2)^2+1=q'$ . These are not divisible by $5$ , which is only possible if $2n,2n+1,2n+2$ are $-1,0,1$ modulo $5$ , respectively.

Finally, let $b$ be the smallest number such that $q|b^2+1$ . We have $b=2n$ and $q-b=4n^2-2n+1$ and $q+b=4n^2+2n+1$ . So $b=-1\mod 5$ and $q=2\mod 5$ .

We claim that $P(3q-b)$ is $=q$ . This is true because $(3q-b)^2+1$ is divisible by $10$ (as $3q-b$ is $2\mod 5$ and it is odd), and it is smaller than $10q^2$ . So done: $P(b)=P(q-b)=P(q+b)=P(3q-b)$ .

This post has been edited 1 time. Last edited by Satyaprakash2009rta, Nov 7, 2015, 3:20 PM

Z K Y

The post below has been deleted. Click to close.

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

111 posts

#3 h Jun 7, 2016, 7:11 AM • 2 Y

Y by Adventure10, Mango247

This is problem A. 643. from KöMaL.
http://www.komal.hu/verseny/feladat.cgi?a=honap&l=en&h=201504&t=mat

This post has been edited 1 time. Last edited by Géza Kós, Jun 7, 2016, 7:12 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a