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×11+8×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

From Bezout’s Lemma, note that since gcd(7,11)=1, which divides 100, there exists x,yZ 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,47m), where mZ. Since we are looking for positive integers as solutions, we need 8+11m>0 and 47m>0, which gives us 811<m<47. 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
11=7(1)+44=117(1)7=4(1)+33=74(1)3=7(117(1))(1)=27114=3(1)+11=43(1)1=(117(1))(2711)1=11273
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).

Attribution
Source : Link , Question Author : Lanner , Answer Author : Adhvaitha

Leave a Comment