Problem A. 539. (September 2011)
A. 539. Find all prime numbers p3 for which 1+k(p1) is prime for every integer .
Kolmogorov Cup, 2010
(5 pont)
Deadline expired on 10 October 2011.
Solution. We show that two such primes exist: 3 and 7.
p=3 satisfies the conditions since 1+1^{.}2=3 is a prime.
p=5 does not satisfies the condition since 1+2^{.}4=9 is composite.
p=7 satisfies the conditions since 1+1^{.}6=7, 1+2^{.}6=13 and 1+3^{.}6=19 are all primes.
p=11 does not satisfies the condition since 1+2^{.}10=21 is composite.
p=13 does not satisfies the condition since 1+2^{.}12=25 is composite.
In the rest of the solution we assume p17.
Suppose that some prime does not divide (p1). Then q and p1 are coprime, so there is such a , for which q1+k(p1). By qp1<1+k(p1), the number q is a proper divisor of (1+k(p1)), contradicting the assumption that 1+k(p1) is a prime.
Hence, p1 is divisible by all prime numbers less than p/2. Let r be the greatest prime which is less than p/2. By Chebysev's theorem we have . The numbers 2,3,r are distinct prime divisors of p1, so 6rp1. But this is not possible because p14r+2<6r.
Statistics:
18 students sent a solution.  
5 points:  Ágoston Tamás, Gyarmati Máté, Homonnay Bálint, Janzer Olivér, Kiss 065 Eszter, Kovács 444 Áron, Maga Balázs, Mester Márton, Nagy Bence Kristóf, Omer Cerrahoglu, Strenner Péter, Szabó 928 Attila, Tatár Dániel, Zilahi Tamás. 
3 points:  1 student. 
2 points:  1 student. 
1 point:  1 student. 
0 point:  1 student. 
