My attempt:  $ax+by=d$(as gcd(a,b)=d).  Dividing by c  $\frac{a}{c}x+\frac{b}{c}y=\frac{d}{c}$  Let $k$ be the gcd of$ (\frac{a}{c},\frac{b}{c})$ so $k|\frac{a}{c}$ and $ k|\frac{b}{c}$ then $k|\frac{a}{c} x + \frac{b}{c}y$  and so $k|\frac{d}{c}$.  As $d|a $ implies that $\frac{d}{c}|\frac{a}{c} $ similarly it divides $\frac{b}{c}$ . Hence $\frac{d}{c}|k$(as $k$ is the greatest common factor). Thus $k= \frac{d}{c}$
4220
I'm trying to prove that $(ma, mb) = $|$m$|$(a, b)$ , where $(ma, mb)$ is the greatest common divisor between $ma$ and $mb$. My thoughts: If $(ma, mb) = d$ , then $d$|$ma$ and $d$|$mb$ → $d$|$max + mby$ → $d$|$m(ax+by)$. This implies that $d$|$m$ or $d$|$(ax+by)$. This is the same as  $d$|$m$ or $d$|$a$ and $d$|$b$, so $d$|$m$ or $d$|$(a,b)$. This is the same as $d$|$m|$ or $d|(a,b)$, so $d$|$|m|(a,b)$. I don't know what to do.
73192
Prove: If $a\mid m$ and $b\mid m$ and $\gcd(a,b)=1$ then $ab\mid m$  I thought that $m=ab$ but I was given a counterexample in a comment below.  So all I really know is $m=ax$ and $m=by$ for some $x,y \in \mathbb Z$. Also, $a$ and $b$ are relatively prime since $\gcd(a,b)=1$.   One of the comments suggests to use , i.e., $aq+br=1$ for some $q,r\in\mathbb{Z}$. Any more hints?  New to this divisibility/gcd stuff. Thanks in advance!
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.
38165
Suppose $\forall (a;b;c;d) \in \mathbb{Z}^4$ as $\gcd(a,b)=\gcd(c,d)=1$:  How can I prove that $\gcd(a,bc)=\gcd(a,c)$?  Also, how to prove that $\gcd(ac,bd) = (\gcd(a,d))*(\gcd(b,c))$?
45487
I'm working through Oystein Ore's Number Theory and its History.  On p. 109, I'm stuck on #2.  The question asks the reader to verify the following identity [Note: $(x,y)=\gcd(x,y)$]: $$(ab,cd)=(a,c)(b,d)\left(\frac{a}{(a,c)},\frac{d}{(b,d)}\right)\left(\frac{c}{(a,c)},\frac{b}{(b,d)}\right)$$  I've tried numerous numeric examples and not found an exception.  I've tried a messy proof, substituting sample factors and exponents, but it's not very cohesive, clear, or robust.  Clearly, if $a,b,c,d$ are all relatively prime, the answer is clear.  I don't know how to concisely prove this if that's not the case though. I've tried using the idea that $m(x,y)=(mx,my)$ to get rid of the denominators, but I still end up with some fractions.  I've tried to use the symmetry of the fractions to simplify things. I also looked at this link without significant progress:
56453
I'm trying prove $$\gcd(a,b) \gcd(a,c) \gcd(b,c) \,\text{lcm} (a,b,c)^2=\text{lcm}(a,b)\,\text{lcm}(a,c) \,\text{lcm}(b,c) \gcd(a,b,c)^2$$  It is a part of solution of another problem I try a lot to prove it but I could not be succeed.  I tried using exponent manipulation in prime factorizations but it didn't help me.
1089
Suppose $a$ and $b$ are positive integers, and that $d=\gcd(a,b)$. Suppose we have found integers $x$ and $y$ such that $ax+by=d$. Prove that $x$ and $y$ are relatively prime.
21254
How can i prove that  if $\gcd(a,b)=1$ there exist $x&gt;0$ and $y&gt;0$ such that $ax-by=1$?
94419
I'm trying to prove that if $a$ divides $bc$ and $\gcd(a,b) = d$ then $\frac a d$ divides c. I tried using Bezout identity but couldn't get anywhere.
114208
Let $a, b, c \in \mathbb{N}$. Show that if $a^2+b^2=c^2$ then $gcd(a,b)=gcd(a,c)=gcd(b,c)$.  Using basic divisibility criteria I couldn't advance anything.
8732
If $\gcd(a,b) = 1$ and $a,b\mid x$ then $ab\mid x$.  My attempt at answering the question:  \begin{align*} x &amp;\equiv 0 \pmod{a}\\\ &amp;\Longrightarrow x\text{ is divisible by $a$}\\\ &amp;\Longrightarrow x = ma\text{ for some integer $m$}\\\ \ \\\ x &amp;\equiv 0 \pmod{b}\\\ &amp;\Longrightarrow  x\text{ is divisible by $b$}\\\ &amp;\Longrightarrow x = mb\text{ for some integer $m$}\\\ \ \\\ x^2 &amp;= (ma)(mb)\\\ x^2 &amp;= (m^2)(ab)\\\ x &amp;= \sqrt{m^2ab}\\\ x &amp;= m\sqrt{a}\sqrt{b} \end{align*} Let $m$ be $k\sqrt{a}\sqrt{b}$. Then \begin{align*} x &amp;= kab\\\ &amp;\Longrightarrow x \equiv 0 \pmod{ab} \end{align*}  Is this correct, if not can someone point me in the right direction?
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?
7242
I can't crack this one.      Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$ (the only constraint is that  $a,b,c,z \in \mathbb{Z}$ and $c\neq 0)$
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.
45857
Let $a,b,c$ be positive integers.  Verify that Diophantine equation $ax + by = c$ has integer solution $x_0, y_0$ if and only if $GCD(a,b)|c$. Attempt Diophantine $ax + by = c$ has integer solution $x_0, y_0$ implies $GCD(a,b)|c$. Factoring out $ GCD(a,b)$ from each side gives $$\frac{1}{GCD(a,b)}(ax + by) = \frac{1}{GCD(a,b)}c$$ which must still have an integer solution as $GCD(a,b)$ obviously divides both $a$ and $b$.  If $GCD(a,b)$ does not divide $c$ there is no integer solution. That $GCD(a,b)|c$ implies that $ax + by = c$ has integer solution $x_0, y_0$. Let $c = GCD(a,b)d$, where $d$ is integer. $ax + by = GCD(a,b)d$;  divide both sides by $GCD(a,b)$: Obtain $mx + ny = d$ with $GCD(m,n) = 1$.  If $d$ is an integer and $GCD(m,n) = 1$ then $x,y$ must be integers as $mx + ny$ cannot be further divided evenly. or $ax + by = c$ has no solution implies $GCD(a,b)$ does not divide c. $c = GCD(a,b)(\frac{ax}{GCD(a,b)} + \frac{by}{GCD(a,b)}) + r$ with $GCD(a,b) &gt; 0, 0&lt;r&lt;GCD(a,b)$, r integer $\frac{c}{GCD(a,b)} = \frac{ax + by}{GCD(a,b)} + \frac{r}{GCD(a,b)}$
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.
108892
I am having trouble understanding why the Euclidean algorithm for finding the GCD of two numbers always works?   I found some resources here (), and here().  But I am a little confused about how they approach it here. I understand that if we have two numbers, a and b, then the greatest common divisor of a and b has to be less than a, and if a divides b, then a will have to be the GCD.   But I am confused about what happens when:  b=a*q+r So now, we are saying that we take a/r, correct? Why should we do this at all?