South African Mathematical Olympiad Third Round

We may assume that $a$, $b$, $c$ are all positive, since if $a$, $b$, $c$ are all positive, and $\gcd(a + kb, c) = \gcd(a, b, c)$ for some integer $k$, then we immediately have $\gcd(-a + (-k)b, \pm c) = \gcd(-a + k(-b), \pm c) = \gcd(a + (-k)(-b), \pm c) = \gcd(\pm a, \pm b, \pm c)$. Moreover, if at least one of $a$, $b$ and $c$ is equal to $1$, then the result follows immediately: if $a = 1$ or $c = 1$, choose $k = 0$; otherwise, if $b = 1$, choose $k = 1 - a$. In all these cases, $\gcd(a + kb, c) = \gcd(a, b, c) = 1$.

Henceforth, assume that all of $a$, $b$ and $c$ are greater than $1$. This implies that there is a list of prime numbers $p_1, p_2, \dots, p_n$ and non-negative integers $\alpha_i, \beta_i, \gamma_i$, $i = 1, 2, \dots, n$, such that
$$a = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_n^{\alpha_n}$$
$$b = p_1^{\beta_1} p_2^{\beta_2} \cdots p_n^{\beta_n}$$
$$c = p_1^{\gamma_1} p_2^{\gamma_2} \cdots p_n^{\gamma_n}.$$
Let us first assume that $\gcd(a, b, c) = 1$. This implies that, for each $i \in \{1, 2, \dots, n\}$, not all three of $\alpha_i, \beta_i$ and $\gamma_i$ are positive. We may also assume that, for each $i \in \{1, 2, \dots, n\}$, not all three of $\alpha_i, \beta_i$ and $\gamma_i$ are $0$ (otherwise we could simply discard the primes $p_i$ for which this happens). We now call a prime $p_i$ a one-prime if exactly one of $\alpha_i, \beta_i$ and $\gamma_i$ is positive. Likewise, we call a prime $p_i$ a two-prime if exactly two of $\alpha_i, \beta_i$ and $\gamma_i$ are positive. Let $E = \{p_{i_1}, p_{i_2}, \dots, p_{i_t}\}$ be the complete list of one-primes among $p_1, p_2, \dots, p_n$. If there are no one-primes in this list, put $E = \emptyset$. Let
$$k = \begin{cases} p_{i_1} p_{i_2} \cdots p_{i_t} & \text{if } E \neq \emptyset \\ 1 & \text{if } E = \emptyset. \end{cases}$$
We show that, for this $k$, $\gcd(a + kb, c) = \gcd(a, b, c) = 1$.
Since $\gcd(a + kb, c)$ is a divisor of $c$, the only possible way that $\gcd(a + kb, c) > 1$ is that it is divisible by at least one of $p_1, p_2, \dots, p_n$. We show that this is not the case.

Firstly, consider any $p_{i_j} \in E$ (if $E \neq \emptyset$). For the triple $(\alpha_{i_j}, \beta_{i_j}, \gamma_{i_j})$ there are three possibilities:

I. $(\alpha_{i_j}, \beta_{i_j}, \gamma_{i_j}) = (\alpha_{i_j}, 0, 0)$, with $\alpha_{i_j} > 0$. Here, $p_{i_j}$ does not divide $c$.

II. $(\alpha_{i_j}, \beta_{i_j}, \gamma_{i_j}) = (0, \beta_{i_j}, 0)$, with $\beta_{i_j} > 0$. Here, again, $p_{i_j}$ does not divide $c$.

III. $(\alpha_{i_j}, \beta_{i_j}, \gamma_{i_j}) = (0, 0, \gamma_{i_j})$, with $\gamma_{i_j} > 0$. Here, $p_{i_j}$ does not divide $a + kb$ (where $k = p_{i_1}p_{i_2}\cdots p_{i_t}$).

So $\gcd(a+kb, c)$ is not divisible by any of the one-primes.

Secondly, let $p_r$ denote any of the two-primes. For the triple $(\alpha_r, \beta_r, \gamma_r)$ there are three possibilities:

I'. $(\alpha_r, \beta_r, \gamma_r) = (\alpha_r, \beta_r, 0)$, with $\alpha_r, \beta_r > 0$. Here, $p_r$ does not divide $c$.

II'. $(\alpha_r, \beta_r, \gamma_r) = (\alpha_r, 0, \gamma_r)$, with $\alpha_r, \gamma_r > 0$. Here, $p_r$ does not divide $a+kb$ (recall that $k$ is not divisible by $p_r$).

III'. $(\alpha_r, \beta_r, \gamma_r) = (0, \beta_r, \gamma_r)$, with $\beta_r, \gamma_r > 0$. Here, again, $p_r$ does not divide $a+kb$.

It follows that $\gcd(a+kb, c) = 1 = \gcd(a, b, c)$.

Finally, if $\gcd(a, b, c) = d > 1$, then $\gcd(\frac{a}{d}, \frac{b}{d}, \frac{c}{d}) = 1$, and from the above, there exists an integer $k$ such that $\gcd(\frac{a}{d} + k \cdot \frac{b}{d}, \frac{c}{d}) = 1 = \gcd(\frac{a}{d}, \frac{b}{d}, \frac{c}{d})$. Multiplying both sides by $d$ gives $\gcd(a + kb, c) = d = \gcd(a, b, c)$, and we are done.

As in Solution 1, we may assume that $\gcd(a, b, c) = 1$. By Dirichlet's Theorem, the sequence $s_n = a/\gcd(a, b) + n \cdot b/\gcd(a, b)$, $n \in \mathbb{N}$, contains infinitely many primes. Let $p = a/\gcd(a, b) + k \cdot b/\gcd(a, b)$, $k \in \mathbb{N}$, be prime, with $p > c$. Then, as $\gcd(a, b)$ and $c$ are relatively prime,
$$1 = \gcd(p, c) = \gcd(p \cdot \gcd(a, b), c) = \gcd(a + kb, c).$$