How to characterize pairs $(a,b) \in \mathbb N^2$ which satisfy this curious equation $\text{lcm}(a,b)-\text{gcd}(a,b)=\varphi(a \cdot b)$?

153 Views Asked by At

If $p$ is a prime then: $\text{lcm}(1,p)-\text{gcd}(1,p)=p-1=\varphi(1 \cdot p)$

How to characterize pairs $(a,b) \in \mathbb{N} \times \mathbb{N}$ which satisfy this curious equation?

This equation I posed by some investigation not much related to anything other than curiosity.

$\varphi$ is the totient-function.

1

There are 1 best solutions below

0
On

Assume that for some prime $p$, we have $p^2 \mid a$. Then, it is clear that $p^2 \mid ab \implies p \mid \varphi(ab)$. It is also clear from definition that $p \mid \text{lcm}(a,b)$. This shows: $$p \mid (\text{lcm}(a,b)-\varphi(ab)) \implies p \mid \gcd(a,b) \implies p \mid b$$

We have prime $p$ dividing both $a$ and $b$. Then: $$\nu_p(\text{lcm}(a,b)-\gcd(a,b))=\nu_p(\gcd(a,b))=\min(\nu_p(a),\nu_p(b)) $$ $$\nu_p(\varphi(ab))=\nu_p(\varphi(p^{\nu_p(a)+\nu_p(b)}s)) \geqslant \nu_p(a)+\nu_p(b)-1$$ from the canonical formula for the Euler Totient Function. This forces: $$\min(\nu_p(a),\nu_p(b)) \geqslant \nu_p(a)+\nu_p(b)-1$$ But we know that $\nu_p(a) \geqslant 2$. This shows: $$\nu_p(a)+\nu_p(b)-1>\nu_p(b)\geqslant \min(\nu_p(a),\nu_p(b))$$ which is a contradiction. This means that our initial assumption about the existence of $p$ such that $p^2 \mid a $ is false. This shows that $a$ is square-free. Similarly, we also have $b$ to be square-free.

Now, let $\{p_i \mid 1 \leqslant i \leqslant I\}$ be the set of primes dividing both $a$ and $b$, $\{q_j \mid 1 \leqslant j \leqslant J\}$ be the set of primes dividing $a$ alone, and $\{r_k \mid 1 \leqslant k \leqslant K\}$ be the set of primes dividing $b$ alone. These three sets have no primes in common with each other (pairwise intersection is $\varnothing$). Then: $$a=\prod p_i \prod q_j \quad ; \quad b=\prod p_i \prod r_k$$ $$\text{lcm}(a,b)-\gcd(a,b)=\prod p_i \prod q_j \prod r_k - \prod p_i = \prod p_i \bigg( \bigg( \prod q_j \prod r_k \bigg) -1\bigg)$$ $$\varphi(ab)=\varphi \bigg(\prod p_i^2 \prod q_j \prod r_k \bigg) = \prod p_i \prod (p_i-1) \prod (q_j-1) \prod (r_k-1)$$

Equating, we have: $$\text{lcm}(a,b)-\gcd(a,b)=\varphi(ab)$$ $$\prod p_i \bigg( \bigg( \prod q_j \prod r_k \bigg) -1\bigg)=\prod p_i \prod (p_i-1) \prod (q_j-1) \prod (r_k-1)$$ $$\bigg(\prod q_j \prod r_k \bigg) -1 = \prod (p_i-1) \prod (q_j-1) \prod (r_k-1)$$

Note that you have: $$x=\bigg(\prod q_j \prod r_k \bigg) \implies \varphi(x)=\prod (q_j-1) \prod (r_k-1)$$

This shows: $$x-1=\varphi(x) \cdot \prod (p_i-1) \implies \varphi(x) \mid (x-1)$$

Note that $\varphi(x) \mid (x-1)$ is Lehmer's Totient Problem. It is unknown whether there are any solutions except prime $x$. Knowing that the quotient is expressable as $\prod (p_i-1)$ doesn't help.

Let us assume that the only solutions to Lehmer's Totient Problem are prime $x$. Then: $$\phi(x)=x-1 \implies \prod (p_i-1)=1$$

This is only possible when there is only one prime in the product ($I=1$) which must be $2$, or when there are no primes in the product ($I=0$), which gives null product as $1$. This corresponds to the solutions $(1,p)$ for all primes $p$ and $(2,2q)$ for odd primes $q$. Hence, assuming that Lehmer's Totient Problem has only prime solutions, these are the only possible pairs of solutions:

$$(a,b)=(1,p),(p,1),(2,2q),(2q,2) \quad ( p,q \in \mathbb{P} \space ; \space q \neq 2)$$

Lehmer's Totient Problem: https://mathworld.wolfram.com/LehmersTotientProblem.html