# 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.

### Related posts

• July 15, 2013 Number Theory Question What is the remainder when (13100 +17100) is divided by 25? A. 2 B. 0 C. 15 D. 8 Correct Answer: Choice (A) Explanation: What is the remainder when (13100 […] Posted in Number Theory
• November 8, 2010 Questions on Number Theory – Remainder patterns Here are a few questions from remainders in Number Theory 1. What are the last two digits of the number 7 45 ? 2. What is the remainder when we divide 390 + 590 by 34?   3. N2 […] Posted in Number Theory
• November 15, 2010 CAT Number Theory – Modulus Had sent an entry on Euler's phi function earlier , and thought it would be best to follow this up with a slightly more detailed post on modulus arithmetic. If we divide a number N by […] Posted in Number Theory
• November 8, 2010 Number Theory Remainders – 2 more questions Have given below two more questions on remainders. Question 1: A prime number p greater than 100 leaves a remainder q on division by 28. How many values can q take?. Question […] Posted in Number Theory