Primes in arithmetic progression (Posted on 2008-09-30)

	Submitted by pcbouhid
No Rating
Solution:	(Hide)
"The USSR Olympiad Problem Book", by D.O.Shklarsky, N.N.Chentzov, I.M.Yaglom, problem n. 70, solution at page 152. Since all primes exceeding 2 are odd, the common difference of the AP sought must be an even number; hence we may eliminate 2 as a possible term of the progression. Also, since there are certainly three successive terms of the progression, all of which exceed 3 and which by themselves must form an AP, the common difference d must be divisible by 6, that is divisible by 2 and 3. We now show that d must be divisible by 5. Assume d is not divisible by 5. Then the numbers a, a+d, a+2d, a+3d, a+4d, all yield different remainders ipon divisible by 5 (if two of the remainders are equal, then it is easily shown that d is divisible by 5, a contradiction of the assumption just made). Thus, one of the numbers of the progression is then divisible by 5. Since all the terms of the progression are prime, this is a contradiction. Hence d must be divisible by 5. We can show, in the same manner, that d must be divisible by 7 (this conclusion cannot be reached for 11, since there are to be only ten terms in the progression, and a, a+d, a+2d,..., a+9d would not necessarily provide a number divisible by 11.) Therefore, the common difference d of the progression must be a multiple of 2*3*5*7 = 210; that is, d = 210*k. According to the conditions of the problem, a10 = a1 + 9d = a1 + 1890k < 3000. This inequality is impossible for k >= 2, hence, necessarily, k = 1. It follows that a>sub>1 < 3000 - 9d = 3000 - 1890 = 1110. Now, 210 = 11*19 + 1; consequentely, the (m+1)st term of the progression may be represented in the form an+1 = a1 + (11*19 + 1)*m = 11*19m + (a1 + m). It follows that if a1 yields a remainder of 2 upon division by 11, then a10 is divisible by 11. If a1 yields a remainder of 3 when divided by 11, then a9 is divisible by 11, and so on. Therefore, a1 cannot yield upon division by 11 any of the remainders 2, 3, 4, ..., or 10. If a1 <> 11, then since a1 is prime it cannot be divisible by 11; this means that either a1 = 11 or a1 yields a remainder of 1 upon division by 11. Further, since 210 = 13*16 + 2, and so an+1 = a1 + (13*16 + 2)*m = 13*16m + (a1 + 2m), it may be shown that if a1 is divisible by 13, it can yield as a remainder only one of the numbers 2, 4, 6, 8, 10, or 12. Since a1 is odd (as are all terms of the progression), either a1 = 11 or it can be written in one of the following forms: 2*11*13*j + 23 = 286j + 23 or 286j + 45 or 286j + 67 or 286j + 155 or 286j + 177 or 286j + 199. Since a1 < 1110, the possible values for a1 are limited to the integers 11; 23, 309, 595, 881; 45, 331, 615, 903; 67, 353, 637, 925; 155, 441, 727, 1013; 177, 463, 749, 1035; 199, 485, 771, 1057; of which the following are prime: 11, 23, 881, 331, 67, 353, 727, 1013, 463, 199. We found the necessary conditions for the existence of the progression sought; namely, d = 210, and a1 equal to one of the prime numbers listed. We must test each of the possibilities (for example, a1 = 11 is quickly found untenable, since then a2 = 221 = 13*17, which is not prime. Exactly one of the above primes, a1 = 199, will produce an acceptable progression: 199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089.

	Subject	Author	Date
	re: Well...	Charlie	2008-10-01 11:10:14
	Slightly larger	ed bottemiller	2008-09-30 20:07:00
	Also see	Gamer	2008-09-30 17:41:57
	Interesting and necessary	Gamer	2008-09-30 17:40:12
	re: Interesting	pcbouhid	2008-09-30 17:20:34
	Interesting	Leming	2008-09-30 14:59:32
	Well...	ed bottemiller	2008-09-30 13:27:20
	Solution	ed bottemiller	2008-09-30 13:17:13
	computer solution	Charlie	2008-09-30 13:16:46