[Math] Find all numbers $n$ such that $\phi (n) = 20$

elementary-number-theorytotient-function

I'm trying to find all values of $n$ that satisfy euler's phi function in the title.

I start by knowing $n$ cannot be a power of $2$ since $\phi (n)$ is not. Then, $n$ is divisible by an odd prime.

I try to find odd primes satisfying $(p-1)|20$ and so my list is $3,5,11$. Then, $n=2^a3^b5^c11^d$. I'm stuck here, since I don't know how to bound my exponents or what values to use.

I think $a\leq 2$ because $2^2|\phi(n)$. So far I have generated:

$n=2^2\cdot 11, 2\cdot 3\cdot 11, 3\cdot 11$, or $44,66,33$. This was done through trial and error i.e. sampling values for exponents and checking if they satisfy the phi function. Is there an algebraic way to determine the exponents / check if there are other solutions?

Best Answer

I start by knowing $n$ cannot be a power of $2$ since $\phi (n)$ is not. Then, $n$ is divisible by an odd prime.

I try to find odd primes satisfying $(p-1)|20$ and so my list is $3,5,11$. Then, $n=2^a3^b5^c11^d$. I'm stuck here, since I don't know how to bound my exponents or what values to use.

This is good work so far. To continue, show that if $p$ is prime and $p^x$ divides $n$, then $p^{x-1}$ divides $\phi(n)$. Of the primes in your list ($2, 3, 5, 11$), which ones can have $p^{x-1}$ divides $n$, assuming $x \ge 2$?

What about if $x \ge 3$? In this case, $p^2$ would have to divide $20$.

This should let you narrow down to a finite (fairly small) number of possibilities for $a$, $b$, $c$, and $d$ in $n = 2^a 3^b 5^c 11^d$.

Related Solutions

Number Theory – Smallest n with Unique Totient Function Value

The answer is

\[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;
        }
    }
}

For any $a$, can we find $b$ and $c$ such that $\phi(a^2)+\phi(b^2)=\phi(c^2)$? ($\phi$ is Euler’s totient function.)

(This might need some editing later, it's a bit messy.)

As a summary, for any given $a$ there are always solutions for the equation $$ \varphi(a^2) + \varphi(b^2) = \varphi(c^2) $$

The approach is similar to the one described in the OP. We consider all cases of prime factors $2,3,5,7$ of $a$, then find appropriate $b$ and $c$ using that information.

Let $r,s,t$ be the exponent of prime factors $2,3,5$ of $a$. We write $$ a=2^r3^s5^tm $$

Proposition: If $(r,s,t)$ is not of the form $r=1,s=1$ and $t\geq 2$, then there is a solution.

We shall solve the various cases as follows:
Case 1: $r=0$.
Case 2: $r\geq 1$ and $s=0$.
Case 3: All remaining cases except $r=1,s=1$ and $t\geq 2$.

For the exceptional case $r=1,s=1,t\geq 2$, we require prime $7$. This is handled in case 4.

Case 1: $r=0$

This case is covered in the OP: Since $\gcd(r,2)=1$, $$ \varphi(a^2)+\varphi(a^2)=2\varphi(a^2)= \varphi((2a)^2) $$ so we set $b=a,c=2a$.

Hence we assume $r\geq 1$.

For case 2 we cover the cases $s=0$.

Case 2a: $r=1,s=0$ any $t$

We have $$ \varphi(2^2) + \varphi(3^2) = 8 = \varphi((2^2)^2) $$ therefore $$ \varphi((2\cdot 5^tm)^2) + \varphi((3\cdot 5^tm)^2) = \varphi((2^2\cdot 5^tm)^2) $$

Case 2b: $r\geq 2,s=0,t=0$

Let $$ b = 2^{r+1}m ,\quad c = 2^{r-1}5m $$ Then $$ \begin{align} \varphi(a^2)+\varphi(b^2) &= \varphi((2^r m)^2) + \varphi((2^{r+1} m)^2)\\ &= 2^{2r-1}\varphi(m^2) + 2^{2r+1} \varphi(m^2) \\ &= 2^{2r-1}5 \varphi(m^2)\\ & = \varphi(2^{2r-2}\cdot 5^2m^2)\\ &= \varphi(c^2) \end{align} $$ Notice we needed $r\geq 2$ for equality 4.

Case 2c: $r\geq 2,s=0,t\geq 1$

Let $$ b = 2^{r+1}3^15^t m, \quad c = 2^r 5^{t+1}m $$ which gives $$ \begin{align} \varphi(a^2) + \varphi(b^2) &= \varphi(2^{2r}5^{2t}m^2) + \varphi(2^{2r+2} 3^2 5^{2t} m^2)\\ &= 2^{2r+1}5^{2t-1} \varphi(m^2) + 2^{2r+4}\cdot 3\cdot 5^{2t-1} \varphi(m^2)\\ &= (1 + 8\cdot 3)2^{2r+1}5^{2t-1}\varphi(m^2)\\ &= 2^{2r+1} 5^{2t+1} \varphi(m^2)\\ &= \varphi(2^{2r} 5^{2t+2} m^2)\\ &= \varphi(c^2) \end{align} $$ Observe that this would have worked with $r=1$ as well.

Hence we may now consider $r,s\geq 1$.

Solve the case of $t=0$ first:

Case 3a: $r,s\geq 1, t=0$

Let $$ b = 2^{r+1}3^s5^1 m,\quad c= 2^r 3^{s+2}m $$ and we verify that $$ \begin{align} \varphi(a^2) + \varphi(b^2) &= \varphi(2^{2r}3^{2s}m^2) + \varphi(2^{2r+2}3^{2s}5^2m^2)\\ &= 2^{2r}3^{2s-1}\varphi(m^2) + 2^{2r+4}3^{2s-1}5\varphi(m^2)\\ &= (1 + 2^4\cdot 5)2^{2r}3^{2s-1}\varphi(m^2)\\ &= 2^{2r} 3^{2s+3} \varphi(m^2)\\ &= \varphi(2^{2r} 3^{2s+4}m^2)\\ &= \varphi(c^2) \end{align} $$

This leaves the case of $r,s,t\geq 1$. We first eliminate the cases of $r\geq 3$.

Case 3b: $r\geq 3,s,t\geq 1$

This can be seen directly from $$ \begin{align} \varphi((2^{r}3^{s}5^{t}m)^2) + \varphi((2^{r-2}3^{s+1} 5^t m)^2 &= \varphi(2^{2r} 3^{2s} 5^{2t} m^2) + \varphi(2^{2r-4} 3^{2s+2} 5^{2t} m^2)\\ &= 2^{2r+2} 3^{2s-1} 5^{2t-1} \varphi(m^2) + 2^{2r-2} 3^{2s+1} 5^{2t-1} \varphi(m^2)\\ &= (2^4 + 3^2)2^{2r-2}3^{2s-1} 5^{2t-1} \varphi(m^2)\\ &= 2^{2r-2}3^{2s-1} 5^{2t+1} \varphi(m^2)\\ &= \varphi( 2^{2r-4} 3^{2s} 5^{2t+2} m^2)\\ &= \varphi( (2^{r-2} 3^s 5^{t+1} m)^2 ) \end{align} $$ The condition $r\geq 3$ is used in equality 2, for computing exponents of prime $2$.

We are left with the cases $r\in \{1,2\}$ and $s,t\geq 1$.

Case 3c: $r=2$ and $s,t\geq 1$

Let $$ b = 3^s 5^t m,\quad c = 3^{s+1} 5^t m $$ Then $$ \begin{align} \varphi(a^2) + \varphi(b^2) &= \varphi(2^4 3^{2s} 5^{2t}m^2) + \varphi(3^{2s} 5^{2t} m^2)\\ &= 2^6 3^{2s-1} 5^{2t-1} \varphi(m^2) + 2^3 3^{2s-1} 5^{2t-1} \varphi(m^2)\\ &= (2^3+1) 2^3 3^{2s-1}5^{2t-1} \varphi(m^2)\\ &= 2^3 3^{2s+1} 5^{2t-1} \varphi(m^2)\\ &= \varphi( 3^{2s+2} 5^{2t} m^2)\\ &= \varphi(c^2) \end{align} $$

Finally, we investigate the case of $r=1$. When $s\geq 2$ we still have a solution:

Case 3d: $r=1, s\geq 2$ and $t\geq 1$

Let $$ b = 2^{3} 3^{s-1} 5^t m, \quad c = 2^1 3^{s-1} 5^{t+1} m $$ and we check that $$ \begin{align} \varphi(a^2) + \varphi(b^2) &= \varphi( 2^{2} 3^{2s} 5^{2t} m^2) + \varphi( 2^{6} 3^{2s-2} 5^{2t} m^2)\\ &= 2^{4} 3^{2s-1} 5^{2t-1} \varphi(m^2) + 2^{8} 3^{2s-3} 5^{2t-1} \varphi(m^2)\\ &= (3^2 + 2^4)2^{4} 3^{2s-3} 5^{2t-1} \varphi(m^2)\\ &= 2^{4} 3^{2s-3} 5^{2t+1} \varphi(m^2)\\ &= \varphi( 2^{2} 3^{2s-2} 5^{2t+2} m^2 )\\ &= \varphi(c^2) \end{align} $$

However in the final case of $r=1,s=1$, we only have solution for $t=1$

Case 3e: $r=1,s=1,t=1$

This can be seen directly from $$ \begin{align} \varphi((2^1 3^s 5^1 m)^2) + \varphi( (2^3 3^s m)^2 ) &= \varphi( 2^2 3^{2s} 5^{2} m^2) + \varphi( 2^6 3^{2s} m^2)\\ &= 2^4 3^{2s-1} 5^1 \varphi(m^2) + 2^6 3^{2s-1} \varphi(m^2)\\ &= (5 + 2^2)2^4 3^{2s-1} \varphi(m^2)\\ &= 2^4 3^{2s+1} \varphi(m^2)\\ &= \varphi( 2^4 3^{2s+2} m^2) \\ &= \varphi( (2^2 3^{s+1} m)^2 ) \end{align} $$

The unsolved case is $r=1,s=1$ and $t\geq 2$, which we handle next.

Case 4: $r=1,s=1,t\geq 2$

Let $u$ be the exponent of the prime factor $7$ of $a$. i.e. $$ a = 2^1 3^1 5^t 7^u n $$

If $u=0$, we set $$ b = 5^t 7^1 n,\quad c = 3^2 5^t n $$ so that $$ \begin{align} \varphi(a^2)+\varphi(b^2) &= 48\cdot 5^{2t-1}\varphi(n^2) + 168\cdot 5^{2t-1} \varphi(n^2)\\ &= 2\cdot 3^3 \cdot 4\cdot 5^{2t-1} \varphi(n^2)\\ &= \varphi(3^4 5^{2t} n^2)\\ &= \varphi(c^2) \end{align} $$

For $u=1$, we set $$ b = 2^2 5^t n,\quad c = 2^5 5^t n $$ Checking: $$ \begin{align} \varphi(a^2) + \varphi(b^2) &= \varphi(2^2 3^2 5^{2t} 7^2 n^2) + \varphi( 2^4 5^{2t} n^2)\\ &= 2^5 3^2 5^{2t-1} 7^1 \varphi(n^2) + 2^5 5^{2t-1}\varphi( n^2)\\ &= (3^2 7^1 + 1) 2^5 5^{2t-1} \varphi(n^2)\\ &= 2^{11} 5^{2t-1} \varphi(n^2)\\ &= \varphi( 2^{10} 5^{2t} n^2)\\ &= \varphi(c^2) \end{align} $$

Finally, for the last case of $u\geq 2$, we can set $$ b = 2^4 3^2 5^t 7^{u-1} n,\quad c = 2^1 3^1 5^{t+2} 7^{u-1} n $$ Checking: $$ \begin{align} \varphi(a^2) + \varphi(b^2) &= \varphi(2^2 3^2 5^{2t} 7^{2u} n^2) + \varphi( 2^8 3^4 5^{2t} 7^{2u-2} n^2)\\ &= 2^5 3^2 5^{2t-1} 7^{2u-1} \varphi(n^2) + 2^{11} 3^{4} 5^{2t-1} 7^{2u-3} \varphi(n^2)\\ &= (7^2 + 2^6 3^2) 2^5 3^2 5^{2t-1} 7^{2u-3} \varphi(n^2)\\ &= (625) 2^5 3^2 5^{2t-1} 7^{2u-3} \varphi(n^2)\\ &= 2^5 3^2 5^{2t+3} 7^{2u-3} \varphi(n^2)\\ &= \varphi( 2^2 3^2 5^{2t+4} 7^{2u-2} n^2)\\ &= \varphi(c^2) \end{align} $$