$a,b\in\mathbb{N}$ and $ab&gt;2$.Suppose,$\text{lcm}(a,b)=L,\gcd(a,b)=G$ and $a+b\mid L+G$.Prove that $\dfrac{(a+b)}{4}\cdot(a+b)\ge (L+G)$. Also prove that equality occurs when $a,b$ are consecutive odd integers.    Hint: There is an exception when $a,b$ are both equal to 2.  I could not approach this problem at all. Please help.
122370
Let $a$ and $b$ be natural numbers with $ab&gt;2$. Suppose that the sum of their highest common factor and least common multiple is divisible by $a+b$. Prove that the quotient is at most $\frac{a+b}4$. When is this quotient exactly equal to $\frac{a+b}4$.
33423
I want to show that for $\gcd(a,b) = 1$ $a,b \in Z$   $\gcd(a+b, a-b) = 1$ or $\gcd(a+b, a-b) = 2$ holds.      I think the first step should look something like this:      $d = \gcd(a+b, a-b) = \gcd(2a, a-b)$   From here I tried to proceed with two cases. 1: $a-b$ is even, which leads to $\gcd(a+b, a-b) = 2$ 2: $a-b$ is odd, which leads to $\gcd(a+b, a-b) = 1$  My main problem I think is, that I do not know how I should include $\gcd(a,b) = 1$ in the proof.  Any help is appreciated. Thx in advance. Cherio Woltan
107898
Show that $\gcd(a,bc)=1$ if and only if $\gcd(a,b)=1$ and $\gcd(a,c)=1$.  I am new at proofs and I think I should use Euclid's Lemma which states "If $p$ is a prime that divides $ab$, then $p$ divides $a$ or $p$ divides $b$. However, I am not sure how to create a concrete proof or argument.  Any hints or help would be greatly appreciated. Thanks!
7614
How can I prove that if $\gcd(a, b) = 1$, then $\gcd(ab, c) = \gcd(a, c) \times \gcd(b, c)$?  By eea there exists $ax+by=1$ from $\gcd(a,b)=1$ so a and be are co-primes there also exists $dk=a$ and $dj= b$ where $d=\gcd(a,b)=1$ this is all the information I have gathered from the question but I dont know how to approach and solve it. Can anyone help explain to me how to arrive at the answer? Thanks!
14113
Let $a, b, c$ be integers. Prove that if $\gcd(a,b)=1$ then $\gcd(ab,c) = \gcd(a,c) \gcd(b,c)$  First time asking here. I'm not sure what your policies are on general homework help but I truly am stuck.  So far I have shown $\gcd(a,c) \gcd(b,c)$ as an integer combination of $ab$ and $c$. So if I can show that $\gcd(a,c) \gcd(b,c)$ divides $ab$ and $c$ I can use the proof that if an integer $d$ is a common divisor of $a$ and $b$, and $d=ax+by$ for some $x$ and $y$, that $d=\gcd(a,b)$. However I don't really know where to start with this. Any help would be appreciated.
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.
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.
108006
We were given the following problem as an assignment, we proved the converse in class for prime numbers; however, we can't use the assumption that $\operatorname{gcd}(a,b) = 1$.  So I am struggling to think of my first possible move.  We are given $ar + bs = 1$, the only think I can think of is let $d$ be a common divisor or $ar + bs$ and then show that the $d = 1$.  However, I am not really sure how to do that.  If anyone could just give me a hint or two to nudge me in the right direction I would be appreciative.
50039
I am having trouble completing the proof if $a \mid b$ then $\gcd(a,b) = |a|$. My attempt: If $a\mid b$ there is a $k \in \mathbb{Z}$ such that $b = ak$. Let $d = \gcd(a,b)$. Then $d \mid a$ and $d\mid b$ so by hypothesis we have $d\mid a$ and $d\mid ak$. Hence, $d \leq \gcd(a,ak)$. We can easily see that the largest common denominator of $a$ and $ak$ is $|a|$, thus $d \leq\gcd(a,ak) = |a|$ so $\gcd(a,b) \leq |a|$. I am stuck and not sure how to show the reverse inequality $|a| \leq \gcd(a,b)$ to complete the proof.
37162
My problem is how to somehow relate the the gcd and congruence. I know that $(a,b) = ax + by$. I also know that $a \equiv b \pmod n$ means $n\mid a-b$. Any hints?  Thanks!
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.
41678
As stated in the title, the problem to prove is  Let $a,b,c \in \mathbb{Z}$. If $\gcd(a,c)=1=\gcd(b,c)$, then $\gcd(ab,c)=1$.  I think I've proved it, but I would like a second opinion. Here goes:  PROOF Suppose $\exists d \neq 1 \in \mathbb{Z}$ s.t $\gcd(ab,c)=d$. It follows then that $d|ab$ and $d|c$. Now, if $d|a$ but not $b$, then since $d|c$, by linearity we have $d|\gcd(a,c)$. But $\gcd(a,c)=1$ so then $d=1$. The argument for $d|b$ is similar, resulting in $d=1$. Thus, since both cases lead us to $d=1$, we have a contradiction on our hands $\implies$ $ab$ and $c$ must be relatively prime $\implies \gcd(ab,c)=1$. $Q.E.D$  The question: was this a valid argument or do you think I should provide more?
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$?
45033
I don't really know how to prove this, i suppose it must have something to do with the definition of greatest common divisor and Bézout's identity.  I looked at some other questions here and thought that i had to get to gcd(ma+nb,mn)=1 and that gcd(a,n)gcd(b,m)=1 too, but i'm not sure.
4816
Could someone please help me with this proof?     Suppose that $a, b \in N$, and $d = \gcd(a, b)$. Since $d$ divides $a$, we have $a = de$ for some integer $e,$ and similarly $b = df$ for some integer $f$. Prove that $\gcd(e, f) = 1$.   I understand why it works. Since d is all the common factors of $a$ and $b, e$ and $f$ had no common factors, therefore the $\gcd(e,f) = 1$. But how do I prove this?  Thanks in advance.
60939
I'm stuck at proving:     Let $a, b, c \in \mathbb{Z}, a\cdot b \neq 0$. Prove:   $$ a \mid m \hspace{15px}\text{and}\hspace{15px} b \mid m \implies \frac{a \cdot b}{\text{gcd}(a, b)} \mid m $$   My current attempt looks like this:  Let $t := \text{gcd}(a, b)$ donate the greatest common divisor of $a$ and $b$.   $$ \implies\exists\, a', b': a = t\cdot a' \hspace{15px}\text{and}\hspace{15px} b  = t \cdot b' $$  $$ \implies \frac{a  b}{\text{gcd}(a, b)} = \frac{a  b}{t} = \frac{t  a'b}{t} = a' b $$  I know that since b \mid m: $a'b \mid m$ iff $\text{gcd}(a', b) = 1$ and $a' \mid m$, but I'm not sure whether this is the right approach to this problem.   Currently I don't know about identities involving the least common multiple.
32234
In the integers, it follows almost immediately from the division theorem and the fact that $a | x,y \implies a | ux + vy$ for any $u, v \in \mathbb{Z}$ that the least common multiple of $a$ and $b$ divides any other common multiple.  In contrast, proving $e|a,b \implies e|gcd(a,b)$ seems to be more difficult. In Elementary Number Theory by Jones &amp; Jones, they do not try to prove this fact until establishing Bezout's identity.  has a proof without Bezout's identity, but it is convoluted to my eyes.  I tried my hand at it, and what I got seems no cleaner:  Proposition: If $e | a,b$, then $e | gcd(a,b)$.  Proof: Let $d = gcd(a,b)$. Then if $e \nmid d$, by the division theorem there's some $q$ and $c$ such that $d = qe + c$ with $0 &lt; c &lt; r$.  We have $a = k_1 d$ and $b = k_2 d$, so by substituting we obtain $a = k_1 (qe + c)$ and $b = k_2 (qe + c)$. Since $e$ divides both $a$ and $b$, it must divide both $k_1 c$ and $k_2 c$ as well. This implies that both $k_1 c$ and $k_2 c$ are common multiples of $c$ and $r$.  Now let $l = lcm(r, c)$. $l$ divides both $k_1 c$ and $k_2 c$. Since $l = \phi c$ for some $\phi$, we have $\phi | k_1, k_2$, so $d \phi | a, b$.  But we must have $\phi &gt; 1$ otherwise $l = c$, implying $r | c$, which could not be the case since $c &lt; r$. So $d \phi$ is a common divisor greater than $d$, which is a contradiction. $\Box$  Question: Is there a cleaner proof I'm missing, or is this seemingly elementary proposition just not very easy to prove without using Bezout's identity?