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.)

elementary-number-theorynumber theorytotient-function

This question was inspired by the discussion in: Euler's totient function applied to higher power triples. Keith Backman suggested that perhaps there are many solutions to the following equation:

$$\phi(a^2)+\phi(b^2)=\phi(c^2) \tag{1}\label{1}$$

Without loss of generality I will assume $a \leq b$.

Is there a solution to $\eqref{1}$ with some $b$ and $c$ values, for any given value of a?

For example with $1 \leq a \leq 4$ there is are solutions:
$$\phi(1^2)+\phi(1^2)=\phi(2^2)$$
$$\phi(2^2)+\phi(3^2)=\phi(4^2)$$
$$\phi(3^2)+\phi(7^2)=\phi(12^2)$$
$$\phi(4^2)+\phi(6^2)=\phi(5^2)$$

I created a program and verified there is a solution for $1 \leq a \leq 8500$. And Peter's program verified up to $33000$. I expect that the answer to my question is yes, but I don't know how I would begin proving it.

Update

I've made some progress in proving it for some cases of $a$.

Case 1: $a$ is odd (Thanks to Peter's comment)

Let $b = a$ and $c = 2 a$

$$\phi(a^2)+\phi(a^2)=\phi((2a)^2)$$
$$2\phi(a^2)=\phi(4a^2)$$
Since $a$ does not contain a prime factor of $2$. It's totient can be calculated separately:
$$2\phi(a^2)=\phi(4)\phi(a^2)$$
$$2\phi(a^2)=2\phi(a^2)$$

$\square$

Case 2: $a$ contains at least two $2$'s and no $5$'s in its prime factorization

Let $b = 2a$ and $c = \frac{5}{2}a$.

Let $n$ be the number of $2$'s in the prime factorization of $a$.

Let $q$ be the prime factors of $a$ excluding all $2$'s which may be present.

Thus we can express $a$ as: $a = 2^nq$

$$\phi\lbrack(2^nq)^2\rbrack+\phi\lbrack(2\cdot2^nq)^2\rbrack=\phi\lbrack(\frac{5}{2}2^nq)^2\rbrack$$
$$\phi(2^{2n}q^2)+\phi(2^{2n+2}q^2)=\phi(5^2\cdot2^{2n-2}q^2)$$
Separate out the totient function because of the definition of $q$:
$$\phi(2^{2n})\phi(q^2)+\phi(2^{2n+2})\phi(q^2)=\phi(5^2)\phi(2^{2n-2})\phi(q^2)$$
$$\phi(2^{2n})+\phi(2^{2n+2})=\phi(5^2)\phi(2^{2n-2})$$
$$2^{2n-1}+2^{2n+1}=20\cdot2^{2n-3}$$
$$2^{2n-1}+2^{2n+1}=5\cdot2^{2n-1}$$
$$1+2^{2}=5$$

$\square$

Note where this proof would fail if $a$ was allowed to have a prime factor of $5$. If there were one $5$ in the prime factorization then in order to divide both sides by $\phi(q^2)$ the expression "$\phi(5^2 \cdot q^2)$" would become $25 \cdot \phi(q^2)$ instead of $20 \cdot \phi(q^2)$. This would force b to require a different multiplier, but this would just be a wild goose chase since another prime factor would not be allowed!

I found some alternate values of b and c that work for other cases (exactly one 2 in prime factor was one case), but nothing seems to come out cleanly because it just creates more restrictive cases.

Best Answer

(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} $$

Related Question