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,y∈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∈Z. Since we are looking for positive integers as solutions, we need 8+11m>0 and 4−7m>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)+4⟹4=11−7⋅(1)7=4⋅(1)+3⟹3=7−4⋅(1)⟹3=7−(11−7⋅(1))⋅(1)=2⋅7−114=3⋅(1)+1⟹1=4−3⋅(1)⟹1=(11−7⋅(1))−(2⋅7−11)⋅1=11⋅2−7⋅3
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