A number theory problem by Lee Wall

Number Theory Level 3

Let $S$ be the set of integers that leave a remainder of $1$ when divided by $2$ , a remainder of $2$ when divided by $3$ , and a remainder of $3$ when divided by $4$ . How many integers in the interval $[0, 10^{4}]$ belong to $S$ ?

The answer is 833.

1 solution

Kartik Prabhu
Jun 15, 2014

Using the given information, we can see that any number following the given conditions can be written as:

$2x - 1$

$3y - 1$

$4z - 1$

Now, bearing in mind that these are all different ways of representing the same number, we can also see that

$2x = 3y = 4z$

(Imagine forming an equation, and then adding a one to both sides).

At this point, we can see that in order for a number to satisfy the conditions of the question, it must be exactly $1$ less than the lowest common multiple of $2, 3, 4 = 12$ .

So we just need to find out how many multiples of 12 there are in the first 10,000 numbers. With a little trial and error using a calculator, that number comes out to be $\boxed{833}$

or use Chinese Remainder Theorem.

mathh mathh - 6 years, 10 months ago

A number theory problem by Lee Wall

The answer is 833.

1 solution

0 pending reports