The 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=\varnothing$. Let $$k=\{\begin{array}{ll}{p}_{i_1}{p}_{i_2}\cdots p_{i_t}& \text{if }E\ne \varnothing \\ 1& \text{if }E=\varnothing .\end{array}$$ 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\ne \varnothing$). 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.

---

Alternative solution.

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).$$