It is an exercise on the lecture that i am unable to prove.  Given that $gcd(a,b)=1$, prove that $gcd(a+b,a^2-ab+b^2)=1$ or $3$, also when will it equal $1$?
29124
Hint:  $a^2 -ab +b^2 = (a+b)^2 -3ab.$  I know we can say that there exists an $x,y$ such that $ax + by = 1$.  So in this case, $(a+b)x + ((a+b)^2 -3ab)y =1.$  I thought setting $x = (a+b)$ and $y = -1$ would help but that gives me $3ab =1.$  Any suggestions?
89643
Prove that $\gcd(3^n-2,2^n-3)=1$ if and only if $\gcd(5,2^n-3)=1$ where $n$ is a natural number.   I didn't see an easy way to prove this using the Euclidean algorithm, but it seems true that both gcd's are not $1$ only if $n = 3+4k$. Is there an easy way to prove the statement?
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)$
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!
117753
Prove that $$gcd(2^{2^m}+1, 2^{2^n}+1)=1$$ if $m, n$ are positive integers such that $m \neq n$.  A Hints to solve the problem is also given in the book as follows:  Let $m&gt;n$. Then $2^m=2^{n}2^{m-n}=2^n.2k$ for some integer $k$, (since $m&gt;n$). Let $2^{2^n}=x$. Then $2^{2^m}-1=x^{2k}-1$ and it is divisible by $x+1$.  I am still unable to solve. Please help.
40178
Prove that if $\gcd(a,c)=1$ and $\gcd(b,c)=1$ then $\gcd(ab,c)=1$. My attempt is let $\gcd(ab,c)=d$. Since $d \mid ab$ and $d \mid c$ , $d \mid (abt+cs)$ for some integers $s$ and $t$. Then by definition of divisibility, we have $$abt+cs=dk$$ for some integers $k$. Then I got stuck here.
109119
Prove that if $a$ and $b$ are odd, coprime numbers, then $\gcd(2^a +1, 2^b +1) = 3$.   I was thinking among the lines of:  Since $a$ and $b$ are coprime numbers, $\gcd(a,b)=1$. Then there exist integers $x$ and $y$ such that, $ax+by=1$.   Then, $a=(1-by)/x$, $b=(1-ax)/y$  So if I write $2^a+1$ as:  $2^{(1-by)/x}+1$  Then can I say that the above expression is equivalent to 0 (mod 3)?
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?
43423
I tried to prove this by induction but I got stuck, this is what I've got.  Base case: $n = 2$. $\gcd(2! + 1, 3*3!+1) = gcd(3, 7) = 1.$  Inductive step: assuming for $n = k$ that $\gcd(k!+1, 3k!+1) = 1$ holds. Let $n = k + 1$. We have to prove that $\gcd((k+1)! + 1, 3(k+1)!+1) = 1.$  From assumption we get that:  $\gcd(k!+1, 3k!+1) = 1$  Multiplying this by $k + 1$ we get:  $(k + 1) * \gcd(k!+1, 3k!+1) = k + 1$  Subtracting k from both sides:  $(k + 1) * \gcd(k!+1, 3k!+1) - k = 1$  Now $k+1$ can enter the gcd and we have:  $\gcd((k +1)! + (k + 1), 3(k + 1)! + (k + 1)) - k = 1$  Now I dont know where to proceed from here.
21114
I want to find this  $$ \sum_{k=1}^n \gcd(k,n)$$  but I don't know how to solve. Does anybody can help me to finding this problem.  Thanks.
47293
How can I prove that if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$, without using prime decomposition? I should only use definition of gcd, division algorithm, Euclidean algorithm and corollaries to those. Thanks for your help!
83845
I am lost.   So far...  If $\gcd (a,b) = 1$, by Bezout's Formula  $ax + by = 1$  If $c|(a+b)$, then $cf = a+b$  Then,  $a (x-y) + cfy = 1$   $b(yx) + cfx = 1$  Am I on the right track? Any suggestions?
27033
Let $p$ be prime number ($p\gt2$) and $a,b\in\mathbb Z$ ,$a+b\neq0$ ,$\gcd(a,b)=1$ how to  prove that $$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1~~\text{or}~~ p$$  Thanks in advance .
39116
Somewhere on Stack Exchange I saw the equation     $$\gcd(2^m-1,2^n-1)=2^{\gcd(m,n)}-1.$$   I had never seen this before, so I started trying to prove it. Without success...  Can anyone explain me (so actually prove) why this equation is true?  And can we say the same when replacing the '$2$' by any integer number '$a$'?
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?
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.
2131
I know that $\gcd(a,b)$ divides $a$ and $b$, and must also then divide $(a)(t)$ ($t$ being some integer).  This makes sense to me, but how do I prove it?  It seems that the addition of $(a)(t)$ is a continuation of the linear combination of $\gcd(a,b) = av + bu$ for some $v$, $u$ being elements of $\mathbb{Z}$.    Any help?