Maths Olympiad Prep

Library / /13 of 63

Number theory Difficulty 6.4 National olympiad Prove it Japan

For every positive integer nn, let f(n)f(n) be the smallest positive integer such that f(n)f(n) is prime to nn and f(n)+1f(n) + 1 is prime to n+1n + 1. How many different integers will appear in {f(1),f(2),,f(1010)}\{f(1), f(2), \dots, f(10^{10})\}?

Solution

11

First, we prove f(n)=p1f(n) = p-1 for a positive integer nn and the smallest prime pp that does not divide n+1n+1. For any integer mm with 1m<p11 \le m < p-1, m+1m+1 has a prime factor qq with q<pq < p. Since qq must divide n+1n+1 from the definition of pp, m+1m+1 cannot be prime to n+1n+1, thus f(n)p1f(n) \ge p-1. On the other hand, every prime factor of p1p-1 must divide n+1n+1, again from the definition of pp, thus it cannot divide nn. Hence p1p-1 is prime to nn and pp is prime to n+1n+1, which yields f(n)=p1f(n) = p-1.

Let pnp_n denote the nn-th smallest prime and let ak=p1p2pk1a_k = p_1p_2\cdots p_k - 1. {ak}\{a_k\} is a strictly increasing sequence with 6469693229=a101010<a11=2005604901296469693229 = a_{10} \le 10^{10} < a_{11} = 200560490129. From the above statement, if 1n10101 \le n \le 10^{10} then there exists 1k111 \le k \le 11 such that f(n)=pk1f(n) = p_k - 1 (note that n+1a11n+1 \le a_{11} and cannot be divided by at least one of {p1,p2,,p11}\{p_1, p_2, \dots, p_{11}\}). On the other hand, f(2)=1=p11f(2) = 1 = p_1 - 1 and f(ak)=pk+11f(a_k) = p_{k+1} - 1 for 1k101 \le k \le 10, since ak+1a_k + 1 is divided by p1,p2,,pkp_1, p_2, \dots, p_k and not by pk+1p_{k+1}. Hence, {f(1),f(2),,f(1010)}\{f(1), f(2), \dots, f(10^{10})\} consists of 11 integers, p11,p21,,p111p_1 - 1, p_2 - 1, \dots, p_{11} - 1.

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 and solution reproduced as published; topic and difficulty added by this site.