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

• Maybe $$\varphi(n^2)=n\cdot \varphi(n)$$ is helpful to prove the conjecture. – Peter Sep 21 '18 at 19:11
• If $a$ is odd , then $b=a$ and $c=2a$ does the job : $$\varphi(a^2)+\varphi(a^2)=2\varphi(a^2)=2a\varphi(a)=2a\varphi(2a)=\varphi((2a)^2)$$ – Peter Sep 22 '18 at 8:31
• The claim is true upto $a=33\ 000$ – Peter Sep 22 '18 at 13:29

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

• Good answer, I was afraid there were going to be a lot of cases going my method, but at least it's proven now. – jwc845 Sep 26 '18 at 0:08
• @jwc845 Yeah it seems quite difficult to cut down on the number of cases for this type of approach. Using two primes $p,q$ it looks like even simple cases like $a=pq$ has no solutions, while using three quickly complicates matters. Perhaps there are better approaches. – Yong Hao Ng Sep 26 '18 at 2:23
• It also looks like a solution always exist where b and c are integer multiples of a. This didn't necessarily have to be the case (my partial proof had a $\frac{5}{2}$ multiplier), but I guess it makes sense. Still good work even if it's not necessarily elegant. – jwc845 Sep 26 '18 at 2:28