Write 100 as the sum of two positive integers

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 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.

Answer 5

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'.

Answer 6

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

Answer 7

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

Answer 8

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