Show that if $gcd(x, y) = 1$ then $gcd(x − y, x + y)$ is either $1$ or $2$  I think the question is asking me to show if the $\gcd(x,y)$ then the $\gcd(x-y,x+y)$ is $1$ or $2$.  so, for the first bit. Let $d=\gcd(a,b)d=\gcd(a,b)$; by definition there are integers $a'a′$ and $b'b′$ such that $a=a'da=a′d$ and $b=b'db=b′d$, so $a'dx+b'dy=da′dx+b′dy=d$. Dividing through by $dd$, then $a'x+b'y=1′x+b′y=1$.  Let $e=gcd(x,y)e=gcd(x,y)$. As before, there are integers $x'x′$ and $y'y′$ such that $x=ex'x=ex′$ and $y=ey'y=ey′$. Substituting these into the previous equation, we get $a'ex'+'ey'=1a′ex′+′ey′=1$, or $e(a'x'+b'y')=1e(a′x′+b′y′)=1$. Since $a'x'+b'y'a′x′+b′y′$ is an integer, this implies that $e=1$ or $e=−1$: these are the only divisors of $11$. But $e$ is a greatest common divisor and hence by definition positive, so $e=1$
69274
If  $a,b$ are positive integers such that $\gcd(a,b)=1$, then show that $\gcd(a+b, a-b)=1$ or $2$ and $\gcd(a^2+b^2, a^2-b^2)=1$ or $2 $. Progress We have   $\gcd(a,b)=1\implies \exists u,v\in \mathbb Z$ such that $au+bv=1\implies a^2u'+bv'=1, u',v'\in \mathbb Z$. Let $\gcd(a+b, a-b)=d$. Then $\mid (a+b)x+(a-b)y, \forall x,y\in \mathbb Z$. How to show $\gcd(a+b, a-b)=1$ or $2$ and $\gcd(a^2+b^2, a^2-b^2)=1$ or $2 $.
60229
Say $a$ and $b$ are integers. $\gcd(a,b)$ is then $d$. Now if $a$ equals $dm$ for some integer $m$ and b equals $dn$ for some integer n, how come the gcd of this m and n is always 1?
54066
If $x$ and $y$ are natural numbers, and $56x = 65y$, prove that $x + y$ is divisible by $11$.  I tried  taking the $\gcd(56x,65y)$ using the Euclidean algorithm, but I got nowhere with it and do not know where to head.
103936
This is some old Olympiad problem (I vaguely remember its Iranian )  I factorised it as  $ (x-y)(3x + 3y +1) = y^2 $  Then I fruitlessly tried to prove   $\gcd(x-y, 3x + 3y +1 ) = \gcd (6x+1,6y+1) = 1$  for proving that $x-y$ is a perfect square.  How do I continue my method or are there other ways to approach this intuitively?
75783
For the integers $a,b,c$ show that $\gcd(a,bc)=\gcd(a,\gcd(a,b)\cdot c)$  Proof:  Let $u$ and $v$ be integers. Then $\gcd(a,b)=au+bv$. Then $c\cdot \gcd(a,b)=c\cdot(au+bv)=acu+bcv$ Let $x$ and $y$ be integers. Then $\gcd(a,\gcd(a,b)\cdot c)=ax+(acu+bcv)y=ax+acuy+bcvy=a(x+cuy)+(bc)(vy)$.  Let $d$ and $e$ be integers. Then $\gcd(a,bc)=ad+bce$.   Since $d$ and $e$ are integers let $d=x+cuy$ and $e=vy$. Hence $\gcd(a,bc)=\gcd(a,\gcd(a,b)\cdot c)$
72040
Show that if $fd'=f'd $ and the pair $f, d $ are coprime, that is gcd($d,f $)=1, as is the pair $f',d' $, then $f=f' $ and $d=d' $.  This should be simple, but I couldn't verify it. 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.
24761
Show that if $n$, $a$, $b$, and $c$ are positive integers with $\gcd(a, b) = 1$ and $ab = c^n$, then there are positive integers $d$, and $e$ such that $a = d^n$ and $b = e^n$.   I know that (by Bezout) $\gcd\left(a,b\right) = 1$ implies $ax + by = 1$ for some integers $x$ and $y$, and also that $\gcd\left(a^n,b^n\right) = 1$, but this does not help me.
99730
Here's the question:  Let $a$ and $b$ be integers such that $\gcd(a,b) = 1$. Let $r$ and $s$ be integers such that  $$ar + bs =1.$$  Prove that $\gcd(a,s) = \gcd(r,b) = \gcd(r,s) = 1$.  I was stuck how to solve this problem. My first instinct is to do a proof by contradiction, that is, assume the $\gcd(a,s) &gt; 1$ - therefore there exists a $d &gt; 1$ such that $a = dn$ for an integer $n$ and $s = dm$ for an integer $m$. However, I don't know where to go from here (or even if this is the correct route).  I would really appreciate some help - thank you in advance for everything!  Thanks!
38131
So, if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$ means $1=ax+by$, and want to show $a^2x+b^2y=1$. By squaring $1=ax+by$ both sides, I get, $1=(ax)^2+b(2axby+by^2)$. It doesn't help my proof. Please help me with this proof.
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.
59721
I would like to know why $\gcd(3n,3n+ 2) = 1$ when $n$ is odd.  I tried to use the Euclidean Algorithm, but I got confused: $$ 3n+2 = 3n + 2$$ $$3n = \ ? $$ Thanks!
74959
Prove or disprove 'If $\gcd(a,b)=1$ then, $\gcd(a^2,b^2)=1$, with $a,b\not= 0$'  I need to prove this statement. I think it is true and also the converse is true.  I took some examples such as $\gcd(2,5)=1$, and $\gcd(4,25)=1$...  But how can I prove this? I know that $1=ax+by$ for some $4x,y\in \mathbb{Z}$.. But not sure   How to go from there..   Any clue?
4480
How do I go about proving this?  If $\gcd(a,b)=1$ and $\gcd(a,c)=1$, then $\gcd(a,bc)=1$. I'm very confused with gcd proofs.
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.
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)$
48672
Suppose $a, b \in \mathbb{Z}$, $a &gt; b$, and $\gcd (a,b) = 1$.  What can be said about $\gcd (a+b,a-b)$?  Is it true in general that $\gcd (a+b,a-b) \leq 2$?