I'm not really sure how to approach the problem, since I'm not really sure I understand the mechanisms why it is true aside from putting some numbers in and see that it works.  Qualitatively, I'd try a proof by contradiction, trying to show that $\gcd(a-bc, b) \neq \gcd(a,b)$ and use some prime attribute to contradict the assumption.
81
Given: $a = qb + r$. Then it holds that $\gcd(a,b)=\gcd(b,r)$. That doesn't sound logical to me. Why is this so?    Addendum by LePressentiment on 11/29/2013: (in the interest of  and averting a duplicate)  What's the intuition behind this result? I only recognise the proof and examples solely due to algebraic properties and formal definitions; I'd like to apprehend the result naturally.
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!
74091
Problem: Show that if $(b,c)=1$, then for any integer $a$ we have $(a,bc)=(a,b)(a,c)$. [Hint: Prove that each member of the alleged equation divides the other.]  This is the way I proved it (without the hint): $(a,b)(a,c)=(a(a,b),c(a,b))=(a^2,ab,ac,bc)=(a^2,bc,a(b,c))=(a^2,a,bc)=((a^2,a),bc)=(a,bc)$  But how should I prove it using that hint or at least a similar proof.
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.
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.
1810
I know it might be too easy for you guys here. I'm practicing some problems in the textbook, but this one really drove me crazy. From $\gcd( a, b ) = 1$, I have $ax + by = 1$, where should I go from here? The extra $ac$ is so annoying. Any hint?    Thanks, Chan
22520
I came to point where I suppose for case 1 that $A\subseteq B$ and conclusion is trivial. For case 2 I suppose that $A\not\subseteq B$ and try to prove $B\subseteq A$, but that gets me nowhere. Any pointers here are most welcome.
103058
Prove that (a) gcd(a, b) = gcd (a, b – a) (b) Let r be the remainder if we divide b by a. Then gcd(a, b) = gcd(a, r).  I solved part a like: Assume a=pcommonpa b=pcommonpb gcd (a,b) = pcommon b-a = pcommon*(pb-pa)  So: gcd(a, b-a) = common again But I need help for part b guys I can solve it but I need a mathematical expression.
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.
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?
71548
I am a beginner in number theory and I would like some hints to solve the following  problem : Assume we have natural numbers $a_1,a_2,...$ such that $i$ is not equal to $j$ and $\gcd(a_i , a_j) = \gcd(i,j)$. Prove that $a_i = i$. I know that I have to show $i$ counts $a_i$ and $a_i$ counts $i$ but I don’t know how to show this. Since $\gcd(i,j) = \gcd(j,i)$ is it also true that $a_i = j$?
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.
45763
Let $p$ be a prime. Suppose that $\gcd(a, b) = p$. Find $\gcd(a^2,b)$  for all integers a and b.   I was able to prove that $\gcd(a^2,b^2) = p$ but I don't know if it helps.  Any help is greatly appreciated.
55171
Show that if $a, b$ and $c$ are integers with $c|ab$ then $c|(a,c)(b,c)$.  Now $(a, c)$ and $(b, c)$ would both divide $c$ since it's the gcd, but how would I show $c$ divides their product, and $(a,c)(b, c) \geq  c$ and not the other way around?
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.
34036
Prove for positive integers $a,b,c$ and $d$  (where $b  \neq 0$ , $d \neq 0$ and $b \neq d$), if $\gcd(a,b) = \gcd(c,d) = 1$, then $\frac{a}{b} + \frac {c}{d}$ is not an integer.  I understand that if $\gcd(a,b)$ and $\gcd(c,d) = 1$, at least one number in each pair is a prime or is $1$. As for after that, I'm totally stumped, could I get some tips, clues, help?
78958
If $a$ and $b$ are two coprime integers then prove that $\gcd((a+b)^m, (a-b)^m) \leq 2^m$  My attempt:  I took two cases first one in which a and b are both odd then very clearly the gcd will be 2^m but I'm stuck in the second case in which one of the integer is even and the other one is odd I am reaching no where I tried everything even binomial expansion but I'm stuck.