Monday, November 08, 2010

Number Theory - Remainders

In Number Theory, questions involving remainders are pretty common. Given below are two simple questions on the concept of remainders

Question 1:
Three numbers leave remainders of 43, 47 and 49 on division by N. The sum of the three numbers leaves a remainder 9 on division by N. What are the values N can take?

Question 2. 
A number leaves a remainder 3 on division by 14, and leaves a remainder k on division by 35. How many possible values can k take?

Correct Answers:
Question 1: 65 and 130
Question 2: 5 different values

Explanatory Answers
Qn 1: Three numbers leave remainders of 43, 47 and 49 on division by N. The sum of the three numbers leaves a remainder 9 on division by N. What are the values N can take?

This question is based on some very basic and very important remainder properties. When the sum of two numbers is divided by the same divisor, the remainder should be equal to the sum of the two remainders. As long as the divisor remains the same, remainders are consistent for addition, subtraction and multiplication. In other words, we can add three numbers and then compute the remainders, or just add the three remainders. The equivalent rule applies for multiplication and subtraction also.

In this question, the sum of the three numbers should leave a remainder 43 + 47 + 49 = 139. Or, it should be of the form N * k + 139, where K is an integer.

However, it leaves a remainder 9, or it is of the form N * m + 9

N * k + 139 = N *m + 9
N * (m-k) = 130.

Or, N should be a factor of 130. Since the remainders left on division by N are 43, 47 and 49, N should be greater than 49.
The only factors of 130 that are greater than 49 are 65 and 130. So, N can take 2 values – 65 or 130.

Qn 2: A number leaves a remainder 3 on division by 14, and leaves a remainder k on division by 35. How many possible values can k take?

Let us have a look at the theory for this question as well. For instance, let us assume a number N leaves a remainder of 3 on division by 8. What would be the remainder when number N is divided by 24?

N/8 remainder = 3
N/24 remainder = ?
Let us look at Numbers that leave remainder 3 on division by 8
 3, 11, 19, 27, 35, 43 ……

For these numbers, remainders when divided by 24 are
3, 11, 19, 3, 11, 19 ……

Possible remainders are 3, 11 or 19

Alternative approach

N/8  remainder = 3
N = 8q + 3

q can be in one of 3 forms
3p
3p + 1
3p + 2

N = 8(3p) + 3 or 
8(3p + 1) + 3  or
8(3p + 2) + 3
24p + 3   or 
24p + 11 or 
24p + 19

N/24   possible remainders are 3, 11, 19

Why did we choose to write q as 3p, 3p + 1 or 3p + 2?
8 x 3 = 24, this is why we chose 3p, 3p +1, 3p + 2

So, if we are given that remainder on dividing N by 8, then there will be a set of possibilities for the remainder of division of N by 24 (or any multiple of 8)

Let us look at the opposite also. Say, we know the remainder of division of N by 42 is 11, what should be the remainder when N is divided by 7?

N/42 remainder = 11
N/7   remainder =?

N / 42 remainder = 11
N = 42q + 11

42q + 11 divided by 7
42q leaves no remainder
11/7 remainder = 4

So, if we are given that remainder on dividing N by 42, then we can find the remainder of dividing N by 7 (or any factor of 42)

Now, let us address the question

A number leaves a remainder of 3 on division by 14, or it can be written as 14n + 3
On division by 70, the possible remainders can be 3, 17 (3 +14), 31 (3 + 28), 45 (3 + 42), or 59 (3 + 56). The number can be of the form

70n + 3
70n + 17
70n + 31
70n + 45
70n + 59

Now, we need to divide this number by 35
70n + 3 divided by 35, the remainder will be 3
70n + 17 divided by 35, the remainder will be 17
70n + 31 divided by 35, the remainder will be 31
70n + 45 divided by 35, the remainder will be 10
70n + 59 divided by 35, the remainder will be 24

On division by 35, the possible remainders are 3, 17, 31, 10 or 24. There are 5 possible remainders
Post a Comment