Russia 2002

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

Russia 2002

G H J

Reveal topic tags

modular arithmetic

arithmetic sequence

algebra unsolved

L

G H BBookmark kLocked kLocked NReply

Source: nice

The post below has been deleted. Click to close.

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

413 posts

#1 h Aug 25, 2007, 2:54 PM • 2 Y

Y by Adventure10, Mango247

What is the largest possible length of an arithmetic progression of positive integers $a_{1}, a_{2},\cdots , a_{n}$ with difference $2$ , such that ${a_{k}}^{2}+1$ is prime for $k = 1, 2, . . . , n$ ?

Z K Y

The post below has been deleted. Click to close.

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

23439 posts

pco

#2 h Aug 25, 2007, 3:51 PM • 1 Y

Y by Adventure10

Moonmathpi496 wrote:

What is the largest possible length of an arithmetic progression of positive integers $a_{1}, a_{2},\cdots , a_{n}$ with difference $2$ , such that ${a_{k}}^{2}+1$ is prime for $k = 1, 2, . . . , n$ ?

Take any three consecutive terms $a,a+2,a+4$ and look modulo 5 :
If $a=0\pmod{5}$ , then $(a+2)^{2}+1=0\pmod{5}$ and the second is divisible by $5$ .
If $a=1\pmod{5}$ , then $(a+2)^{2}+1=0\pmod{5}$ and the second is divisible by $5$ .
If $a=2\pmod{5}$ , then $a^{2}+1=0\pmod{5}$ and the first is divisible by $5$ .
If $a=3\pmod{5}$ , then $a^{2}+1=0\pmod{5}$ and the first is divisible by $5$ .
If $a=4\pmod{5}$ , then $(a+4)^{2}+1=0\pmod{5}$ and the third is divisible by $5$ .

So, among any three consecutive terms, one of the ${a_{k}}^{2}+1$ is divisible by $5$ , so is not prime (except if it is equal to 5).
So the maximum is two, except if the number $2$ is in the sequence. And in this case we can have a three-elements sequence :
$2,4,6$ which gives the three primes $5,17,37$ .

The answer is $3$ .

Z K Y

The post below has been deleted. Click to close.

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

1363 posts

Erken

#3 h Aug 25, 2007, 3:58 PM • 1 Y

Y by Adventure10

Answer: $n = 3$ .
Solution:
Denote $p_{i}= a_{i}^{2}+1$ .If $a_{i}\equiv 2,-2(mod 5)$ then $5|a_{i}^{2}+1$ .If $a_{i}> 2$ and $a_{i}\equiv 2,-2(mod 5)$ then $p_{i}$ isn't prime number.So it is obviously that among any three numbers $a,a+2,a+4$ exist one number that $\equiv 2,-2(mod 5)$ .Now if in the progression isn't exist $2$ ,then $n\leq 2$ .If $a_{1}= 2$ then $a_{2}= 4$ , $a_{3}= 6$ .And $p_{1}= 5,p_{2}= 17,p_{3}= 37$ .
Edit:I was too slow.I'm sorry pco.

Z K Y

The post below has been deleted. Click to close.

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

484 posts

#4 h Jan 13, 2008, 8:27 PM • 2 Y

Y by Adventure10, Mango247

Anyone have the whole problem set(with the distribution for each grades) and solution for russia 2002 & 2003?
Thanks

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a