Maths Olympiad Prep

Library / Taiwan IMO Selection Camp /149 of 359

Taiwan IMO Selection Camp

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+1−1ϕ(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, bi−1=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+1−1ϕ(bi+1)=2ribi2^{r_{i+1}-1}\phi(b_{i+1}) = 2^{r_i}b_i shows that ri+1≤rir_{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 i≥ni \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+2−12pi+2si+2−1=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 i≥ni \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=bj−1k = b_j - 1, then by Fermat's Little Theorem, bj+k≡(bj+1)−1≡0(modbj)b_{j+k} \equiv (b_j + 1) - 1 \equiv 0 \pmod{b_j}, hence bj∣bj+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,604 problems in a working order, from Junior Challenge 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.