values of n for which φ(n)=τ(n)


Within this entry, we use the following notation:

Within this entry, we will determine all values of n for which φ(n)=τ(n).

Define γ: by

γ(n)=τ(n)φ(n).

Note that γ is a multiplicative functionMathworldPlanetmath since both φ and τ are. Thus, we will initially focus on the values of γ at prime powers. We will need specific values of γ(pk). These are calculated below.

γ(1)=11=1γ(2)=21=2γ(4)=32γ(8)=44=1γ(16)=58γ(32)=616=38γ(3)=22=1γ(9)=36=12γ(5)=24=12

Note that

γ(pk)=τ(pk)φ(pk)=k+1pk-1(p-1).

If p is fixed, we can extend this to a continuous functionMathworldPlanetmathPlanetmath Γp: defined by

Γp(x)=x+1px-1(p-1).

We investigate the derivativePlanetmathPlanetmath (http://planetmath.org/Derivative) of Γp for x1:

Γp(x)=1p-1px-1-(x+1)px-1lnp(px-1)2=1-(x+1)lnppx-1(p-1)<1-2ln2px-1(p-1)<0.

Thus, for p fixed and k1, γ(pk) is a strictly decreasing function of k.

On the other hand, from the equation

γ(pk)=k+1pk-1(p-1),

it is clear that, if k is fixed, γ(pk) is a strictly decreasing function of p.

Thus, we have proven the following:

Lemma 1.

Let p be a prime and k be a nonnegative integer with pk{1,2,3,4,8,16}. Then

γ(pk)12

with equality holding if and only if pk{5,9}.

This lemma has an immediate consequence:

Lemma 2.

Let m be an odd natural number. Then

γ(m)=1 or γ(m)12.

Moreover, γ(m)=1 if and only if m=1 or m=3.

Now we will examine the general case. Let φ(n)=τ(n). Then γ(n)=1.

Suppose that 4n. Let m be an odd natural number with n=4m. Thus,

1=γ(n)=γ(4m)=γ(4)γ(m)=32γ(m).

Therefore,

γ(m)=23,

which contradicts the second lemma. Hence, 4∦n.

Suppose that 16n. Let m be an odd natural number with n=2km. Then k4. Thus,

1=γ(n)=γ(2km)=γ(2k)γ(m)γ(16)γ(m)=58γ(m).

Therefore,

γ(m)85,

which contradicts the second lemma. Hence, 16n.

Now we deal with the cases that can actually occur.

  • Case I: n is odd

    The second lemma immediately applies, yielding n=1 or n=3.

  • Case II: 2n and 3n

    Let m be an odd natural number with n=2m. Then 3m and

    1=γ(n)=γ(2m)=γ(2)γ(m)=2γ(m).

    Thus,

    γ(m)=12.

    By the first lemma, for all pkm with k>0,

    γ(pk)12

    with equality holding if and only if pk=5. Therefore, m=5. Hence n=10.

  • Case III: 2n and 3n

    Let m be an odd natural number with n=6m. Then 3m and

    1=γ(n)=γ(6m)=γ(2)γ(3)γ(m)=2γ(m).

    Thus,

    γ(m)=12.

    By the first lemma, for all pkm with k>0,

    γ(pk)12

    with equality holding if and only if pk=5. Therefore, m=5. Hence n=30.

  • Case IV: 2n and 9n

    Let m be an odd natural number with 3m such that n=23km. Then k2 and

    1=γ(n)=γ(23km)=γ(2)γ(3k)γ(m)=2γ(3k)γ(m)2γ(9)γ(m)=γ(m).

    Since 3m, the second lemma yields that m=1. Thus,

    1=γ(n)=γ(23k)=γ(2)γ(3k)=2γ(3k).

    Therefore,

    γ(3k)=12.

    By the first lemma, k=2. Hence, n=18.

  • Case V: 8n

    Recall that 16n. Thus, there exists an odd natural number m with n=8m. Then

    1=γ(n)=γ(8m)=γ(8)γ(m)=γ(m).

    The second lemma yields that m=1 or m=3. Hence, n=8 or n=24.

It follows that

{n:φ(n)=τ(n)}={1,3,8,10,18,24,30}.

This list of numbers appears in the OEIS as sequenceMathworldPlanetmath http://www.research.att.com/ njas/sequences/A020488A020488.

Title values of n for which φ(n)=τ(n)
Canonical name ValuesOfNForWhichvarphintaun
Date of creation 2013-03-22 18:03:48
Last modified on 2013-03-22 18:03:48
Owner Wkbj79 (1863)
Last modified by Wkbj79 (1863)
Numerical id 12
Author Wkbj79 (1863)
Entry type Feature
Classification msc 11A25
Related topic EulerPhifunction
Related topic TauFunction