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

$\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$ – Leg 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$ – Leg 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$.

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

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

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

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

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

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

$\endgroup$

protected by Zev Chonoles May 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).

Would you like to answer one of these unanswered questions instead?

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