[nacht]

This is a rather interesting problem from a book of problems that get asked during interviews.

Find the smallest positive integer that leaves a remainder of 1 when divided by 2, a remainder of 2 when divided by 3, a remainder of 3 when divided by 4, … and a remainder of 9 when divided by 10.

Citation:

( Show Spoiler )

Heard on the Street, by Timothy Falcon Crack

[Monte314]

Uh... in that ellipsis (...) are you suggesting a "range": remainder of 4 when divided by 5, remainder of 5 when divided by 6, etc.?

[nacht]

	Originally Posted by Monte314 To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	Uh... in that ellipsis (...) are you suggesting a "range": remainder of 4 when divided by 5, remainder of 5 when didvided by 6, etc.?

Yep, exactly.

[level]

All you have to do is find the least common multiple for 2,3,4,5,6,7,8,9 and 10 and subtract one. The result is the number you're looking for.

[Monte314]

	Originally Posted by level To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	All you have to do is find the least common multiple for 2,3,4,5,6,7,8,9 and 10 and subtract one. The result is the number you're looking for.

Your answer is correct, but it is customary here to supply an attempt at a proof with a proposed solution. For example: how do we know your algorithm gives the smallest solution?

[level]

"Find the smallest positive integer that leaves a remainder of 1 when divided by 2"
Integers leaving a remainder of 1 when divided by 2 can be described by this sequence: a(n)=2n+1, where n=1,2,3...n, and a more general one for each set of integers and remainders would be b(n)=cn+d, where c is the denominator and d the remainder. With these, we are searching for numbers that are amongst the solutions of every sequence. The smallest of them is the answer to the question.

First, sorry for the awful description- I'm a non-native English speaker, and this is the first time in my life I've attempted writing anything even vaguely mathematical in a language different than Polish. I'm not even sure if I got all of the terminology right.

Second, that's as far as I got with a more "elegant" solution, and ran out of ideas what to do next. If I were to do a formal proof, I'd probably go more into that direction. I don't have much more though, sorry.

[themuzicman]

( Show Spoiler )

Leaving the greatest possible remainder means having a multiple of a given number less one. Thus, 8 gives us the greatest possible remainder for 3, because 3*3=9, and 8=9-1., 8/3 gives the greatest possible remainder of 2.

So, to have the greatest possible remainder for all numbers from 2-10, one must find the least common multiple for each of these numbers, and the easiest way to do this is to break them down into their prime factors.

Thus, we have the prime numbers: 2,3,5,7 and any numbers that require multiple primes, namely 8 and 9, so we add 2,2,3 to the list.

Multiply these together, and we get 2520.
Subtract one, and we get 2519.

QED

[Monte314]

Originally Posted by level To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.

"Find the smallest positive integer that leaves a remainder of 1 when divided by 2" Integers leaving a remainder of 1 when divided by 2 can be described by this sequence: a(n)=2n+1, where n=1,2,3...n, and a more general one for each set of integers and remainders would be b(n)=cn+d, where c is the denominator and d the remainder. With these, we are searching for numbers that are amongst the solutions of every sequence. The smallest of them is the answer to the question. First, sorry for the awful description- I'm a non-native English speaker, and this is the first time in my life I've attempted writing anything even vaguely mathematical in a language different than Polish. I'm not even sure if I got all of the terminology right. Second, that's as far as I got with a more "elegant" solution, and ran out of ideas what to do next. If I were to do a formal proof, I'd probably go more into that direction. I don't have much more though, sorry.

Please don't feel bad; we all understand the difficulties of expressing sophisticated ideas in a second language... and thanks for the update.

[Reivan]

Couldn't you also use the chinese remainder theorem to find the answer?

[K27]

Skipping steps could cause a disaster! My idea was correct but the number was wrong. Good that I checked!
To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.


[HIDE="spoiler"]The number is 2*2*2*3*3*5*7-1.
The LCM of 2, 3, ..., 10 is 2*2*2*3*3*5*7 = 2520, as we see all the factors 2 to 10 are all in it. So this number, let it be X, can be written as X = 2*N2 = 3*N3 = ... = 10*N10 for some Ni belongs to natural numbers for i=2,3,...,10. X-1 will gives us X = 2*(N2 - 1) + 1 = 3*(N3 - 1) + 2 = ... = 10*(N10 - 1) + 9, with the desired remainder when the divisors are 2, 3, ..., 10.
Calculation shows that the answer (X) is 2519.

We have 2519 = 2*1259 + 1 = 3*839 + 2 = 4*629 + 3 = 5*503 + 4 = 6*419 + 5 = 7*359 + 6 = 8*314 + 7 = 9*279 + 8 = 10*251 + 9 ... (*).



To prove that this is the smallest number, I proceed by contradiction.

Let assume there is a positive integer Y that is smaller than 30239 which will satisfy the requirement that the remainder is one less than the divisor for 2, 3, ..., 10. So,

Y = 2*K2 + 1 = 3*K3 + 2 = 4*K4 + 3 = ... = 10*K10 + 9 ... (1) for some integers Ki, i = 2,3,...,10.

We may write 30239 = m + Y ... (2), where m > 0 and m is an integer.

Substitute (*) and (1) into (2), we will get an array of equality as following:
2*1259 + 1 = 2*K2 + 1 + m
3*839 + 2 = 3*K3 + 2 + m
4*629 + 3 = 4 * K4 + 3 + m
...
10*251 + 9 = 10*K10 + 9 + m

Then,
2*1259 = 2*K2 + m
3*839 = 3*K3 + m
4*629 = 4 * K4 + m
...
10*251 = 10*K10 + m

This tells us that m is divisible by 2, 3, 4, ..., 10. This follows that m is the LCM of 2, 3, 4, ..., 10. And this is 2520.

So substitute this into (2), we get 2519 = 2520 + Y, Y = -1. This violates the assumption that Y is a positive integer.[/HIDE]

[Monte314]

@Reivan: Yep... Chinese Remainder Theorem is the obvious approach. But there's no fun in that!

Notice that the demonstration by K27 can be viewed as a special case of the CRT... she is pretty impressive!

[K27]

I used CRT? I was not aware of that.
I will go research about that.

--Edit--
I googled CRT and I understood what I have done that resembles the theorem. This theorem is interesting, and me being a Chinese speaker makes the reading of the original text the more interesting. But I probably need more time if I need a formal CRT version. Before that I need to understand the whole thing in and out!

The maths world is just so big...

[Monte314]

Here is how I describe the CRT for my students:

You have a race track with N horses all lined up at the starting gate. Each one is allowed to start at the stroke of a second, but they all start at different times. Also, they are all running at different speeds, but the number of seconds required for each horse to complete a lap is a positive integer. Under what conditions will there be a future time at which the horses are all lined up at the starting line? If these conditions are satisfied, what is the earliest such time?

[K27]

The different times they start are the remainders.
O_o CRT now looks a whole lot easier.

[Monte314]

Yep; the different start times give the remainders!

I find that tangible analogies like this not only help people remember the components of a theorem, but often provide some insights into why it's true and how to get started on a proof.

[K27]

x ≡ y (mod n_1) and x ≡ y (mod n_2) and ... and x ≡ y (mod n_i) ⇔ x ≡ y (mod N), N = (n_1)(n_2)...(n_i) and y is congruent to the remainder of x with respect to each x_i...

I find ⇐ easy to prove. The other direction is still a puzzle to me. Need more time to think about.

I've just realised that I've got a lot to think about at hand. lol

[nacht]

( Show Spoiler )

We basically have many correct answers so far. It basically boils down to that there are two major approaches you can use: Recognizing that X+1 = lcm(.) and the Chinese Remainder Theorem. Neither are especially difficult, but the key is getting to the point where you can recognize that is what is going on.

Thank you Monte for handling the explanations on this one ^_^