Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem A. 539. (September 2011)

A. 539. Find all prime numbers p\ge3 for which 1+k(p-1) is prime for every integer 1\le k\le\frac{p-1}2.

Kolmogorov Cup, 2010

(5 pont)

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 p\ge17.

Suppose that some prime q\le\frac{p-1}2 does not divide (p-1). Then q and p-1 are coprime, so there is such a 1\le k\le q\le\frac{p-1}2, for which q|1+k(p-1). By q\lep-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 r\ge\left[\frac{p-1}4\right]\ge\frac{p-3}4>3. The numbers 2,3,r are distinct prime divisors of p-1, so 6r|p-1. But this is not possible because p-1\le4r+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.

Problems in Mathematics of KöMaL, September 2011