33
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I think you want to reword this 'Scalable algorithm to write N as the sum of two positive integers, for large N' $\endgroup$ – smci May 4 '15 at 7:13
  • $\begingroup$ 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." $\endgroup$ – David Richerby May 4 '15 at 21:07
37
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Lanner May 3 '15 at 23:31
  • $\begingroup$ @Lanner Check what happens when you plug in $x=8+11m$ and $y=4-7m$ into the original equation. $\endgroup$ – Adhvaitha May 3 '15 at 23:32
  • 1
    $\begingroup$ 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? $\endgroup$ – Andrew Coonce May 4 '15 at 14:15
  • 1
    $\begingroup$ @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. $\endgroup$ – Adhvaitha May 4 '15 at 15:04
  • 1
    $\begingroup$ @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. $\endgroup$ – Andrew Coonce May 4 '15 at 16:38
11
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user21820 May 5 '15 at 12:48
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It must be the sum of two positive integers, so a,b > 0. $\endgroup$ – Lanner May 3 '15 at 23:00
  • $\begingroup$ @Gary. Bezout coefficients are not guaranteed to be positive. $\endgroup$ – MathMajor May 3 '15 at 23:02
  • $\begingroup$ The Bezout coefficients for positive integers are guaranteed to have different signs. $\endgroup$ – Ittay Weiss May 3 '15 at 23:04
  • $\begingroup$ 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. $\endgroup$ – Gary. May 3 '15 at 23:07
  • 1
    $\begingroup$ @MathMajor: Thanks, you know what those fake internet points will do to you ; ). $\endgroup$ – Gary. May 3 '15 at 23:34
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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)$
| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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