Suppose we want to find all non-negative integers $x$ and $y$ that satisfy the equation

$$
7 x+11 y=154
$$

If we only use the fact that $7 x \leq 154$ implies $x \leq 22$ and test the possibilities, we will perform 23 case tests! On the other hand, we can rewrite the equation as

$$
11 y=154-7 x=7(22-x)
$$

Notice that 11 divides $7(22-x)$, but has no common factors with 7. Consequently, 11 is a divisor of $22-x$. Since $22-x \leq 22$, it suffices to test $x=0, x=11$ or $x=22$ to find the three solutions $(x, y)=(0,14),(11,7)$ or $(22,0)$ with only three case tests.

(a) Find all pairs $(m, n)$ of non-negative integers that satisfy the equation

$$
5 m+8 n=120
$$

(b) Let $a, b$ and $c$ be positive integers with $c>1$ such that

$$
\frac{1}{a}+\frac{1}{b}=\frac{1}{c}
$$

Prove that at least one of the numbers $a+c$ or $b+c$ is a composite number, i.e., has some divisor greater than 1 and less than itself.
Solution

a) We can rewrite the equation as

$$
\begin{aligned}
8 n & =120-5 m \\
& =5(24-m)
\end{aligned}
$$

We see that 8 divides the right-hand side and has no common factor with 5. Consequently, \(24-m\) must be a multiple of 8. Knowing that 24 is a multiple of 8, we conclude that \(m\) is a multiple of 8 between 0 and 24. Therefore, the solutions to the equation are \((m, n) = (0,15), (8,10), (16,5)\) or \((24,0)\).

b) If \(a\) and \(c\) have a common factor \(d > 1\), then \(d\) is a divisor of \(a+c\) greater than 1 and less than \(a+c\). We can conclude that \(a+c\) is composite. Similarly, if \(b\) and \(c\) have a common factor, then \(b+c\) is a composite number. On the other hand, suppose \(c\) has no common factors with either \(a\) or \(b\). We can develop the given equation as follows:

$$
\begin{aligned}
\frac{1}{a}+\frac{1}{b} & =\frac{1}{c} \\
\frac{a+b}{a b} & =\frac{1}{c} \\
c(a+b) & =a b
\end{aligned}
$$

This tells us that \(c\) is a divisor greater than 1 of the product \(ab\) that has no common factors with the product \(ab\). This is not possible. Therefore, one of the two cases above must occur, and we conclude that at least one of the numbers \(a+c\) or \(b+c\) is composite.