# Is $\phi(ab)\ge\phi(a)\cdot \phi(b)$ true for every positive integer pair $(a/b)$?

If $\phi(n)$ is the totient-function, does $$\phi(ab)\ge \phi(a)\cdot \phi(b)$$ hold for every pair $(a,b)$ of positive integers ? And does equality hold if and only if $\gcd(a,b)=1$ ?

I defined $$g:=\gcd(a,b)$$ $$a':=\frac{a}{g}$$ $$b':=\frac{b}{g}$$ and tried to reduce the problem to the $a'$ and $b'$, but this approach led to nowhere.

• This statement would be useful to solve this : math.stackexchange.com/questions/2488373/… – Peter Oct 25 '17 at 10:37
• I don't understand the claim "...and all those numbers are coprime to $ab$". If $a=2$, $b=6$ then, in your notation, $g=2,a'=1,b'=3$, yes? $2$ is a number smaller than $a'b'$ which is coprime to $a'b'$ but $2$ is not coprime to $ab$. Am I misreading? – lulu Oct 25 '17 at 10:54
• I believe that if you write $a=\prod p_i^{a_i}\times \prod q_j^{\alpha_j}$ and $b=\prod p_i^{b_i}\times \prod r_k^{\beta_k}$ where the $p_i$ are the primes dividing $\gcd (a,b)$ and the $q_j,r_k$ are primes distinct from each other and from the $p_i$ you can then write down both sides to see the inequality you desire. (the left has terms like $p_i^{a_i+b_i-1}$ the right has $p_i^{a_i+b_i-2}$). – lulu Oct 25 '17 at 10:57
• I don't see how the edit eliminated the counterexample I gave. The co-primality of the factors seems difficult to sort out, though I expect you can break it into cases. The explicit calculation I sketched, while somewhat unsatisfactory, handles this. – lulu Oct 25 '17 at 11:11
• I expect some variant of your argument will work. Like I said, I find the explicit computation somewhat unsatisfying...presumably there is an enumerative method that establishes what you want. At the moment, however, I am not seeing it. – lulu Oct 25 '17 at 11:15

Yes.

Using the formula $\phi(ab)=\phi(a)\phi(b)\frac{\gcd(a,b)}{\phi(\gcd(a,b))}$, we can see that $$\phi(ab) \geq \phi(a)\phi(b) \iff \frac{\gcd(a,b)}{\phi(\gcd(a,b))}\geq1$$ Denoting $c=\gcd(a,b)$, we just need to prove $c\geq \phi(c)$. However, this is always true, since $\phi(n)$ counts the number of positive integers up to $n$ relatively prime time to $n$, which can't ever be greater than $n$. We can also see the only solution to $c=\phi(c)$ is $c=1$, so we have $\phi(ab)=\phi(a)\phi(b) \iff \gcd(a,b) =1$.

• A useful formula! (+1 and accept) – Peter Oct 25 '17 at 13:22

Let $\{p_i\}$ be the list of primes dividing $\gcd (a,b)$. Then we can write $$a=\prod p_i^{a_i}\times \prod q_j^{\alpha_j}\quad \&\quad b=\prod p_i^{b_i}\times \prod r_k^{\beta_k}$$

Where the $q_j,r_k$ are primes disjoint from each other and from the $p_i$.

We can now compute both sides of your desired inequality. We get $$\varphi(ab)=\prod p_i^{a_i+b_i-1}(p_i-1)\times \varphi\left(\prod q_j^{\alpha_j}\right)\times \varphi\left(\prod r_k^{\beta_k}\right)$$ While $$\varphi(a)\varphi(b)=\prod p_i^{a_i+b_i-2}(p_i-1)^2\times \varphi\left(\prod q_j^{\alpha_j}\right)\times \varphi\left(\prod r_k^{\beta_k}\right)$$

From this we see that we can compute the ratio $$\boxed {\frac {\varphi(ab)}{\varphi(a)\varphi(b)}=\prod \frac {p_i}{p_i-1}}$$

The inequality you desire follows at once (as well as the claim that equality requires the gcd to be $1$).

Examples:

I. $a=12, b=16$. Then the only $p_i$ is $2$ and we remark that $$\varphi(192)=64=2\times \varphi(12)\times \varphi(16)$$

II. $a=18,b=60$. Then the $p_i$ are $2,3$ and we have $$\frac {\varphi(18\times 60)}{\varphi(18)\times \varphi (60)}=3=\frac 21\times \frac 32$$

III. $a=10,b=45$. In this case the ratio comes out $\frac 54$ as desired (I've included this examples just to illustrate that, of course, the ratio need not always be an integer).

• Nice answer (+1) – Peter Oct 25 '17 at 13:21