1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Familiare with Bezout's lemma? $\endgroup$ – Vera Jul 20 '18 at 10:49
  • $\begingroup$ i wasn't, but it sure looks very similar, thanks for your help ! $\endgroup$ – François Huppé Jul 20 '18 at 10:53
  • 1
    $\begingroup$ @peter, thanks for your help, i didnt mentionned it but of course, to avoid using negative integers x, y, we need $n > ab-a-b$ $\endgroup$ – François Huppé Jul 20 '18 at 11:10
  • 1
    $\begingroup$ @peter, regarding Goldbach's conjecture, this is just a small part of a project i've been working on. I am not a professional mathematician, i'm a developer, and i'm passionate about math! so i know it is very unlikely for me to find a proof, so i've been working on the problem only on surface, but from A LOT of different angles, some very weird approach. Hundreds of hours of fun i've been having instead of playing video games :) In a couple of weeks i'll publish a website on the subject, with creatives approach ideas, computation tools, complete historical data, etc.. $\endgroup$ – François Huppé Jul 20 '18 at 11:45
  • 1
    $\begingroup$ @peter, i know, as gandalf says, i missed this part: "If a and b have no common factor then there are integers k and l such that ka+lb=1" $\endgroup$ – François Huppé Jul 20 '18 at 11:47
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks very usefull $\endgroup$ – François Huppé Jul 20 '18 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.