Product of Two Integers Equals Product of Their GCD and LCM

গসাগু ও লসাগু এর একটি অত্যন্ত গুরুত্বপূর্ণ সম্পর্ক :

             দুইটি সংখ্যার গসাগু * সংখ্যা দুইটির লসাগু =সংখ্যা দুইটির গুণফল  

ধরি, দুইটি সংখ্যা হল $a$ ও $b$ । এদের গসাগু ও লসাগু কে যথাক্রমে গসাগু $(a,b)$ ও লসাগু $[a,b]$ লিখে প্রকাশ করা হল । এবার সম্পর্কটি প্রমাণের পালা । একটি অতি সহজ প্রমাণ এখানে উপস্থাপণ করা হল ।

সম্পর্কটির প্রমাণ :
ধরি, $a$ ও $b$ সংখ্যা দুটির গসাগু $k$ । তাহলে, এখান থেকে লেখা যায়, $a= ka'$ ................(১) $b= kb'$ ............... (২) ; যেখানে $(a', b') = 1$

লসাগুর সংজ্ঞা অনুসারে দেখা যায় , (১) ও (২) এর মধ্যে $k$ সাধারণ একবার, $a'$ সর্বোচ্চ একবার , $b'$ সর্বোচ্চ একবার আছে । সুতরাং, সংখ্যা দুইটির লসাগু হল $ka'b'$.

তাহলে, আমরা গসাগু আর লসাগু পেলাম যথাক্রমে  

$k$ & $ka'b'$ .
এবার , আমরা সম্পর্ক টি মেলানোর জন্য এই গসাগু আর লসাগু গুণ করে দিব । দেখতো কি হয় ? গুণফল টি থেকে আমরা কি বুঝতে পারি ? এই পর্যায়ে কিন্তু আমাদের প্রমাণ হয়ে গেছে । আসলে (১) ও (২) এ সংখ্যা দুইটির গুণফল এইটাই । তাহলে আমদের প্রমাণ শেষ হয়ে গেল ।
চল, এখন আমরা এটার প্রমাণটা একটু আনুষ্ঠানিক ভাবে লিখি ।

আনুষ্ঠানিক প্রমাণ ঃ $a$ & $b$ সংখ্যা দুটির গসাগু = $k$ । এখন, $a= ka'$ ও $b= kb'$ ।

বামপক্ষ = দুইটি সংখ্যার গসাগু $\times$ সংখ্যা দুইটির লসাগু $$\begin{equation} \begin{split} & = k \times ka'b'\\ & = k^2a'b' \\ & = ka' \times kb' \\ &= a \times b \end{split} \end{equation}$$ = সংখ্যা দুইটির গুণফল = **ডানপক্ষ ** [ প্রমাণিত ]

আরেকটি প্রমাণ । তবে এইটা কিছুটা জটিল মনে হতে পারে । এজন্য তোমাদের prime power factorization (ppf), lcm(লসাগু), gcd(গসাগু) সম্পর্কে ভালো ধারণা থাকতে হবে । এইটুকু জেনে রাখো, প্রতিটি সংখ্যাকেই একটি অনন্য উপায়ে মৌলিক সংখ্যার গুণফল আকারে লেখা যায় । নিম্নে প্রমাণ টি উল্লেখ করা হল ।

২য় প্রমাণ ঃ ধরি, সংখ্যা দুইটি হল A ও B . এখন, ppf অনুসারে,
$A$= $P_1^{a_1} \times .............. \times P_k^{a_k}$ &
$B$= $P_1^{b_1} \times .............. \times P_k^{b_k}$ যেখানে, $a_i$,$b_i$ $\ge$ 0 , $i$ = $1,................, k$
এখানে,
$গসাগু(A,B) \times লসাগু(A,B)$ = $P_1^{min(a_1,b_1)+max(a_1,b_1)} \times ............ \times P_k^{min(a_k,b_k)+max(a_k,b_k)}$
= $P_1^{a_1+b_1} \times .................. \times P_k^{a_k+b_k}$ = $A\times B$ ...........................[প্রমাণিত]

আসলে, এটার কোন নিশ্চিত উত্তর নাই ।কারণ, এই সম্পর্ক টি শুধুমাত্র দুইটা সংখ্যার ক্ষেত্রেই সঠিক । কিন্তু এর বেশি সংখ্যা হলে সম্পর্কটি সবসময় সঠিক হবে না ।

লসাগু ও গসাগু তে এই সম্পর্ক টি খুবই তাৎপর্যপূর্ণ । শুধু সম্পর্কটিই নয়, এর প্রমাণ প্রক্রিয়াটিও সমস্যা সমাধানে সহায়ক হতে পারে । সবাইকে অসংখ্য ধন্যবাদ ।।

There exists a theorem stating that for any two positive integers $a$ and $b$, the product of their greatest common factor (GCF) and their least common multiple (LCM) is equal to the product $ab$.

Proof of the theorem

We let $a = (2^{a_1}) \cdot (3^{a_2}) \cdot (5^{a_3}) \cdot (\cdots) \cdot (P^{a_n})$ and $b = (2^{b_1}) \cdot (3^{b_2}) \cdot (5^{b_3}) \cdot (\cdots )\cdot (P^{b_n})$, where $P$ is the greatest element of $\{ \text{prime numbers}\}\cap(\{\text{factors of } a\}\cup\{\text{factors of } b\})$, and $n$ is the index of $P$ in $\{\text{primes}\}$.

Lemma 1. The greatest common factor of $a$ and $b$ is $G=(2^{\min(a_1, b_1)}) \cdot (3^{\min(a_2, b_2)}) \cdot (5^{\min(a_3, b_3)}) \cdot (\cdots) * (P^{\min(a_n, b_n)})$. Proof of lemma 1. Obviously, by properties of exponents, $G$ divides both $a$ and $b$. Now, again by properties of exponents, $G$ is the greatest number that divides both $a$ and $b$ (since if you increment one power of one prime number, it will not be a factor of at least one of $a$ or $b$ (for that prime, say $p^*$, let the two powers be $r$ and $s$, where $r \le s$. Then we have that the power of $p^*$ in $p^* G$ is $r+1$, and then $p^* G$ does not divide the number where $r$ is the exponent of $p^*$. Thus we have defined the GCF of two numbers in terms of the numbers' prime factors. Lemma 2. The least common multiple of $a$ and $b$ is $L=(2^{\max(a_1, b_1)}) \cdot (3^{\max(a_2, b_2)}) \cdot (5^{\max(a_3, b_3)}) \cdot (\cdots) * (P^{\max(a_n, b_n)})$. Proof of lemma 2. Obviously, by properties of exponents, $L$ is a multiple of both $a$ and $b$. Now, again by properties of exponents, $L$ is the least(since if you decrement one power of one prime number, it will not be a multiple of at least one of $a$ or $b$ (for that prime, say $p^*$, let the two powers be $r$ and $s$, where $r \ge s$. Then we have that the power of $p^*$ in $G/p^*$ is $r-1$, and then $G/p^*$ is not a multiple of the number where $r$ is the exponent of $p^*$. Thus we have defined the LCM of two numbers in terms of the numbers' prime factors. Lemma 3. We have $\max(x, y) + \min(x, y) = x + y$. Proof of lemma 3. WLOG, assume $x \le y$. Then $x = \min(x,y)$ and $y=\max(x, y)$. The result follows by substitution. The actual proof. We consider $$ab = (2^{a_1 + b_1}) \cdot (3^{a_2 + b_2}) \cdot (5^{a_3 + b_3}) \cdot (\cdots) \cdot (P^{a_n + b_n})$$ and $$GL=(2^{\max(a_1, b_1)+\min(a_1, b_1)}) \cdot (3^{\max(a_2, b_2) + \min(a_2, b_2)}) \cdot (5^{\max(a_3, b_3) + \min(a_3, b_3)}) \cdot (\cdots) * (P^{\max(a_n, b_n) + \max(a_n, b_n)}).$$ By lemma 3, these two are equal. Thus we have $ab =$ GCF$(a,b)$LCM$(a,b).\text{ } \blacksquare$

We've used the gcd/lcm formula with prime factorisation and a fact that $\max \{ x,y \}+ \min \{ x,y \}=x+y$ to prove $\gcd (m,n) \cdot \text{lcm}(m,n)=mn$ (see Andrew Machkasov's proof in other explanation).

Can this be generalised? Is this following generalisation true?

Why then? Because we can't always have $$\max \{ m_1,m_2, \ldots, m_k \}+ \min \{ m_1,m_2, \ldots, m_l \}=m_1+m_2+ \ldots+m_k.$$ In fact, for $k \ge 3$, $LHS<RHS$. Since the case $k=2$ is special, that's why we have the beautiful identity $\gcd (m,n) \cdot \text{lcm}(m,n)=mn$.

Let us first consider the following: $gcd(a, b) = 1 \implies lcm(a, b) = a b$ $lcm(a c, b c) = c lcm(a, b)$ And lastly: $gcd(\frac{a}{gcd(a, b)}, \frac{b}{gcd(a, b)} ) = 1$

Why is it so? GCD indicates how much alike are the numbers (according to their prime factors). Dividing a number $a$ by its GCD with $b$ will result in number $c$ which is nothing like $b$, and so $GCD(c, b) = 1$. So the third identity may be easily understood.

Now the first identity is trivial: if numbers are nothing alike, then LCM must be their product.

The second formula interprets as follows: if there is something alike between numbers $a$ and $b$ then it must surely be a part of their LCM.

Invoking all of them: $lcm(a, b) = lcm(\frac{a gcd(a, b)}{gcd(a, b)}, \frac{b gcd(a, b)}{gcd(a, b)} ) =$ $gcd(a, b) lcm(\frac{a}{gcd(a, b)}, \frac{b}{gcd(a, b)} ) = gcd(a, b) \frac{a}{gcd(a, b)} \frac{b}{gcd(a, b)} = \frac{a b}{gcd(a, b)}$