1
$\begingroup$

Find three distinct positive integers $x,y,z$ such that $xyz=\text15\cdot{lcm}(x,y,z)\cdot \gcd(x,y,z)$

I've proved this for two numbers $x$ and $y$, but I'm not sure how to expand this to three numbers or even to $n$ numbers

$\endgroup$
  • $\begingroup$ This may help somewhat: GCD to LCM of multiple numbers $\endgroup$ – dxiv Oct 8 '16 at 19:08
  • $\begingroup$ Formatting tips here. $\endgroup$ – Em. Oct 8 '16 at 19:10
  • $\begingroup$ Can you solve the problem with $3$ instead of $15$? (Hint: you can do so using only powers of $3$.) What about $5$ instead of $15$? Can you combine those two solutions somehow? $\endgroup$ – Greg Martin Oct 8 '16 at 19:14
  • $\begingroup$ Is coefficient $15$ at the LHS? not in the RHS? Simply, if $x=\prod_j p_j^{a_j}, y =\prod_j p_j^{b_j}, z=\prod_j p_j^{c_j}$, then $$lcm(x,y,z)=\prod p_j^{\max\{a_j,b_j,c_j\}},$$ $$gcd(x,y,z)=\prod p_j^{\min\{a_j,b_j,c_j\}},$$ and $$\max\{a,b,c\}+\min\{a,b,c\}\le a+b+c$$ for non-negative $a,b,c$. $\endgroup$ – Oleg567 Oct 8 '16 at 19:26
  • $\begingroup$ @Oleg567 It is on left hand side... And can you simplify the symbols down a bit? I'm in 7th grade lol $\endgroup$ – Gerard L. Oct 8 '16 at 19:30
1
$\begingroup$

Consider example, which will show that $xyz\ge lcm(x,y,z)\cdot gcm(x,y,z)$ .

Let $x=24$, $y=50$, $z=70$.

Then consider prime factorization of these numbers:

\begin{array}{|c|c|c|c|c|c|} \hline number & 2 & 3 & 5 & 7 \\ \hline x & 2^3 & 3 & - & - \\ y & 2 & - & 5^2 & - \\ x & 2 & - & 5 & 7 \\ \hline gcd(x,y,z) & 2 & - & - & - \\ \hline lcm(x,y,z) & 2^3 & 3 & 5^2 &7 \\ \hline xyz & 2^3\cdot 2 \cdot 2 & 3 & 5^2\cdot 5 & 7 \\ \hline \end{array}

GCD collects smallest powers of each prime.

LCM collects largest powers of each prime.

So, if consider any prime number $p$, then

$$x = p^a \cdot x_1,$$ $$y = p^b \cdot y_1,$$ $$z = p^c \cdot z_1,$$ where $a\ge 0, b\ge 0, c\ge 0$; then $$gcd(x,y,z) = p^{\min\{a,b,c\}}g_1;$$ $$lcm(x,y,z) = p^{\max\{a,b,c\}}l_1;$$ $$xyz = p^{a+b+c}m_1,$$ where $x_1,y_1,z_1$, $g_1$, $l_1$ and $m_1$ are not divisible by $p$.

But $a+b+c\ge \min\{a,b,c\}+\max\{a+b+c\}$. Since $a+b+c = \min\{a,b,c\}+medium\{a,b,c\}+\max\{a,b,c\}.$

And such property $-$ for each prime number from the table.


If $15$ would be on RHS, then one can construct such $(x,y,z)$: $(3,5,15)$, $(5,15,30)$ for example.

How to find such triples? Let $$x=2^{a_1}\cdot 3^{a_2}\cdot 5^{a_3}\cdot 7^{a_4}\cdot \ldots;$$ $$y=2^{b_1}\cdot 3^{b_2}\cdot 5^{b_3}\cdot 7^{b_4}\cdot \ldots;$$ $$z=2^{c_1}\cdot 3^{c_2}\cdot 5^{c_3}\cdot 7^{c_4}\cdot \ldots;$$ where $a_1,b_1,...,c_4, ...$ $-$ all numbers are non-negative integer numbers.

Then $$xyz = 2^{a_1+b_1+c_1}\cdot 3^{a_2+b_2+c_2}\cdot 5^{a_3+b_3+c_3}\cdot 7^{a_4+b_4+c_4}\cdot \ldots;$$ $$ gcd(x,y,z)\cdot lcm(x,y,z) = 2^{\min\{a_1,b_1,c_1\}+\max\{a_1,b_1,c_1\}}\\ \times 3^{\min\{a_2,b_2,c_2\}+\max\{a_2,b_2,c_2\}}\\ \times 5^{\min\{a_3,b_3,c_3\}+\max\{a_3,b_3,c_3\}}\\ \times 7^{\min\{a_4,b_4,c_4\}+\max\{a_4,b_4,c_4\}}\\ \times \ldots; $$ Since there is $15=3\cdot 5$ near $gcd\cdot lcm$, then looking at powers of $2$, then at powers of $3$ etc, we conclude: $$ \left\{ \begin{array}{l} a_1+b_1+c_1 = \min\{a_1,b_1,c_1\} + \max\{a_1,b_1,c_1\}; \\ a_2+b_2+c_2 = \min\{a_2,b_2,c_2\} + \max\{a_2,b_2,c_2\} \large{+ 1}; \\ a_3+b_3+c_3 = \min\{a_3,b_3,c_3\} + \max\{a_3,b_3,c_3\} \large{+ 1}; \\ a_4+b_4+c_4 = \min\{a_4,b_4,c_4\} + \max\{a_4,b_4,c_4\}; \\ \ldots \end{array} \right. $$ from this point we conclude that:

  • medium number of $a_1,b_1,c_1$ is $0$ (then the smallest is $0$ too);
  • medium number of $a_2,b_2,c_2$ is $1$ (then the smallest is $0$ or $1$);
  • medium number of $a_3,b_3,c_3$ is $1$ (then the smallest is $0$ or $1$);
  • medium number of $a_4,b_4,c_4$ is $0$ (then the smallest is $0$ too);
  • ...

Let us construct such sets of powers:
$a_1=0,b_1=3,c_1=0$; (smallest is $0$, medium is $0$, largest is $3$)
$a_2=1,b_2=2,c_2=0$; (smallest is $0$, medium is $1$, largest is $2$)
$a_3=2,b_3=1,c_3=1$; (smallest is $1$, medium is $1$, largest is $2$)
$a_4=1,b_4=0,c_4=0$; (smallest is $0$, medium is $0$, largest is $1$)
and let other primes have powers $0$ (for simplicity);

and finally compose $x,y,z$:

$x=2^{a_1}\cdot 3^{a_2}\cdot 5^{a_3}\cdot 7^{a_4} = 2^0\cdot 3^1\cdot 5^2\cdot 7^1 = 525$;

$y=2^{b_1}\cdot 3^{b_2}\cdot 5^{b_3}\cdot 7^{b_4} = 2^3\cdot 3^2\cdot 5^1\cdot 7^0 = 360$;

$z=2^{c_1}\cdot 3^{c_2}\cdot 5^{c_3}\cdot 7^{c_4} = 2^0\cdot 3^0\cdot 5^1\cdot 7^0 = 5$;

$gcd(x,y,z) = 5$, $lcm(x,y,z)=12\:600$, $xyz=945\:000$,
$945\:000 = 15\cdot 5 \cdot 12\:600$.

Just for training: reproduce this construction for getting triple $x=3,y=5,z=15$, or other one: $x=5,y=15,z=30$.

$\endgroup$
  • $\begingroup$ What do the g1, l1, and m1 mean? and by medium do you mean the median? $\endgroup$ – Gerard L. Oct 8 '16 at 20:37
  • $\begingroup$ $g_1$ is part of $gcd(...)$-factorization which is not divisible by $p$; in fact, $g_1 = gcd(x_1,y_1,z_1)$. $l_1 -$ similar. For this example, and for $p=2$ we'll have $g_1=1$, $l_1=3\cdot 5^2\cdot 7$. $\endgroup$ – Oleg567 Oct 8 '16 at 20:40
  • $\begingroup$ wait up the 15 is on rhs sry my teacher made typo. Proof for that? $\endgroup$ – Gerard L. Oct 11 '16 at 18:57
  • $\begingroup$ @Gerard, I updated answer with description of solution construction. $\endgroup$ – Oleg567 Oct 11 '16 at 21:58

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.