# Write 100 as the sum of two positive integers

Write $100$ as the sum of two positive integers, one of them being a multiple of $7$, while the other is a multiple of $11$.

Since $100$ is not a big number, I followed the straightforward reasoning of writing all multiples up to $100$ of either $11$ or $7$, and then finding the complement that is also a multiple of the other. So then $100 = 44 + 56 = 4 \times 11 + 8 \times 7$.

But is it the smart way of doing it? Is it the way I was supposed to solve it? I'm thinking here about a situation with a really large number that turns my plug-in method sort of unwise.

• I think you want to reword this 'Scalable algorithm to write N as the sum of two positive integers, for large N' – smci May 4 '15 at 7:13
• This seems like a rather badly designed exercise since, looking at the answers, it's clear that just checking multiples of 7 and 11 is by far the simplest way of solving it. I once saw an exam question that made things much clearer by saying the equivalent of, "Proceed as if 100 is a very large number and you do not know that 100=44+56." – David Richerby May 4 '15 at 21:07

From Bezout's Lemma, note that since $\gcd(7,11) = 1$, which divides $100$, there exists $x,y \in \mathbb{Z}$ such that $7x+11y=100$.

A candidate solution is $(x,y) = (8,4)$.

The rest of the solution is given by $(x,y) = (8+11m,4-7m)$, where $m \in \mathbb{Z}$. Since we are looking for positive integers as solutions, we need $8+11m > 0$ and $4-7m>0$, which gives us $-\frac8{11}<m<\frac47$. This means the only value of $m$, when we restrict $x,y$ to positive integers is $m=0$, which gives us $(x,y) = (8,4)$ as the only solution in positive integers.

If you do not like to guess your candidate solution, a more algorithmic procedure is using Euclid' algorithm to obtain solution to $7a+11b=1$, which is as follows.

We have \begin{align} 11 & = 7 \cdot (1) + 4 \implies 4 = 11 - 7 \cdot (1)\\ 7 & = 4 \cdot (1) + 3 \implies 3 = 7 - 4 \cdot (1) \implies 3 = 7 - (11-7\cdot (1))\cdot (1) = 2\cdot 7 - 11\\ 4 & = 3 \cdot (1) + 1 \implies 1 = 4 - 3 \cdot (1) \implies 1 = (11-7 \cdot(1)) - (2\cdot 7 - 11) \cdot 1 = 11 \cdot 2-7 \cdot 3 \end{align} This means the solution to $7a+11b=1$ using Euclid' algorithm is $(-3,2)$. Hence, the candidate solution $7x+11y=100$ is $(-300,200)$. Now all possible solutions are given by $(x,y) = (-300+11n,200-7n)$. Since we need $x$ and $y$ to be positive, we need $-300+11n > 0$ and $200-7n > 0$, which gives us $$\dfrac{300}{11} < n < \dfrac{200}7 \implies 27 \dfrac3{11} < n < 28 \dfrac47$$ The only integer in this range is $n=28$, which again gives $(x,y) = (8,4)$.

• This looks like I was looking for, but I didn't quite get why you summed $11m$ to the $x$ and $-7m$ to the $y$, since $x$ is supposed to be a multiple of $7$, instead of $11$. – Lanner May 3 '15 at 23:31
• @Lanner Check what happens when you plug in $x=8+11m$ and $y=4-7m$ into the original equation. – Leg May 3 '15 at 23:32
• While $x,y$ are guaranteed to exist from Bezout's Lemma, they are not guaranteed to be positive. Therefor: Bezout's Lemma provides no information about whether this particular problem has a solution. What logic led to $(8,4)$ being your starting point for the search? – Andrew Coonce May 4 '15 at 14:15
• @AndrewCoonce A more algorithmic procedure to obtain solutions to $ax+by=1$ is Euclid's algorithm to compute the gcd. However, in some cases such as this a candidate solution can be guessed easily. – Leg May 4 '15 at 15:04
• @user17762 The only reason I asked for clarification is because the OP already had a natural method for determining it for this case and was looking for a general method. Guessing just because the numbers played nicely here didn't seem like a solution, but your comment clarifies the general solution for me. – Andrew Coonce May 4 '15 at 16:38

An effort to avoid any enumeration or hiding an inductive leap to the answer.

$7a + 11b = 100: a,b \in N$

$11b \leq 100 - 7 = 93$

$\implies 1 \leq b \leq 8$

$7(a+b) = 100 - 4b$

$\implies 100 - 4b \equiv 0 \mod 7$

$\implies 25 - b \equiv 0 \mod 7$

$\implies b \equiv 25 \mod 7$

$\implies b \equiv 4 \mod 7$

$\implies b = 4 + 7n$

We know $1 \leq b \leq 8$.

So we have $b \equiv 25 \mod 7$, so $b = 4$ and hence $a = 8$.

• This works, but it relies on the accidental fact that $11-7$ is a factor of $100$. If I changed it to $103$ this method wouldn't work. The reason is that in general we need the multiplicative inverse of $11$ modulo $7$ or vice versa, for that particular step. – user21820 May 5 '15 at 12:48

But is it the smart way of doing it?

You are asked to find a and b so that $7a+11b=100\iff7(a+b)+4b=100\iff$

$4\Big[(a+b)+b\Big]+3(a+b)=100\iff3\Big\{\Big[(a+b)+b\Big]+(a+b)\Big\}+\Big[(a+b)+b\Big]=$ $100$.

But $100=99+1=3\cdot33+1$, so $a+2b=1\iff2a+4b=2$, and $2a+3b=33$. It follows
that $b_0=-31$ and $a_0=63$ is one solution. But, then again, so are all numbers of the form $a_k=63-11k$ and $b_k=-31+7k$, with $k\in$ Z. All we have to do now is pick one pair whose components are both positive. The first equation implies $k<6$, and the latter $k>4$.

Since $\operatorname{gcd}(7,11)=1$ , you can find $a,b \in \mathbb Z$ with $7a+11b=1$. Now multiply both sides of the equation by $100$ to get one (and so all possible) results:

$$700a+1100b=100$$

Once you have a solution for $700a+1100b=100$, you have all solutions:

$$700(a+11k)+1100(b-7k)=100$$

You can then find $k$ so that both coefficients are positive.

• It must be the sum of two positive integers, so a,b > 0. – Lanner May 3 '15 at 23:00
• @Gary. Bezout coefficients are not guaranteed to be positive. – MathMajor May 3 '15 at 23:02
• The Bezout coefficients for positive integers are guaranteed to have different signs. – Ittay Weiss May 3 '15 at 23:04
• But once we know any $a,b$, we can find solutions $a',b' : 700a'+1100b'=100$ with $a',b' >0$. The Bezout coefficients generate all solutions; they are not the unique solutions. – Gary. May 3 '15 at 23:07
• @MathMajor: Thanks, you know what those fake internet points will do to you ; ). – Gary. May 3 '15 at 23:34

While certainly not the ideal solution, this problem is certainly in the realm of Integer Programming. As plenty of others have pointed out, there are more direct approaches. However, I suspect ILP solvers would operate quite efficiently in your case, and requires less 'thought capital'.

$7a+11b=100$ so modding both sides by $11$ you get $11 \mid (7a-1)$. Let $11a'=7a-1$. Then the problem is transformed to finding $a',b$ such that $a'+b=9$ and $7 \mid (11a'+1)$, which (in my opinion) is somewhat easier to test for.

$7x+11y=100$
$7x=100-11y$
$x=\frac{100-11y}7=14-2y+\frac{2+3y}7$
$a=\frac{2+3y}7$
$7a=2+3y$
$3y=-2+7a$
$y=\frac{-2+7a}3=-1+2a+\frac{1+a}3$
$b=\frac{1+a}3$
$3b=1+a$
$a=3b-1$
$y=\frac{-2+7(3b-1)}3=\frac{-9+21b}3=-3+7b$
$x=\frac{100-11(-3+7b)}7=\frac{133-77b}7=19-11b$
$\begin{matrix} x\gt 0&\to&19-11b\gt 0&\to&11b\lt 19&\to&b\lt\frac{19}{11}&\to&b\le 1&\\ &&&&&&&&&b=1\\ y\gt 0&\to&-3+7b\gt 0&\to&7b\gt 3&\to&b\gt\frac37&\to&b\ge 1&\\ \end{matrix}$
$1$ is the only integral value of $b$ for which both $x$ and $y$ yield positive values, as required by the problem. So, $x=8$ and $y=4$.

Since positive numbers are required, you could do something like this, inspired by the so-called chicken nugget monoid. This method is only viable if one of the numbers is sufficiently small; Euclid's algorithm is much better for big numbers, e.g., writing 2165434 in terms of positive multiples of 97 and 103.

Note the following:

• $11\cdot1=4\mod 7$
• $11\cdot2=1\mod 7$
• $11\cdot3=5\mod 7$
• $11\cdot4=2\mod 7$
• $11\cdot5=6\mod 7$
• $11\cdot6=3\mod 7$
• $11\cdot7=0\mod 7$

So, to find a positive solution for $N$ in terms of $7$ and $11$, find the value of $N$ (mod $7$), subtract the appropriate multiple of $11$ from $N$, and divide the result by $7$. Now you have positive integers $m$ and $n$ such that $7m+11n=N$.

Of course, if $m$ is larger than 11, the solution is not unique, but each $N>77$ has at least one solution.

## $N\leq 77$ with positive solutions (complete list)

• $18=11(1)+7(1)$
• $25=11(1)+7(2)$
• $29=11(2)+7(1)$
• $32=11(1)+7(3)$
• $36=11(2)+7(2)$
• $39=11(1)+7(4)$
• $40=11(3)+7(1)$
• $43=11(2)+7(3)$
• $46=11(1)+7(5)$
• $47=11(3)+7(2)$
• $50=11(2)+7(4)$
• $51=11(4)+7(1)$
• $53=11(1)+7(6)$
• $54=11(3)+7(3)$
• $57=11(2)+7(5)$
• $58=11(4)+7(2)$
• $60=11(1)+7(7)$
• $61=11(3)+7(4)$
• $62=11(5)+7(1)$
• $64=11(2)+7(6)$
• $65=11(4)+7(3)$
• $67=11(1)+7(8)$
• $68=11(3)+7(5)$
• $69=11(5)+7(2)$
• $71=11(2)+7(7)$
• $72=11(4)+7(4)$
• $73=11(6)+7(1)$
• $74=11(1)+7(9)$
• $75=11(3)+7(6)$
• $76=11(5)+7(3)$

Use the Extended Euclidean Algorithm to solve $$7x+11y=100$$ Using the implementation detailed in this answer $$\begin{array}{r} &&1&1&1&3\\\hline 1&0&1&-1&\color{#C00000}{2}&\color{#0000F0}{-7}\\ 0&1&-1&2&\color{#00A000}{-3}&\color{#E0A000}{11}\\ 11&7&4&3&1&0\\ \end{array}$$ we get that $$(\color{#00A000}{-3})\,7+(\color{#C00000}{2})\,11=1$$ multiply by $100$ and use the last column from the algorithm to get the general answer, we get $$(-300+\color{#E0A000}{11}k)\,7+(200\color{#0000F0}{-7}k)\,11=100$$ set $k=28$ (the only $k$ that works) to make the coefficients positive, we get that $$(8)\,7+(4)\,11=100$$

Larger than $\boldsymbol{100}$

Suppose we want to write $1000000$ as a sum of a multiple of $7$ and a multiple of $11$. We can use the result of the algorithm above. That is $$(-3000000+11k)7+(2000000-7k)11=1000000$$ We can use any $272728\le k\le 285714$ to make both coefficients positive.

$k=272728$ gives $$(8)\,7+(90904)\,11=1000000$$ $k=285714$ gives $$(142854)\,7+(2)\,11=1000000$$

## protected by Zev ChonolesMay 10 '15 at 5:58

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).