Here (a,b) represents GCD of a and b  [a,b] represents LCM of a and b  I deduced the relation $(m,n,k)^2[m,n,k]=mnk$  But I am not able to proceed further. Any suggestions??
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)}$.
119971
Prove that $\mathbb Z_{m}\times\mathbb Z_{n} \cong \mathbb Z_{mn}$ implies $\gcd(m,n)=1$.  This is the converse of the Chinese remainder theorem in abstract algebra. Any help would be appreciated.  Thanks!
46484
Recently, I was informed that we can verify the famous formula about $\mathrm{lcm}(a,b)$ and $\gcd(a,b)$ which is $$\mathrm{lcm}(a,b)=\frac{|ab|}{\gcd(a,b)} $$ via group theory.   The least common multiple of two integers $a$ and $b$, usually denoted by $\mathrm{lcm}(a,b)$, is the smallest positive integer that is a multiple of both $a$ and $b$ and the greatest common divisor ($\gcd$), of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.  I do not know if we can prove this equation by using the groups or not, but if we can I am eager to know the way someone face it. Thanks.
55738
A problem taken from the exercises of Concrete Mathematics by Graham, Knuth, and Patashnik  is as follows:      Prove that if $a\perp b$ and $a&gt;b$ then      $$\gcd(a^m-b^m,a^n-b^n) = a^{\gcd(m,n)} - b^{\gcd(m,n)},\quad 0\leq m&lt;n.$$   (In the notation of the book, $a\perp b$ means that $a$ and $b$ are relatively prime, i.e. $\gcd(a,b)=1$.)  I can not prove this equation. Can you please help me to prove this formula?
23362
Prove $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ for $0\ne a,b,c\in \Bbb{Z}$. I tried solving it with sets but I sense there are some details I am missing. I would truly appreciate your reference.
82492
I'm learning about properties of greatest common divisors, specifically when two numbers are relatively prime.  The exercise I'm working through is :     Suppose that $\gcd(a,b) = 1$ and that $a\mid n$ and $b\mid n$. Prove that $ab\mid n$   Proof(so far):   $\gcd(a,b)=1$ implies $am+bk = 1$ for some integers $m$ and $k$.   (Given hint) Multiplying the equation by $n$ yields: $$amn+bkn=n$$  I'm not sure what to do after applying the hint. Am I supposed to show that $ab$ divides both $amn$ and $bkn$?  Thanks in advance.
8302
My reference for learning abstract algebra says that in an abelian group $G$ the product of two elements (say $a$ with order $n$ and $b$ with order $m$) has order $mn$ if $gcd(n,m) = 1$.   What I don't understand is where the $gcd(m,n)=1$ comes into use in proving this fact? For example, $ a^{mn} = (a^n)^m = (e)^m = e$ (identity element). A similar argument for $b^{mn}$ together with the fact that $G$ is abelian is enough to show that $(ab)^{mn} = e$. From here, how do I conclude for an integer $r &lt; mn$ that $(ab)^r \neq e$  Also, are there any other conclusion that can be drawn if $gcd(n,m) \neq 1$ ?  Thanks for any feedback in advance !
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.
100285
Why is this true? I suspect that its because $\frac{LCM(a,b)^3GCD(a,b)^3}{b^3}=a^3$ and $\frac{LCM(a,b)^3GCD(a,b)^3}{a^3}=b^3$, so it must be the case for $LCM(a,b) \notin R(a,b)$, right?
106815
I need to show that the $$\gcd\left(\frac a {\gcd(a,b)},\frac b {\gcd(a,b)}\right) =1$$  I'm not sure exactly how to approach this .. I tried using the fact that $\gcd(a,b)=d$ so $d=ma+nb$ but I didn't get too far  Could anyone suggest where to start?
19995
Here is what I got so far:  Let $\gcd(ka,km) = d$  Then by the Euclidean Algorithm, we have integers $s,t$ such that:  $$s(ka) + t(km) = d \implies k|d  $$  Let $$d/k = g = sa + tm.  \tag{1}$$  So now I need to show that $g$ is indeed = $\gcd(a,m)$. Let  $\gcd(a,m) =  h$  Now since $k|d \implies d|a , d|m  \space $  (since $$\gcd(ka,km) = d \implies  g|  \gcd(a,m) = h \\\implies h = dj  ,$$ for some integer $j$.  Putting this into (1):  $$ h/jk = g = sa + tm $$  since $$h = dj \implies dj/j = kg \\ \implies d = kg. $$   So $g$ is the $\gcd(a,m)$?  Is this a correct proof? Or have I gone in some sort of circle? Many thanks for any hints or direction!
110279
If integers $a$ and $b$ are not both zero, then $\gcd(a,b)=\gcd(a-b,b)$   Assume either $a=0$ or $b=0$. If $a=0$, then $\gcd(a,b)=\gcd(0,b)=b$ and $\gcd(a-b,b)=\gcd(-b,b)=-b$, so $\gcd(a,b)\neq\gcd(a-b,b)$.  If $b=0$, then $\gcd(a,b)=\gcd(a,0)=0$ and $\gcd(-b,b)=\gcd(a,0)=0$.  So, what can I say? Can you help? Can you check my proof-trying?
55143
The problem's quite clear. Prove that $$\gcd(a^2, b^2) = \gcd(a, b)^2$$  This is easy to understand intuitively and using the Fundamental Theorem of Arithmetic would be easy but I want to prove it by using the Divisibility axioms and the GCD. I have attempted it and am mentioning my results.  Here $d = \gcd(a, b)$.   $$d | ax + by \implies d^2 | a^2x^2 + 2axby + b^2y^2 \implies d^2 | a^2x^2 + b^2y^2 \implies \gcd(a^2, b^2) | d^2$$  I feel that this is not necessary. Please help.  Also, the proof can be generalized to $$\gcd(a^n, b^n) = \gcd(a, b)^n$$  Any help would be appreciated.
10327
I know that the definition of gcd of two numbers $ a, b $ is $G$ ,where  $G\mid a$, $\;G\mid b  $ and  If $d\mid a$, $\;d\mid b $, then $ d\mid G.$  Now, using this how do I prove that in $\mathbb Z$, this definition coincides with the definition that $G$ is the GREATEST (w.r.t. usual ordering) common divisor?  So to prove that I write, say $G=dq+ r,\;  0\le r&lt;d$. My aim is to show that $ r$ is $0$. So I have to construct some $G+x $ which is also a divisor of both $ a$ and $b$, to get a contradiction. How do I get $ x$?
80346
I'm having some trouble proving the following proposition:  Let $m \in \mathbb N$ and $a,b,k \in \mathbb Z$, then: $$ka \equiv kb \pmod{m} \iff a \equiv b \pmod{\frac{m}{\gcd(k,m)}}$$  I began by trying to prove that $a \equiv b \pmod{\frac{m}{\gcd(k,m)}} \implies ka \equiv kb \pmod{m}$ but I got stuck with: $$a\gcd(k,m) \equiv b \gcd(k,m) \pmod{n}$$ Then I also tried to prove that $ka \equiv kb \pmod{m} \implies a \equiv b \pmod{\frac{m}{\gcd(k,m)}}$ But I also was not able to conclude anything. This is my first time learning modular arithmetic and I'm still confused with the concepts and have no intuition with this at all, this is perhaps why I'm having some trouble solving these types of questions. How can I prove this?
6930
I was reading a text book and came across the following:  Important Results (This comes immediately after LCM:) If 2 [integers] $a$ and $b$ are given, and their $LCM$ and $HCF$ are $L$ and $H$ respectively, then $L \times H = a \times b$  Can some please help me understand why the above result is true? Thanks in advance.
28693
How can we show that the number of pairs $(a,b)$ (where the pairs $(a, b)$ and $(b, a)$ are considered same) with $\operatorname{lcm}(a, b) = n$ is equal to $$\displaystyle\frac{(2e_1+1)(2e_2+1)...(2e_k+1)+1}{2},$$ Where $n=p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$, $p_i$s are prime for all  $1\leq i\leq k$. I managed to guess this formula for a programming problem I was working on, but I'd be interested in a deduction or proof.