# gcd and lcm from prime factorization proof [closed]

How should I approach obvious proofs like these

I have been trying but couldn't find an elegant way to work these. Any help is highly appreciated ! Especially looking for a nice proof/hint for first problem

• I don't think that this question is a good fit for the site as written, but: Try using proof by contradiction for the first problem. Aug 20, 2014 at 22:56
• so is this site not useful in getting help in number theory questions related to proofs ? Aug 21, 2014 at 14:37
• It is a great place for number theory questions and proof help, but we have specific guidelines. Specific to your question, you're asking too broad of a question - each of the numbered items should be a separate question. Also, we want to hear your attempts. The question could be edited into a good fit, but not as it stands now. Aug 21, 2014 at 16:39
• If you had spent little time reading the question and paid some attention to the details, you would have seen that the question was specific and if you don't get the question yet, here is your second chance : How to work the first question so that the results will be useful to work remaining 3 questions. The other users who have answered understood the point of question but clearly you have rushed too quickly >.< Aug 21, 2014 at 16:56

Let $a=p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ and $b=p_{1}^{b_{1}}\cdots p_{r}^{b_{r}}$; then it is easy to verify that $a\vert b \iff a_{i}\le b_{i}$ for $1\le i\le r$ using the Fundamental Theorem of Arithmetic.

$\textbf{1)}$ $\;\;$If $d\vert m$ and $d\vert n$, it follows that $d=p_{1}^{d_{1}}\cdots p_{r}^{d_{r}}$ with $d_{i}\le k_{i}$ and $d_{i}\le j_{i}$ for $1\le i\le r$, so $\hspace{3.6 in}$ $d_{i}\le\min(k_{i}, j_{i})$ for $1\le i\le r$.

Therefore $\gcd(m,n)=p_{1}^{u_{1}}\cdots p_{r}^{u_{r}}$ where $u_{i}=\min(k_{i},j_{i})$ for $1\le i\le r$.

$\textbf{2)}$ $\;\;$ If $m\vert l$ and $n\vert l$, it follows that $l=p_{1}^{l_{1}}\cdots p_{r}^{l_{r}}p_{r+1}^{l_{r+1}}\cdots p_{s}^{l_{s}}$ with $k_{i}\le l_{i}$ and $j_{i}\le l_{i}$ for $1\le i\le r$, so $\hspace{3.6 in}$ $l_{i}\ge\max(k_{i}, j_{i})$ for $1\le i\le r$.

Therefore ${\rm lcm}(m,n)=p_{1}^{v_{1}}\cdots p_{r}^{v_{r}}$ where $v_{i}=\max(k_{i},j_{i})$ for $1\le i\le r$.

• thanks a lot ! i have worked #3 similar way : $\gcd(m,n)\times lcm(m,n) = p_i^{min\{k_i,j_i\}}\times p_i^{max\{k_i,j_i\}} = p_i^{min\{k_i,j_i\} + min\{k_i,j_i\}} = p_i^{k_i+j_i} = p_i^{k_i}\times p_i^{j_i} = m\times n$ does this look good ? xD Aug 21, 2014 at 14:43
• Yes, this looks fine (if you put in product signs in front of the primes, where i goes from 1 to r, or just write out the products). Aug 21, 2014 at 17:13
• I'll fix it, thank you so much for checking :) Aug 21, 2014 at 17:16
• You're welcome. Aug 21, 2014 at 17:49

Hint  Let $$\, (x,y) := \gcd(x,y),\, \ [x,y] := { \rm lcm}(x,y).\,$$ Via (unique) prime factorizations of $$\,x,y,\,$$ we can $$\rm\color{#0a0}{recursively}$$ compute gcd & lcm one-prime-power at at time as below, where $$\,p\nmid a,b$$

\begin{align}\rm (ap^J,bp^{J+K}) &\rm = (a,bp^K)p^J = \rm\color{#0a0}{(a,b)}p^{\color{#c00}J},\ \ \ \ \ \ \text{[gcd = \:\!\rm \color{#c00}{min}\:\! of expts]}\\[.4em] \rm [\:\!ap^J,bp^{J+K}]\:\! &\rm = [\:\!a,bp^K\:\!]\:\!p^J = \rm\color{#0a0}{[\:\!a,b\:\!]}\:\!p^{\color{#90f}{J+K}},\ \ \text{[lcm = \rm\color{#90f}{max} of expts]}\end{align}\qquad

• thank you :) just a quick question : $\ (ap^j,bp^k) = (a,b)(p^j,p^k)$ does this mean $\gcd(ab, cd) = \gcd(a,c)*\gcd(b,d)$ if $p \not | a,b$ ? Aug 20, 2014 at 22:30
• @rsadhvika It is true in the special case used above since if $\,p\nmid a,b,c\,$ then $\,cp^i\mid ap^j,bp^k\iff c\mid a,b,\,\ p^i\mid p^j,p^k\,$ by uniqueness of prime factorizations. Aug 20, 2014 at 22:53
• @rsadhvika Alternatively, if $\,j\le k\,$ then $\,(ap^j,bp^k) = p^j(a,bp^{k-j}) = p^j(a,b)\,$ by $\,(a,p)=1.\$ Aug 20, 2014 at 22:57
• got it completely, thank you so much xD Aug 21, 2014 at 14:39