3
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ Shouldn't the inequalities be flipped since the gcd is always smaller than or equal to the lcm? $\endgroup$
    – parafoo
    Nov 22, 2019 at 2:57
  • $\begingroup$ 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. $\endgroup$ Nov 22, 2019 at 3:03
  • $\begingroup$ ah true yes ill correct that $\endgroup$ Nov 22, 2019 at 4:13

1 Answer 1

4
$\begingroup$

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

As for your (2), i.e.,

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

$\endgroup$
2
  • $\begingroup$ With the counter example the condition of uniqueness wo't allow $a_1=a_2$ this would reduce the cardinality to $n=1$ $\endgroup$ Nov 22, 2019 at 4:20
  • $\begingroup$ I'm very sorry for not including that in my original post I am too tired to be posting questions but yes indeed your counter example for the original question is valid $\endgroup$ Nov 22, 2019 at 4:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .