Is there any alternate proof for proving that  The product of L.C.M (Least Common Multiple) and G.C.D (Greatest Common Divisor) of any two positive integers = the product of those two integers   ?  As of now, there exists a proof which involves use of Number Theory based facts.   I am interested to know if there exists any alternate proof (perhaps in different branch of Mathematics ?!).  You can assume that you want to prove this fact to a person who is aware of basics of mathematics but not NUMBER THEORY
124083
Let $a$ and $b$ be two integers. Prove that  $$ dm = \left|ab\right| ,$$ where $d = \gcd\left(a,b\right)$ and $m = \operatorname{lcm}\left(a,b\right)$.   So I went about by saying that $a = p_1p_2...p_n$ where each $p_n$ is a prime. Same applies to $b = q_1q_2 ... q_c$. So then $m = (u_1u_2...)(p_1p_2...p_n)$ and $m = (t_1t_2...)(q_1q_2...q_c)$ since $a|m$ and $b|m$. $m$ has a unique factorization, so the primes $(u_1u_2...)(p_1p_2...p_n) = (t_1t_2...)(q_1q_2...q_n)$ and the gcd(a,b) = $(p_1p_2...p_n) \cap (q_1q_2...q_n)$ (I know this is not mathematically correct, so is there a correct way to express this?).   So $dm = |ab| \iff d= \frac{|ab|}{m}$. And by the definition above, $\frac{ab}{(t_1t_2...)b} = \frac{a}{(t_1t_2...)}$. And this is where I get stuck. Is my proof right? Am I going in the right direction?  Thanks   PS. I am trying to do this using only the prime factorization theorem and the definitions of the gcd and the lcm.
49507
I would appreciate hints to this. I've done part (a) but am unconfident. Wondering how I could approach part (b)    Question's comment -- The aim of this question is to use the Division Algorithm and the definition of greatest common divisor (gcd) to show that $d_0 = \gcd(a,b)$.    Question:  Let $a,b$ be integers, not both zero, let $S$ be the set of integers defined by $$S = \{ ax + by | x,y \in \mathbb{Z}\}$$ and let $d_0$ be the smallest positive integer in the set $S$. Prove: a. If $s\in S$, then $d_0$ is a divisor of $s$. b. $d_0$ is a divisor of both $a$ and $b$. c. If $d$ is a divisor of both $a$ and $b$, then $d$ is a divisor of $d_0$. d. $d_0 =\gcd(a,b),$ and hence there exists integers $x,y$ such that $ax + by = \gcd(a,b)$.    Attempt:  Note I don't expect full (or any hints to the problem(s) as there are quite a bit, but I would just appreciate hints. a. Let $s \in S$. Then $s = d_0 q + r$ for some $q,r \in \mathbb{Z}$. By definition, $d_0 = ax_0 + by_0$ for some $x_0,y_0 \in \mathbb{Z}$. $s = ax_s + by_s$ for some $x_s,y_s \in \mathbb{Z}$. Hence, $$ax_s + by_s = q(ax_0 + by_0) + r\\ a(x_s - qx_0) + b(y_s - qy_0) = r.$$ Define $x_r:= x_s - qx_0 \in \mathbb{Z}$ and $y_r:= y_s - qy_0 \in \mathbb{Z}$. Then this shows that $r \in S$ which implies $d_0 | s$.
44684
Let $R$ be a UFD. Then for any two elements $a,b \in R \setminus \{0\}$ $ab \sim \gcd (a,b){\operatorname{lcm} (a,b)}$.   My attempt :  Let $d = \gcd (a,b)$.Then $d|a$ and $d|b$.Then $\exists x,y \in R$ such that $a = dx$ and $b = dy$.Now it is to be shown that $c = dxy$ is the lcm of $a,b$.Which I find difficulty to show.It is clear that $a|c$ and $b|c$. Now if $u$ is any common multiple of $a$ and $b$.Then $dx|u$ and also since $y|b$ we have $y|u$ i.e. $dxy|u^2$ $\implies c|u^2$.But I have to show $c|u$ to complete the proof which I fail to prove.Please help me to complete the proof.  Thank you in advance.
27117
If $c$ is a common divisor of $a$ and $b$ then $c$ divides the greatest common divisor of $a$ and $b$.  What can we use to prove this?
77391
I honestly have no idea how to approach this question. I have done easier questions eg. show $gcd(a,b)lcm(a,b)=ab$ by letting $a=Alcm(a,b)$ and $b=Blcm(a,b)$ and then using the fact that $A$ and $B$ are coprime. However this approach only works in two variables. Any help with the question in the title would be greatly appreciated, as well as the thought process behind the answer so that I can approach similar problems.
66002
How would you show that if $ac≡bc$ $\mod m$ and $\gcd(c,m)=d$, then  $a≡b$ $\mod \frac{m}{d}$?  Any help would be much appreciated!
74242
I am trying to show that $\gcd(a,\operatorname{lcm}(b,c))=\operatorname{lcm}(\gcd(a,b),\gcd(a,c))$.  If $d=\gcd(a,\operatorname{lcm}(b,c))$, then $d=ax-my$, where $m=\operatorname{lcm}(b,c)$. So $d=ax-b(ky)$ and $d=ax-c(ly)$, which means that $\gcd(a,b)|d$ and $\gcd(a,c)|d$, or $d$ is a common multiple.  But I wasn't able to show that it is the smallest common multiple.
51653
Did not find this from this website...  If $$ \gcd(a,b)=1,$$ then there exists integers $x$ and $y$ such that $$xa+yb=1.$$  Now, the tip is to use particular corollary, that states:  The class $[m]_{n}$ generates $\mathbb{Z}/n\mathbb{Z}\Leftrightarrow \gcd(m,n)=1.$  I am totally lost with the corollary.  Let's assume that $\gcd(m,n)=1$. Then, $[m]_{n}$ generates $\mathbb{Z}/n\mathbb{Z}$.  OK! Then what?  There is also follow up, where I have to prove the converse. I am familiar with Bezout's lemma.
40178
Prove that if $\gcd(a,c)=1$ and $\gcd(b,c)=1$ then $\gcd(ab,c)=1$. My attempt is let $\gcd(ab,c)=d$. Since $d \mid ab$ and $d \mid c$ , $d \mid (abt+cs)$ for some integers $s$ and $t$. Then by definition of divisibility, we have $$abt+cs=dk$$ for some integers $k$. Then I got stuck here.
80532
I'm trying to prove that $\operatorname{lcm}(n,m) = nm/\gcd(n,m)$ I showed that both $n,m$ divides $nm/\gcd(n,m)$  but I can't prove that it is the smallest number.  Any help will be appreciated.
72856
Here is the question I am trying to prove:     If $a,b$ are relatively prime and $a&gt;b$ prove that $\gcd(a-b, a+b) \in \{1, 2\}$.   Can I begin with something like $(a-b)k + (a+b)l = d$ where $k,l$ are integers and $d=\gcd(a-b,a+b)$?
110975
Let $a_1....a_n$ be pairwise coprime.  That is $gcd(a_i, a_k) = 1$ for distinct $i,k$, I would like to show that if each $a_i$ divides $b$ then so does the product.  I can understand intuitively why it's true - just not sure how to formulate the proof exactly. I want to say if we consider the prime factorizations of each $a_i$, then no two prime factorizations share any prime numbers.   So the product of $a_1...a_n$ must appear in the prime factorization of $b$.  Is this correct?  Or at least if if the idea is correct, any way to formulate it more clearly?
41028
Show that if $c_1, c_2,\ldots, c_{\phi(m)}$ is a reduced residue system modulo $m$, $m \neq 2$, and $m$ is a positive integer, then $c_1 +\cdots+ c_{\phi(m)} \equiv 0 \pmod{m}$   From the problem statement, I only know that $\gcd(c_i, m ) = 1$. Is there any related theorem that I missed?  A hint would be greatly appreciated.  Thanks, Chan
123191
I was working my way through some number theoretic proofs and being a newbie am stuck on this problem :     If $(x, 4) = 2$ and $(y, 4) =2$, then $(x + y, 4) = 4$,     where $(a,b)$ denotes the greatest common divisor of $a$ and $b$.   My Solution  (Incorrect)   $x-4 = 2t$ $y-4 = 2p$ $x + y - 8 = 2(t+p) \Rightarrow x + y - 4 = 2f + 4 = 2(f+2)\Rightarrow 2$ divides $(x+y , 4)$   My Question:  My solution is definitely inadequate. Can someone help me out?
18363
I need to prove that $z\gcd(a,b)=\gcd(za,zb)$.    I tried a lot, for example, looking at set of common divisors of the two sides, but I can't conclude anything from that. Can you please give me some advice how I can handle this problem? And $a,b,z \in \mathbb{Z}$.
2974
Let $(a,b)$ denote the GCD of $a$ and $b$, and let $[a,b]$ denote the LCM of $a$ and $b$. Prove $\frac{[a,b,c]^2}{[a,b][b,c][c,a]}=\frac{(a,b,c)^2}{(a,b)(b,c)(c,a)}$.
3974
Using divisibility theorems, prove that if $\gcd(a,b)=1$ and $a|c$ and $b|c$, then $ab|c$.   This is pretty clear by UPF, but I'm having some trouble proving it using divisibility theorems. I was looking at , and if this could be proven, then the solution would follow immediately.