# Thread: Greatest Common Divisor Problen: If gcd(a, b) = 1, solve gcd(a^2 + b^2, a + b)

1. ## Greatest Common Divisor Problen: If gcd(a, b) = 1, solve gcd(a^2 + b^2, a + b)

How do I solve the problem in the subject line? The back of the book lists an answer "1 or 2", but I'd like to see the steps used to arrive at that solution. Thanks!

2. Note that: $\text{gcd} ( a^2+b^2,a+b) = \text{gcd}((a+b)^2 - (a^2+b^2),a+b)$

3. Originally Posted by VinceW
How do I solve the problem in the subject line? The back of the book lists an answer "1 or 2", but I'd like to see the steps used to arrive at that solution. Thanks!
Hint:
d=gcd(a^2 + b^2, a + b)=gcd(a+b,a^2+b^2 +(a+b)(a-b))=gcd(a+b,2a^2), hence d|2a^2.

4. ## Re: Greatest Common Divisor Problen: If gcd(a, b) = 1, solve gcd(a^2 + b^2, a + b)

Originally Posted by PaulRS
Note that: $\text{gcd} ( a^2+b^2,a+b) = \text{gcd}((a+b)^2 - (a^2+b^2),a+b)$
So starting from this point we can prove it as follows:

If $x|(a+b)$, then since $(a+b)|(a+b)^2$ we have $x|(a+b)^2$.

In particular, any common divisor $x_1$ of $(a^2+b^2)$ and $(a+b)$ is also a divisor of $(a+b)^2$, hence $(a+b)^2 - (a^2+b^2) \equiv 0 - 0 \equiv 0$ $($mod $x_1)$, so $x_1|((a+b)^2 - (a^2+b^2))$. $(a+b)^2 - (a^2+b^2) = 2 \cdot a \cdot b \Rightarrow x_1|(2 \cdot a \cdot b)$.

Conversely, let $y_1$ be any common divisor of $(2 \cdot a \cdot b)$ and $(a + b)$. Then $a^2 + b^2 = (a + b)^2 - 2 \cdot a \cdot b \equiv 0^2 - 0 \equiv 0$ $($mod $y_1)$, therefore $y_1$ is a common divisor of $(a+b)$ and $a^2 + b^2$ as well.

Thus, since we showed the above two pairs have the same set of common divisors, it follows they have the same greatest commond divisor, i.e. $GCD(a^2+b^2,a+b) = GCD(2 \cdot a \cdot b, a+b)$.

Let $y_2$ be any common divisor of $(a \cdot b)$ and $(a+b)$. Let $p_y$ be any odd prime factor of $y_2$. Then $p_y$, being prime, divides at least one of $a,b$. WLOG let us assume $p_y|a$. Then $a + b \equiv 0 + b \equiv b$ $($mod $p_y)$. Recall that $p_y|(a+b)$, therefore $0 \equiv a + b \equiv b$ $($mod $p_y)$. But this means $p_y$ is a common nontrivial divisor of $a$ and $b$, contradicting that $GCD(a,b)=1$.
Thus, our assumption that $p_y$ exists must have been wrong. Then this implies that $GCD(a \cdot b, a + b) = 1$.

Now, let $p_3$ be any common PRIME divisor of $(2 \cdot a \cdot b)$ and $(a+b)$. We already showed $p_3$ does not divide $a \cdot b$, therefore $p_3$ divides the only remaining factor of $2 \cdot a \cdot b$, which is $2$. Thus, $p_3 = 2$ (since $2$ is prime). This implies that any common divisor is a power of $2$. Notice that this also implies that both $a$ and $b$ are odd (whenever the GCD we are looking for is greater than 1). Thus, $4$ does not divide $(2 \cdot a \cdot b)$ so the only possible nontrivial common divisor is $2$. (IOW, other than $2$, the only possible divisor is $1$).

We show by example that the GCD of $2$ is not only possible, but realized. Set $a=3, b=5$. Then the problem's hypthoses are satisfied and $a+b = 8$, $a^2+b^2 = 34$, which indeed have a GCD of $2$.

The other possibility admitted by our proof is the case of the trivial GCD (i.e. GCD = 1). To see that this is realized, set $a=2, b=3$. Then $a+b=5$, $a^2 + b^2 = 13$, which indeed have a GCD of $1$.