There are two numbers that are coprime to each other. What are the possible common positive divisors of their sum and the difference between them?

Sunday, June 3, 2012

Please email your solutions to puzzles@cotpi.com.

### 5 comments

### Credit

This puzzle is based on:

- Apostol, Tom M. Introduction to Analytic Number Theory. New York: Springer-Verlag, 1998. 21. Problem 4.

## Siddhesh Chaubal solved this puzzle:

Let the two numbers be \(a\) and \(b\). Let \(d\) be a common positive divisor of \(a + b\) and \(a - b\). Then \(d \mid a + b\) and \(d \mid a - b\). Therefore, \(d \mid (a + b) + (a - b)\), and thus \(d \mid 2a\). Also, \(d \mid (a + b) - (a - b)\), and thus \(d \mid 2b\). Since \(a\) and \(b\) are coprime to each other, they have no common positive factors other than \(1\), and hence, \(d \mid 2\). Thus \(d\) can be \(1\) or \(2\). \(d = 2\) is possible when the two numbers have the same parity, e.g. \(7\) and \(9\).

## Tanny Libman solved this puzzle:

We have two numbers, \(a\) and \(b\), and they have a sum and difference of \(a + b\) and \(a - b\), respectively. Let's call the common positive divisor of the sum and difference \(n\). We know that \(a + b \equiv 0 \pmod{n}\) and \(a - b \equiv 0 \pmod{n}\). From the second equivalence relation, we know that \(a \equiv b \pmod{n}\). Now plugging this into the first equivalence relation, we get \(a + a \equiv 0 \pmod{n}\). Thus, \(2a \equiv 0 \pmod{n}\).

If \(n\) is odd and \(2a \equiv 0 \pmod{n}\), then \(n\) is either \(1\) and thus it divides \(a\), or \(n > 1\) and thus \(n\) does not divide \(2\) which implies that it divides \(a\). Thus, \(a \equiv b \equiv 0 \pmod{n}\). Now if we want \(a\) and \(b\) to be coprime to each other, then the only possible value for \(n\) is \(1\).

If \(n\) is even and \(2a \equiv 0 \pmod{n}\), either \(a \equiv 0 \pmod{n}\) or \(a \equiv \frac{n}{2} \pmod{n}\). The first possibility would mean that \(a\) and \(b\) are both multiples of some even number \(n\) and thus not coprime, so only \(a \equiv \frac{n}{2} \pmod{n}\) can be true. It is true when \(2a\) is an odd multiple of \(n\). Now the only possible value for \(n\) is \(2\) because using any other even number would imply that both \(a\) and \(b\) are divisible by \(2\) and so they are not coprime. Thus, the only possible values for \(n\) are \(1\) and \(2\).

## Wonderwice Margera solved this puzzle:

Let the numbers be \(a\) and \(b\), \(a \gt b\). Let \(c\) be a common positive divisor of \(a + b\) and \(a - b\), so let \(a + b = cx\), \(a - b = cy\) where \(x\) and \(y\) are integers. Then \(2a = c(x + y)\) and \(2b = c(x - y)\). In other words, \(c\) is a common divisor of \(2a\) and \(2b\). As \(a\) and \(b\) have no common positive factors other than \(1\), this means that \(c\) must divide \(2\). Hence, \(c\) must be \(1\) or \(2\). Both of these values are attained, for example, when \(a = 5\) and \(b = 3\).

## quasi solved this puzzle:

Let \(a\) and \(b\) be two integers coprime to each other, and let \(d = \gcd(a + b, a - b)\).

\begin{align*} & d \mid (a + b) \text{ and } d \mid (a - b) \\ & \implies d \mid (a + b) + (a - b) \text{ and } d \mid (a + b) - (a - b) \\ & \implies d \mid 2a \text{ and } d \mid 2b \\ & \implies d \mid gcd(2a, 2b) \end{align*}

But \(\gcd(2a, 2b) = 2 \cdot \gcd(a, b) = 2\), hence \(d \mid 2\).

Since \(a\) an \(b\) are coprime to each other, they can't both be even.

If \(a\) and \(b\) are both odd, then \(a + b\) and \(a - b\) are both even, hence \(d\) is even. Then, since \(d \mid 2\), it follows that \(d = 2\).

If one of \(a, b\) is odd, and the other is even, then \(a + b\) and \(a - b\) are both odd, hence \(d\) is odd. Then, since \(d \mid 2\), it follows that \(d = 1\).

Thus, assuming that the integers \(a\) and \(b\) are coprime to each other, we have the following results.

## Gnanasenthil G solved this puzzle:

Let \(a\) and \(b\) be two integers such that \(a \perp b\). It is obvious that both \(a\) and \(b\) cannot be even if \(a \perp b\).

If \(a\) or \(b\) is even and the other is odd, both \(a + b\) and \(a - b\) are odd. Then \((a + b) \perp (a - b)\). This can be proved by contradiction. Let us assume that there exists an odd positive integer \(c \gt 1\) such that \(c \mid (a + b)\) and \(c \mid (a - b)\). Then \begin{align} c k_1 & = a + b, \label{eqsum} \\ c k_2 & = a - b. \label{eqdiff} \end{align} where \(k_1\) and \(k_2\) are two distinct odd integers.

From \eqref{eqsum} and \eqref{eqdiff}, we get

\begin{align} a & = \frac{c(k_1 + k_2)}{2}, \label{eqa} \\ b & = \frac{c(k_1 - k_2)}{2}. \label{eqb} \end{align}

Since \(k_1\) and \(k_2\) are odd integers, \(k_1 + k_2\) and \(k_1 - k_2\) are even, and from \eqref{eqa} and \eqref{eqb}, we see that \(c\) is a common divisor of \(a\) and \(b\). This contradicts our assumption that \(a \perp b\). Thus, \((a + b) \perp (a - b)\).

If both \(a\) and \(b\) are odd, the possible common positive divisors of \((a + b)\) and \((a - b)\) are \(1\) and \(2\). This can be proved as follows. Let us assume that there exists a positive integer \(c \gt 2\) such that \(c \mid (a + b)\) and \(c \mid (a - b)\). Then \begin{align} c k_1 & = a + b, \label{eqsum2} \\ c k_2 & = a - b. \label{eqdiff2} \end{align} where \(k_1\) and \(k_2\) are two distinct integers.

From \eqref{eqsum2} and \eqref{eqdiff2}, we get

\begin{align} a & = \frac{c(k_1 + k_2)}{2}, \label{eqa2} \\ b & = \frac{c(k_1 - k_2)}{2}. \label{eqb2} \end{align}

If \(c\) is even, then \(\frac{c}{2}\) is a common divisor of \(a\) and \(b\). Since \(a \perp b\), \(\frac{c}{2} = 1\). Thus, \(c = 2\). If \(c\) is odd, then both \(k_1\) and \(k_2\) must be even because \((a + b)\) and \((a - b)\) are even. Therefore, both \((k_1 + k_2)\) and \((k_1 - k_2)\) are even. Thus, from \eqref{eqa2} and \eqref{eqb2} we see that \(c\) is a common divisor of \(a\) and \(b\). Since \(a \perp b\), \(c = 1\).