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.

  • $\begingroup$ I checked up to 10^7 and found no examples. I'll run something overnight and see how far it gets. $\endgroup$ – Matthew Conroy Feb 1 '11 at 0:57
  • $\begingroup$ Shoot: Pari/GP has a bound on vectors somewhere less than 1.7x10^7. I'll have to use a different method. $\endgroup$ – Matthew Conroy Feb 1 '11 at 4:08
  • $\begingroup$ 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. $\endgroup$ – JSchlather Feb 1 '11 at 8:24
  • $\begingroup$ @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. $\endgroup$ – Derek Jennings Feb 1 '11 at 9:31
  • $\begingroup$ @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. $\endgroup$ – Derek Jennings Feb 1 '11 at 9:39

The answer is

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


\[\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]);
            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;
  • $\begingroup$ Sure but finding an answer that only tells us a the value asked for quite easy with access to the computational power of java, this does not qualify as an answer in the mathematics community albeit with some explanations of how the code works, it's necessary to describe things in a more formal manner with regard to how an answer in mathematics should be presented. $\endgroup$ – Adam L Sep 28 '18 at 23:12
  • 1
    $\begingroup$ @Adam: I disagree (along with $11$ upvoters and the OP who marked this as the accepted answer, all of whom are members of this mathematics community just like you). There are many questions on this site that no one was able to answer without a computer and that I answered using a computer. I agree that any mathematics required to write or understand the code should be explained, but in the present case I used nothing more than well-known basic facts about Euler's totient function. $\endgroup$ – joriki Sep 29 '18 at 12:13
  • 1
    $\begingroup$ @Adam: No, that's not what I'm saying, those are your words. I was merely replying to your claim that "this does not qualify as an answer" and arguing that it does. $\endgroup$ – joriki Sep 29 '18 at 14:51
  • 1
    $\begingroup$ @Adam: Unfortunately I don't. This is a computer programme. It would make no sense to express it in mathematical form; I'm not even sure what exactly you mean by that. The purpose of including the programme isn't to convey mathematics, but rather that people can also run the programme or check or expand or fix it or whatever; all of this only works if I include it as a programme. The mathematics behind the programme is trivial; you can read up on it at Wikipedia; it's basically $\phi(\prod_ip_i^{k_i})=\prod_ip_i^{k_i-1}(p_i-1)$. And I do think the upvotes and the checkmark indicate acceptance. $\endgroup$ – joriki Sep 29 '18 at 18:38
  • 1
    $\begingroup$ @Adam: Of course not. "Level of insight" isn't a relevant category here. A question was asked, and I answered it. If you'd written "Posting a programme doesn't demonstrate any insight", I would have fully agreed. That's not what you wrote, though. You wrote "this does not qualify as an answer". It does, and $11$ people agree with me on that. If you don't agree, you can downvote. $\endgroup$ – joriki Sep 30 '18 at 4:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.