Every integer greater than $0$ can be expressed as a sum of $a$'s and $b$'s, if and only if $a$ and $b$ have no common factor

Question

Every integer greater than $0$ can be expressed as a sum of $a$'s and $b$'s,
if and only if $a$ and $b$ have no common factor.

PROOF:

Consider the case $a=5$, $b=13$. First, let's find how to express $1$ as a sum of $a$'s and $b$'s.

$$5+5+5+5+5+1=13+13$$ $$5(5)+1=2(13)$$ $$1 =2(13)-5(5)$$

$$13+13+13+1=5+5+5+5+5+5+5+5$$ $$3(13)+1=8(5)$$ $$1=8(5)-3(13)$$

Since we can express $1$ as a sum of $a$'s and $b$'s, and since all integers $n>0$ can be express as a sum of $1$'s, then every integer $n>0$ can be written as a sum of $a$'s and $b$'s.

Now about “if and only if $a$ and $b$ have no common factor”? This is because if $a$ and $b$ share a common prime factor, there is no real solution to:

$$1=ax+by$$ $$ax=1-by$$ $$x=\frac{1}{a}\left(1-by\right)$$ $$x=\frac{1}{a}-\frac{by}{a}$$

In the last equation, we know that if $b$ and $a$ have a common factor, $\frac{b}{a}$ can be reduced, this is why $\left(by\mod a\neq1\right)$, which is required to compensate $\frac{1}{a}$ in order to have integer solutions.

Questions:

1: Is my proof correct ?
2: In the last part, is there an more simple way to explain why $a$ and $b$ can't share a common prime factor ?
3: I haven't found anything on this subject, so i would appreciate if somebody could give reference of similar work. I'm mostly interested in the fact that these pairs (a,b) can be prime/prime, prime/non-prime, non-prime/non-prime, because it is related to research on Goldbach's conjecture.

Answer 1

To prove an "if and only if" statement, you have to prove two parts:

1. If $A$ then $B$
2. If not $A$ then not $B$

In your case, $A$ is the statement "$a$ and $b$ have no common factor" and $B$ is the statement "every integer greater than $0$ can be expressed as a sum of $a$s and $b$s".

Part (2) is straightforward. If $a$ and $b$ have a common factor - let's call it $d$ - then any sum of $a$s and $b$s will also have a factor $d$. More formally, if $a=md$ and $b=nd$ then if $c=ka+lb$ we have

$c=k(md) + l(nd) = (km+ln)d$

For Part (1) then you have found a good strategy. If we can show that there are integers $k$ and $l$ such that $ka+lb=1$ then we can construct a sum of $a$s and $b$s that equals any positive integer $c$ as follows:

$c = 1c = (ka+lb)c = (kc)a + (lc)b$

In fact $c$ does not even have to be positive - we can use the same method for any non-zero integer $c$. And we can even include $0$ as long as we allow $0a + 0b$ to be a valid sum of $a$s and $b$s.

So now you need to prove the following statement:

"If $a$ and $b$ have no common factor then there are integers $k$ and $l$ such that $ka + lb = 1$"

This is a special case of Bezout's identity, and is usually proved using the Euclidean division algorithm. This is all interesting stuff, but you will find it is covered in any textbook on elementary number theory.