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

• Jun 9th 2011, 02:08 PM
VinceW
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!
• Jun 9th 2011, 02:40 PM
PaulRS
Note that: $\displaystyle \text{gcd} ( a^2+b^2,a+b) = \text{gcd}((a+b)^2 - (a^2+b^2),a+b)$ (Wink)
• Jun 9th 2011, 02:41 PM
Also sprach Zarathustra
Quote:

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.
• Jun 13th 2011, 04:02 PM
Solvoid
Re: Greatest Common Divisor Problen: If gcd(a, b) = 1, solve gcd(a^2 + b^2, a + b)
Quote:

Originally Posted by PaulRS
Note that: $\displaystyle \text{gcd} ( a^2+b^2,a+b) = \text{gcd}((a+b)^2 - (a^2+b^2),a+b)$ (Wink)

So starting from this point we can prove it as follows:

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

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

Conversely, let $\displaystyle y_1$ be any common divisor of $\displaystyle (2 \cdot a \cdot b)$ and $\displaystyle (a + b)$. Then $\displaystyle a^2 + b^2 = (a + b)^2 - 2 \cdot a \cdot b \equiv 0^2 - 0 \equiv 0$ $\displaystyle ($mod $\displaystyle y_1)$, therefore $\displaystyle y_1$ is a common divisor of $\displaystyle (a+b)$ and $\displaystyle 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. $\displaystyle GCD(a^2+b^2,a+b) = GCD(2 \cdot a \cdot b, a+b)$.

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

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

We show by example that the GCD of $\displaystyle 2$ is not only possible, but realized. Set $\displaystyle a=3, b=5$. Then the problem's hypthoses are satisfied and $\displaystyle a+b = 8$, $\displaystyle a^2+b^2 = 34$, which indeed have a GCD of $\displaystyle 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 $\displaystyle a=2, b=3$. Then $\displaystyle a+b=5$, $\displaystyle a^2 + b^2 = 13$, which indeed have a GCD of $\displaystyle 1$.