Maths Olympiad Prep

Library / /162 of 397

Number theory Difficulty 5.6 AIME, harder Prove it Taiwan

For any positive integer mm, we define ϕ(m)\phi(m) to be the number of positive integers less than mm and relatively prime to mm.
Question: Does there exist an infinite sequence of positive integers a1,a2,,an,a_1, a_2, \dots, a_n, \dots, satisfying:
(i) a1=(2011)!=1×2××2011. (i) \ a_1 = (2011)! = 1 \times 2 \times \dots \times 2011.
(ii) For each positive integer i,ai=ϕ(ai+1). (ii) \ \text{For each positive integer } i, a_i = \phi(a_{i+1}).

Solution

No such sequence exists. We use proof by contradiction, assuming such an infinite sequence exists, we express each aia_i as ai=2ribia_i = 2^{r_i}b_i, where bib_i is odd. Then by properties of the ϕ\phi-function, we have ai=ϕ(ai+1)=2ri+11ϕ(bi+1)a_i = \phi(a_{i+1}) = 2^{r_{i+1}-1}\phi(b_{i+1}).

Note that bi+1b_{i+1} cannot be 11, otherwise we would get bi=1b_i = 1, bi1=1,b_{i-1} = 1, \dots, and finally b1=1b_1 = 1, which obviously contradicts a1=(2011)!a_1 = (2011)!. In this case we have ϕ(bi+1)\phi(b_{i+1}) is even. Comparing 2ri+11ϕ(bi+1)=2ribi2^{r_{i+1}-1}\phi(b_{i+1}) = 2^{r_i}b_i shows that ri+1rir_{i+1} \le r_i.

Since rir_i are all nonnegative integers, they cannot keep decreasing forever, so there must exist some positive integer nn after which (below we always assume the variable ini \ge n) we have ri=ri+1r_i = r_{i+1}. Comparing the above equation shows that 4ϕ(bi+1)4 \nmid \phi(b_{i+1}), and
2bi=ϕ(bi+1)2b_i = \phi(b_{i+1}).

By properties of the ϕ\phi-function, if ϕ(bi+1)\phi(b_{i+1}) is not a multiple of 4, then bi+1b_{i+1} must be a power of some odd prime, denote bi+1=pi+1si+1b_{i+1} = p_{i+1}^{s_{i+1}}, where pi+1p_{i+1} is a prime. Now consider bi+2=pi+2si+2b_{i+2} = p_{i+2}^{s_{i+2}}, we have
bi+1=ϕ(bi+2)2=pi+212pi+2si+21=pi+1si+1. b_{i+1} = \frac{\phi(b_{i+2})}{2} = \frac{p_{i+2} - 1}{2} p_{i+2}^{s_{i+2}-1} = p_{i+1}^{s_{i+1}}.
Hence pi+2=3p_{i+2} = 3 or si+2=1s_{i+2} = 1.

If pi+2=3p_{i+2} = 3 (for some ii), then ai+2a_{i+2} has only the two prime factors 2 and 3, and it is easy to check that subsequently ϕ(ai+2),ϕ(ϕ(ai+2)),\phi(a_{i+2}), \phi(\phi(a_{i+2})), \dots will also only have prime factors 2 and 3, but a1=(2011)!a_1 = (2011)!, a contradiction, so we must have si+2=1s_{i+2} = 1, that is, bi+2=pi+2b_{i+2} = p_{i+2} (for all ini \ge n).

Thus, for all j(n+2)j \ge (n+2), we have bj+1=2bj+1b_{j+1} = 2b_j + 1, and these bjb_j are all primes. We note that for any positive integer kk, bj+k=2k(bj+1)1b_{j+k} = 2^k(b_j + 1) - 1. Let k=bj1k = b_j - 1, then by Fermat's Little Theorem, bj+k(bj+1)10(modbj)b_{j+k} \equiv (b_j + 1) - 1 \equiv 0 \pmod{b_j}, hence bjbj+kb_j|b_{j+k}, which contradicts bj+kb_{j+k} being prime. This completes the proof.

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 zh; metadata (topic, difficulty) added by this project.