Maths Olympiad Prep

Library / /113 of 397

Number theory Difficulty 5.4 AIME, harder Prove it Taiwan

Prove that: In the arithmetic sequence 11,21,31,41,51,61,11, 21, 31, 41, 51, 61, \ldots, there exist infinitely many primes.

Solution

Consider the integer N=(11314161pn)51N = (11 \cdot 31 \cdot 41 \cdot 61 \cdots p_n)^5 - 1. Then NN is relatively prime to 11,41,pn11, 41, \cdots p_n. Let a=11314161pna = 11 \cdot 31 \cdot 41 \cdot 61 \cdots p_n, then
N=a51=(a1)(a4+a3+a2+a+1). N = a^5 - 1 = (a-1)(a^4 + a^3 + a^2 + a + 1).
Clearly, 2(a4+a3+a2+a+1)2 \nmid (a^4 + a^3 + a^2 + a + 1), but 5(a4+a3+a2+a+1)5 \nmid (a^4 + a^3 + a^2 + a + 1). Let p5p \neq 5 be a prime factor of a4+a3+a2+a+1a^4 + a^3 + a^2 + a + 1. Therefore, p(a1)p \nmid (a-1). The reason is as follows:

If p(a1)p \nmid (a-1), then a=kp+1a = kp + 1, for some integer kk, which gives
a2=(kp+1)2,a3=(kp+1)3,a4=(kp+1)4, a^2 = (kp + 1)^2, \quad a^3 = (kp + 1)^3, \quad a^4 = (kp + 1)^4,
and
a4+a3+a2+a+1=(kp+1)4+(kp+1)3+(kp+1)2+(kp+1)+15(modp). a^4 + a^3 + a^2 + a + 1 = (kp+1)^4 + (kp+1)^3 + (kp+1)^2 + (kp+1) + 1 \equiv 5 \pmod{p}.
In fact, (p1)4(mod5)(p-1) \equiv 4 \pmod{5}, that is, p1=5k+4p-1 = 5k + 4.

By Fermat's theorem, p(ap11)p \nmid (a^{p-1} - 1). But at this point
ap11=a5k+41=a4(a5k1)+(a41), a^{p-1} - 1 = a^{5k+4} - 1 = a^4(a^{5k} - 1) + (a^4 - 1),
and since (a51)(a5k1)=(a5)k1k(a^5 - 1) \nmid (a^{5k} - 1) = (a^5)^k - 1^k, this means p(a5k1)p \nmid (a^{5k} - 1). That is, p(a41)p \nmid (a^4 - 1). However
a51=a(a41)+(a1) a^5 - 1 = a(a^4 - 1) + (a - 1)
Therefore, if p(a51)p \nmid (a^5 - 1) and p(a41)p \nmid (a^4 - 1), then p(a1)p \nmid (a - 1). The above cannot happen. By a similar approach, we obtain that the remainder of (p1)(p-1) divided by 55 cannot be 1,2,31, 2, 3.

Hence 5(p1)5|(p-1) and p1p-1 is even. We get 10(p1)10|(p-1), that is, p=10k+1p = 10k + 1, so pp is one of the terms of the given arithmetic sequence. Therefore, the prime factors of a4+a3+a2+a+1a^4 + a^3 + a^2 + a + 1 are 55 and primes of the form 10k+110k + 1.

However a4+a3+a2+a+1>5a^4 + a^3 + a^2 + a + 1 > 5, and 52(a4+a3+a2+a+1)5^2 \nmid (a^4 + a^3 + a^2 + a + 1). In fact, the integer aa has last digit 11, that is, a=5k+1a = 5k + 1. By the binomial theorem, we get
a4+a3+a2+a+1=(5k+1)4+(5k+1)3+(5k+1)2+(5k+1)+1=5[5(25k4+25k3+10k2+2k)+1]. \begin{aligned} a^4 + a^3 + a^2 + a + 1 &= (5k + 1)^4 + (5k + 1)^3 + (5k + 1)^2 + (5k + 1) + 1 \\ &= 5 \cdot [5(25k^4 + 25k^3 + 10k^2 + 2k) + 1]. \end{aligned}
Therefore N=a51N = a^5 - 1 has at least one prime factor of the form 10k+110^k + 1. But by the above, NN is relatively prime to all numbers of the form 10k+110^k + 1. This is a contradiction.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from the original; metadata (topic, difficulty) added by this project.