The largest number which divides 1288 and 2915 and leaves the remainders 1 and 8 respectively, is H and it satisfies the equation, H = 45m + 288n.
Find the value of m + n.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Relevant wiki: Bezout's identity
If 1 2 8 8 leaves a remainder of 1 when divided by H this implies
H ∣ 1 2 8 7
With a similar reasoning
H ∣ 2 9 0 7
Since H is by definition the biggest number which divides both 1 2 8 7 and 2 9 0 7
H = l c m ( 1 2 8 7 , 2 9 0 7 ) = l c m ( 3 2 ⋅ 1 1 ⋅ 1 3 , 3 2 ⋅ 1 7 ⋅ 1 9 ) = 9
We now have
4 5 m + 2 8 8 n = 9 ⟺ 5 m + 3 2 n = 1
Using the Euclidean algorithm to find g cd ( 5 , 3 2 ) and then working backwards
g cd ( 5 , 3 2 ) = g cd ( 5 , 3 2 − 6 ⋅ 5 ) = g cd ( 5 , 2 ) = g cd ( 5 − 2 ⋅ 2 , 2 ) = ( 1 , 2 )
1 = 5 − 2 ⋅ 2 = 5 − 2 ⋅ ( 3 2 − 6 ⋅ 5 ) = 1 3 ⋅ 5 − 2 ⋅ 3 2
Hence
m = 1 3 , n = − 2 ⟹ m + n = 1 1
Note:
This in fact is not completely correct, since infinitly many solutions can be generated in the following way
1 3 ⋅ 5 − 2 ⋅ 3 2 = 1
1 3 ⋅ 5 + 1 6 0 t − 2 ⋅ 3 2 − 1 6 0 t = 1
5 ( 3 2 t + 1 3 ) + 3 2 ( − 5 t − 2 ) = 1
⟹ m = 3 2 t + 1 3 , n = − 5 t − 2