How Smooth Is $\phi(2^n+3)$?
Florian Luca · Rocky Mountain Journal of Mathematics · 2004
Introduction.For any integer n let P (n) denote the largest prime divisor of n with the convention that P (±1) = P (0) = 1.We also let φ(n) denote the Euler function of n.In this paper, we show, among other things, that P (φ(2 n + 3)) tends to infinity with n on a set of n of asymptotic density 1.The example 2 n +3 that we chose is not incidental and is, in a certain sense, the smallest example of numbers of the form 2 n + b, with a fixed integer b, and varying positive integers n, which is interesting for our type of problem.Suppose, let's say, that instead we look at the numbers 2 n +1.It is then well-known (see [2]), that for all sufficiently large n, the number 2 n +1 will have a prime divisor p which is congruent to 1 modulo n.In particular, n divides φ(2 n +1), and therefore P (φ(2 n +1)) ≥ P (n).Since P (n) tends to infinity on a set of n of asymptotic density 1 (see [3]), we get that P (φ(2 n +1)) tends to infinity on a set of n of asymptotic density 1 as well.This example also hints as to why it is difficult to show that P (φ(2 n + 1)) tends to infinity with n for all n.In fact, when n = 2 k is a power of two, the number F k := 2 2 k + 1 is what is known as a Fermat number.It is not known if there are infinitely many Fermat numbers which are primes, nor is it known if there are infinitely many Fermat numbers which are composite, but the standard believed conjecture is that there should be only finitely many Fermat numbers which are primes (see [5]).However, if this were not so, that is if infinitely many Fermat numbers F k were primes, then for such k we would have P (φ(2 2 k + 1)) = 2, which shows why it is difficult to prove that P (φ(2 n + 1)) tends to infinity with n for all values of n.Since φ(2 n + 2) = φ(2 n-1 + 1), it follows that the same arguments as above apply to P (φ(2 n + 2)), which is why we have chosen to look at the numbers of the form 2 n + 3.The numbers of the form 2 n + 3 were chosen only as an example, and in this paper we will formulate and prove our main Theorem in