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

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

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

The only integer in this range is $n=28$, which again gives $(x,y) = (8,4)$.