An Euler Question

[mc3003]

I have a question here:

Find the lowest possible integer whose remainder is 10 when it is divided by 11, 12 when it is divided by 13, and 16 when it is divided by 17.

[laiusergiu]

Let the lowest possible integer, which satisfies these conditions, be denoted by n:

Let's translate the statements into mathematical relations (where a,b,c are integers)
n = 11a + 10 = 11a+11-1 = 11(a+1) - 1
n = 13b + 12 = 13b+13-1 = 13(b+1) - 1
n = 17c + 16 = 17c+17-1 = 17(c+1) - 1

Since n = 11(a+1) - 1 --> n+1 = 11(a+1) i.e (n+1) is a multiple of 11
Since n = 13(b+1) - 1 --> n+1 = 13(b+1) i.e (n+1) is a multiple of 13
Since n = 17(c+1) - 1 --> n+1 = 17(a+1) i.e (n+1) is a multiple of 17

The smallest positive number that is a multiple of 11, 13, and 17 is 11*13*17=2431 --> n+1=2431 -->n=2430

[mc3003]

Thanks honey ^^

[ranjithsmiles]

This is one of the LCM Model.
Any number ,which when divided by p,q or r leaving respective remainders of s,t and u
where (P-s)=(q-t)=(r-u)=V(say),
it will be of the form
k(LCM of p,q and r)-v,
the smallest such no will be obtained by substituting k=1

In this case ,
v=1
l.c.m( 11,13,17) = 2431
k=1
Ans: 2431-1 = 2430

[mithunsam]

If you look at the divisors and reminders...
11-10 = 1
13-12 = 1
17-16 = 1

That means, we need to subtract 1 from the resulting number.

Now the smallest possible multiple of 11, 13, & 17 (let us say N) is nothing but the multiplications of these 3 numbers (because, all these numbers are prime).

Therefore N = 11*13*17 = 2431

Now, look at the sentence, which I highlighted above.

To get our final answer, subtract 1 from 2431 => 2430.

[jnelson0612]

Great minds at work in this thread!

Of course, I need to ask what is the original source of this problem?