1
$\begingroup$

How should I approach obvious proofs like these

enter image description here

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – apnorton
    Aug 20, 2014 at 22:56
  • 3
    $\begingroup$ so is this site not useful in getting help in number theory questions related to proofs ? $\endgroup$
    – AgentS
    Aug 21, 2014 at 14:37
  • $\begingroup$ 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. $\endgroup$
    – apnorton
    Aug 21, 2014 at 16:39
  • 2
    $\begingroup$ 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 >.< $\endgroup$
    – AgentS
    Aug 21, 2014 at 16:56

2 Answers 2

2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – AgentS
    Aug 21, 2014 at 14:43
  • $\begingroup$ 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). $\endgroup$
    – user84413
    Aug 21, 2014 at 17:13
  • $\begingroup$ I'll fix it, thank you so much for checking :) $\endgroup$
    – AgentS
    Aug 21, 2014 at 17:16
  • $\begingroup$ You're welcome. $\endgroup$
    – user84413
    Aug 21, 2014 at 17:49
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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$ ? $\endgroup$
    – AgentS
    Aug 20, 2014 at 22:30
  • $\begingroup$ @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. $\endgroup$ Aug 20, 2014 at 22:53
  • $\begingroup$ @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.\ $ $\endgroup$ Aug 20, 2014 at 22:57
  • $\begingroup$ got it completely, thank you so much xD $\endgroup$
    – AgentS
    Aug 21, 2014 at 14:39

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