# Question on Number Theory

Question

A bus service runs from Chennai to Blr every third day with the first bus starting on Jan 1st. Another bus service runs from Chennai to Mumbai every 5th day starting from Jan 2nd. A third bus service from Chennai to Cochin runs on every 7th day starting from Jan 4th. In that year (which is not a leap year), on how many different days will a bus run from Chennai to all three cities?

Explanation

Let us call Jan 1st as day 1, jan 2nd as day 2 and so on.

So,
The Chennai-Blr services runs on days             1, 4, 7, 10, 13, 16, 19,......
The Chennai-Mumbai services runs on days    2, 7, 12, 17, 22, 27,......
The Chennai-Cochin services runs on days     4, 11, 18, 25, ......

First up, let us see if we can find one day where all three buses ply.

Chennai Blr runs on days of the form 3a + 1, Chennai_Mumbai on 5b + 2, and Chennai-Cochin on 7c + 4. If N can be written as 3a + 1, 5b + 2 and 7c + 4, then we should be able to get n as 105d + ___ . (105 is the LCM of 3, 5 and 7)

This is a very important idea. Get lots of practice on this idea. Wrap your head around this idea very clearly.

First let us combine 3a + 1 and 5b + 2.

A number of the form 3a + 1, on division by 15 can have one of the following remainders { 1, 4, 7, 10, 13}
A number of the form 5b + 2, on division by 15 can have one of the following remainders { 2, 7, 12}

Or, if a number is of the form 3a + 1 and 5b + 2, it has to be of the form 15k + 7.

Now, N = 15K + 7 and 7c + 4.

Number 15k + 7, on division by 105 can have one of the following remainders { 7, 22, 37, 52, 67, 82, 97}}
Number 7c + 4, on division by 105 can have one of the following remainders { 4, 11, 18, 25, 32, 39, 46, 53, 60, 67, 74, 81, 88, 95, 102, 109}

Or, the number is of the form 105d + 67.

So, all three services will run on days 67, 67 + 105, 67 + 105*2 and so on.

Or, on days 67, 172  and 277. (Any other day would go beyond 365)

So, all three services would run together 3 days of the year.

Wonderful question testing concepts of LCM and Remainders.

IIM CAT Preparation Tips: Question on Number Theory

## Oct 8, 2014

### Question on Number Theory

Question

A bus service runs from Chennai to Blr every third day with the first bus starting on Jan 1st. Another bus service runs from Chennai to Mumbai every 5th day starting from Jan 2nd. A third bus service from Chennai to Cochin runs on every 7th day starting from Jan 4th. In that year (which is not a leap year), on how many different days will a bus run from Chennai to all three cities?

Explanation

Let us call Jan 1st as day 1, jan 2nd as day 2 and so on.

So,
The Chennai-Blr services runs on days             1, 4, 7, 10, 13, 16, 19,......
The Chennai-Mumbai services runs on days    2, 7, 12, 17, 22, 27,......
The Chennai-Cochin services runs on days     4, 11, 18, 25, ......

First up, let us see if we can find one day where all three buses ply.

Chennai Blr runs on days of the form 3a + 1, Chennai_Mumbai on 5b + 2, and Chennai-Cochin on 7c + 4. If N can be written as 3a + 1, 5b + 2 and 7c + 4, then we should be able to get n as 105d + ___ . (105 is the LCM of 3, 5 and 7)

This is a very important idea. Get lots of practice on this idea. Wrap your head around this idea very clearly.

First let us combine 3a + 1 and 5b + 2.

A number of the form 3a + 1, on division by 15 can have one of the following remainders { 1, 4, 7, 10, 13}
A number of the form 5b + 2, on division by 15 can have one of the following remainders { 2, 7, 12}

Or, if a number is of the form 3a + 1 and 5b + 2, it has to be of the form 15k + 7.

Now, N = 15K + 7 and 7c + 4.

Number 15k + 7, on division by 105 can have one of the following remainders { 7, 22, 37, 52, 67, 82, 97}}
Number 7c + 4, on division by 105 can have one of the following remainders { 4, 11, 18, 25, 32, 39, 46, 53, 60, 67, 74, 81, 88, 95, 102, 109}

Or, the number is of the form 105d + 67.

So, all three services will run on days 67, 67 + 105, 67 + 105*2 and so on.

Or, on days 67, 172  and 277. (Any other day would go beyond 365)

So, all three services would run together 3 days of the year.

Wonderful question testing concepts of LCM and Remainders.