Problem A. 539. (September 2011)
A. 539. Find all prime numbers p3 for which 1+k(p-1) is prime for every integer .
Kolmogorov Cup, 2010
Deadline expired on October 10, 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 (p-1). Then q and p-1 are coprime, so there is such a , for which q|1+k(p-1). By qp-1<1+k(p-1), the number q is a proper divisor of (1+k(p-1)), contradicting the assumption that 1+k(p-1) is a prime.
Hence, p-1 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 p-1, so 6r|p-1. But this is not possible because p-14r+2<6r.
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.