1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This statement would be useful to solve this : math.stackexchange.com/questions/2488373/… $\endgroup$ – Peter Oct 25 '17 at 10:37
  • $\begingroup$ 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? $\endgroup$ – lulu Oct 25 '17 at 10:54
  • 1
    $\begingroup$ 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}$). $\endgroup$ – lulu Oct 25 '17 at 10:57
  • $\begingroup$ 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. $\endgroup$ – lulu Oct 25 '17 at 11:11
  • 1
    $\begingroup$ 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. $\endgroup$ – lulu Oct 25 '17 at 11:15
2
$\begingroup$

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

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

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

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

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.