KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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 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 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.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley