## Number Theory - Remainders

Posted by Rajesh Balasubramanian on 12:27 PM with No comments

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.

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?

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

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

Categories: CAT number theory, Remainders

## 0 comments:

Post a Comment