# proof of inequality relation for the greatest common divisor and lowest common multiple and totient of a finite natural number set

I haven't gotten anywhere in establishing a proof for this yet, it is something that I worked on a while back, but I don't think it will be difficult considering how intimately related the three quantities are:

I had not been considering singltons, which do not conform as pointed out, so I apologize for having to make this edit now:

$${\{a_j}\}_{j=1..n} \subset \mathbb N \land n \gt 1 \tag 0$$ $$\gcd \Bigl({\{a_j}\}_{j=1..n}\Bigr) \lt n\,\varphi\Bigl(\sum^n_{j=1}a_j\Bigr) \lt \operatorname{lcm}\Bigl({\{a_j}\}_{j=1..n}\Bigr) \tag 1$$

Originally I had only stated the above as

$$\gcd \Bigl({\{a_j}\}_{j=1..n}\Bigr) \lt n\,\varphi\Bigl(\sum^n_{j=1}a_j\Bigr) \tag a$$

but for whatever reason added the other side which as shown by the answer provided is false.

$$\prod^{n}_{j=1}a_j= \gcd({\{a_j}\}_{j=1..n}) \cdot \operatorname{lcm}({\{a_j}\}_{j=1..n}) \operatorname{ if and only if} \,{\{a_j}\}_{j=1..n} \operatorname{is pairwise coprime} \tag 2$$

Where $$\varphi$$ is the Euler totient function.

But yeah I guess hints are probably what I am looking for seeing I don't see why I cant do this myself

edit 23/11/2019:

another inequality similar to $$(a)$$ holds:

$$\gcd \Bigl({\{a_j}\}_{j=1..n}\Bigr) \lt n\,\varphi\Bigl(\prod^n_{j=1}a_j\Bigr) \tag b$$

• Shouldn't the inequalities be flipped since the gcd is always smaller than or equal to the lcm? Nov 22, 2019 at 2:57
• Note for the last quantity, the left side is always true for $n = 2$, such as shown at Proving gcd($a,b$)lcm($a,b$) = $|ab|$, regardless of whether or not the $2$ values are coprime. Nov 22, 2019 at 3:03
• ah true yes ill correct that Nov 22, 2019 at 4:13

You state for your (1) that

$$\operatorname{lcm}\Bigl({\{a_j}\}_{j=1..n}\Bigr) \lt n\,\varphi\Bigl(\sum^n_{j=1}a_j\Bigr) \lt \gcd \Bigl({\{a_j}\}_{j=1..n}\Bigr) \tag{1}\label{eq1A}$$

However, I agree with parafoo's question comment that suggests you meant to flip the inequalities around, as $$\gcd$$ is always less than or equal to the $$\text{lcm}$$. However, even with this change, \eqref{eq1A} is not always true. For example, for the left part, consider $$n = 2$$, with $$a_1 = 2$$ and $$a_2 = 11$$. Then $$\operatorname{lcm}\Bigl({\{a_j}\}_{j=1..n}\Bigr) = 22$$, but $$n\,\varphi\Bigl(\sum^n_{j=1}a_j\Bigr) = 2\varphi(13) = 2(12) = 24$$.

With the right part, consider $$n = 2$$ again, with $$a_1 = a_2 = 210$$. In this case, $$n\,\varphi\Bigl(\sum^n_{j=1}a_j\Bigr) = 2\varphi(240) = 2\left(\frac{240(1)(2)(4)(6)}{2(3)(5)(7)}\right) = 192$$, but $$\gcd \Bigl({\{a_j}\}_{j=1..n}\Bigr) = 210$$.

$$\prod^{n}_{j=1}a_j= \gcd({\{a_j}\}_{j=1..n}) \cdot \operatorname{lcm}({\{a_j}\}_{j=1..n}) \operatorname{ if and only if} \,{\{a_j}\}_{j=1..n} \operatorname{is pairwise coprime} \tag{2}\label{eq2A}$$
as I stated in my question comment, this is always true for $$n = 2$$, such as shown at Proving gcd($$a,b$$)lcm($$a,b$$) = $$|ab|$$, regardless of whether or not the $$2$$ values are coprime. As such, consider $$n \ge 3$$. With that restriction, \eqref{eq2A} then always holds. To see this, consider the set of all prime factors used among the $$a_j$$ is $$p_i$$ for $$1 \le i \le m$$ for some $$m \ge 0$$. Next, have
$$a_j = \prod_{i=1}^{m} p_i^{e_{i,j}}, \; e_{i,j} \ge 0 \tag{3}\label{eq3A}$$
For any given $$1 \le i \le m$$, the power of $$p_i$$ in the product of all $$a_j$$ for $$1 \le j \le n$$ would be the sum of all of the $$e_{i,j}$$, in the $$\gcd$$ would be the minimum among all of the $$e_{i,j}$$, and in the $$\text{lcm}$$ would be the maximum among all of the $$e_{i,j}$$. The sum of all the values cannot be equal to the sum of the minimum & maximum if there are $$3$$ or more positive values among the $$e_{i,j}$$. Thus, there must be at least $$1$$ value which is $$0$$, but then the minimum must be $$0$$, and there can only be one non-zero value, which is the maximum. This only occurs if all $$a_j$$ are pairwise coprime. On the other hand, if all $$a_j$$ are pairwise coprime, then the $$\gcd$$ of all of them would be $$1$$ and, as only $$1$$ $$a_j$$ value can contain any factor of $$p_i$$, the $$\text{lcm}$$ of all $$a_j$$ would be the product of them.
• With the counter example the condition of uniqueness wo't allow $a_1=a_2$ this would reduce the cardinality to $n=1$ Nov 22, 2019 at 4:20