# What is the smallest value of $n$ for which $\phi(n) \ne \phi(k)$ for any $k<n,$ where $n=4m$?

Let $\phi(n)$ be Euler's totient function. For $n=4m$ what is the smallest $n$ for which

$$\phi(n) \ne \phi(k) \textrm{ for any } k<n \textrm{ ?} \quad (1)$$

When $n=4m+1$ and $n>1$ the smallest is $n=5$ and when $n=4m+3$ it's $n=3.$ However, when $n=4m+2$ the above condition can never be satisfied since

$$\phi(4m+2) = (4m+2) \prod_{p | 4m+2} \left( 1 - \frac{1}{p} \right)$$ $$= (2m+1) \prod_{p | 2m+1} \left( 1 - \frac{1}{p} \right) = \phi(2m+1).$$

In the case $n=4m,$ $n=2^{33}$ is a candidate and $\phi(2^{33})=2^{32}.$ This value satisfies $(1)$ because $\phi(n)$ is a power of $2$ precisely when $n$ is the product of a power of $2$ and any number of distinct Fermat primes:

$$2^1+1,2^2+1,2^4+1,2^8+1 \textrm{ and } 2^{16}+1.$$

Note the $n=2^{32}$ does not satisfy condition $(1)$ because the product of the above Fermat primes is $2^{32}-1$ and so $\phi(2^{32})=2^{31}=\phi(2^{32}-1)$ and $2^{32}-1 < 2^{32}.$

The only solutions to $\phi(n)=2^{32}$ are given by numbers of the form $n=2^a \prod (2^{x_i}+1)$ where $x_i \in \lbrace 1,2,4,8,16 \rbrace$ and $a+ \sum x_i = 33$ (note that the product could be empty), so all these numbers are necessarily $\ge 2^{33}.$

Why don't many "small" multiples of $4$ satisfy condition $(1)$? Well, note that for $n=2^a(2m+1)$ we have

$$\phi(2^a(2m+1))= 2^a(2m+1) \prod_{p | 2^a(2m+1)} \left( 1 - \frac{1}{p} \right)$$ $$= 2^{a-1}(2m+1) \prod_{p | 2m+1} \left( 1 - \frac{1}{p} \right) = 2^{a-1}\phi(2m+1),$$

and so, for $a \ge 2,$ if $2^{a-1}\phi(2m+1)+1$ is prime we can take this as our value of $k<n$ and we have $\phi(n)=\phi(k).$ This, together with the existence of the Fermat primes, seems to be why it's difficult to satisfy when $n=4m.$

I have only made hand calculations so far, so I would not be too surprised if the answer is much smaller than my suggestion. The problem is well within the reach of a computer, and possibly further analysis without the aid of a computer. But, anyway, I've decided to ask here as many of you have ready access to good mathematical software and I'm very intrigued to know whether there is a smaller solution than $2^{33}.$

Some background information:

This question arose in my search to bound the function $\Phi(n)$ defined as follows.

Let $\Phi(n)$ be the number of distinct values taken on by $\phi(k)$ for $1 \le k \le n.$ For example, $\Phi(13)=6$ since $\phi(k)$ takes on the values $\lbrace 1,2,4,6,10,12 \rbrace$ for $1 \le k \le 13.$

It is clear that $\Phi(n)$ is increasing and increases by $1$ at each prime value of $n,$ except $n=2,$ but it also increases at other values as well. For example, $\Phi(14)=6$ and $\Phi(15)=7.$

Currently, for an upper bound, I'm hoping to do better than $\Phi(n) \le \lfloor (n+1)/2 \rfloor .$

But this this not the issue at the moment, although it may well become a separate question.

This work originates from this stackexchange problem.

-
I checked up to 10^7 and found no examples. I'll run something overnight and see how far it gets. – Matthew Conroy Feb 1 '11 at 0:57
Shoot: Pari/GP has a bound on vectors somewhere less than 1.7x10^7. I'll have to use a different method. – Matthew Conroy Feb 1 '11 at 4:08
I wrote a quick program to compute some values of your function ($\Phi$ that is). It seems like you should certainly be able to get a better lower bound. I've computed into the twenty thousands and the ratio of the terms appears to be approaching 1/5 for instance $\Phi(25000)=5032$. It may be going lower, I'll let it run over night and see how far it gets. It may actually be slowing down more now that I look at a few values. – JSchlather Feb 1 '11 at 8:24
@Matthew: Thanks for that! It makes me glad that I decided to give up on the hand calculations, post the question and go to bed. Please let me know if your program finds a solution. Thanks. – Derek Jennings Feb 1 '11 at 9:31
@Jacob: Thanks for your time. I, too, think that a better lower bound than that implied by the PNT should be within reasonable reach, but I haven't yet given much thought to that side. My question arose when I was looking at the upper bound. Thanks for posting those numbers. I'm still trying to understand the behaviour of $\Phi(n),$ so please let me know if you have any further interesting results. Thanks. – Derek Jennings Feb 1 '11 at 9:39

$33817088 = 2^9 \cdot 257^2 = 2^9 \cdot (2^8 + 1)^2$

with

$\phi(33817088) = 16842752 = 2^{16} \cdot (2^8 + 1) = 2^{16} \cdot 257\;.$

Here's the Java code to find it (it takes a couple of seconds to run on a MacBook Pro):

import java.util.Arrays;

public class Totient {
final static int mod4 = 0;     // remainder mod 4 to test
final static int n = 40000000; // highest number to test

static boolean [] prime = new boolean [n / 2]; // prime [i] : is 2i + 1 prime?
static boolean [] seen = new boolean [n];      // seen [i] : we've seen phi (n) = i
static int [] phi = new int [n];               // phi [i] : phi (i)

public static void main (String [] args) {
Arrays.fill (prime,true);
Arrays.fill (seen,false);
Arrays.fill (phi,1);

// calculate the primes we need
int limit = (int) Math.sqrt (n); // highest factor to test
for (int p = 3;p <= limit;p += 2) // loop over odd integers
if (prime [p >> 1])            // only test primes p
for (int k = 3*p;k < n;k += 2*p) // loop over odd multiples of p
prime [k >> 1] = false;      // sieve them out

// fill phi by looping over all primes
fill (2);
for (int p = 3;p < n;p += 2)
if (prime [p >> 1])
fill (p);

// now go through phi, remembering which values we've already seen
for (int i = 1;i < n;i++) {
if ((i & 3) == mod4 && !seen [phi [i]]) {
System.out.println ("found " + i + " with phi (" + i + ") = " + phi [i]);
return;
}
seen [phi [i]] = true;
}
}

// multiply all phi values by their factors of prime p
static void fill (int p) {
// once for the first factor of p
for (int i = p;i < n;i += p)
phi [i] *= p - 1;

// and then for the remaining factors
long pow = p * (long) p; // long to avoid 32-bit overflow
while (pow < n) {
for (int i = (int) pow;i < n;i += pow)
phi [i] *= p;
pow *= p;
}
}
}

-