m + n ? m + n?

Number Theory Level pending

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.

10 13 15 11

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.

1 solution

Marco Brezzi
Aug 20, 2017

Relevant wiki: Bezout's identity

If 1288 1288 leaves a remainder of 1 1 when divided by H H this implies

H 1287 H\mid 1287

With a similar reasoning

H 2907 H\mid 2907

Since H H is by definition the biggest number which divides both 1287 1287 and 2907 2907

H = l c m ( 1287 , 2907 ) = l c m ( 3 2 11 13 , 3 2 17 19 ) = 9 H=lcm(1287,2907)=lcm(3^2\cdot 11\cdot 13,3^2\cdot 17\cdot 19)=9

We now have

45 m + 288 n = 9 5 m + 32 n = 1 45m+288n=9 \iff 5m+32n=1

Using the Euclidean algorithm to find gcd ( 5 , 32 ) \gcd(5,32) and then working backwards

gcd ( 5 , 32 ) = gcd ( 5 , 32 6 5 ) = gcd ( 5 , 2 ) = gcd ( 5 2 2 , 2 ) = ( 1 , 2 ) \begin{aligned} \gcd(5,32)&=\gcd(5,32-6\cdot 5)\\ &=\gcd(5,2)\\ &=\gcd(5-2\cdot 2,2)\\ &=(1,2) \end{aligned}

1 = 5 2 2 = 5 2 ( 32 6 5 ) = 13 5 2 32 \begin{aligned} 1&=5-2\cdot 2\\ &=5-2\cdot(32-6\cdot 5)\\ &=13\cdot 5-2\cdot 32 \end{aligned}

Hence

m = 13 , n = 2 m + n = 11 m=13,n=-2\Longrightarrow m+n=\boxed{11}


Note:

This in fact is not completely correct, since infinitly many solutions can be generated in the following way

13 5 2 32 = 1 13\cdot 5-2\cdot 32=1

13 5 + 160 t 2 32 160 t = 1 13\cdot 5 +160t-2\cdot 32-160t=1

5 ( 32 t + 13 ) + 32 ( 5 t 2 ) = 1 5(32t+13)+32(-5t-2)=1

m = 32 t + 13 , n = 5 t 2 \Longrightarrow m=32t+13,n=-5t-2

Thanks for the solution :)

Ojasee Duble - 3 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...