How 9 Cheenta students ranked in top 100 in ISI and CMI Entrances?
Learn More

Arithmetic of Remainders | Math Olympiad

Let's discuss a problem based on Arithmetic of Remainders and understand the concept behind it.

Consider the two number: 37 and 52

What is the remainder when we divide 37 by 7? 2 of course. And 52 produces remainder 3 when divided by 7. Suppose we want to know the remainder when the product of 37 and 52 is divided by 7.

One way to do this is to first multiply 37 and 52 to get 1924, and then divide it by 7 to get 274 as quotient and 6 as remainder. Indeed 37 \times 52 = 1924 = 7 \times 274 + 6

However there is a simpler method to do this. If we just multiply the remainders produced by 37 and 52 we will get the final remainder! Indeed 3 \times 2 = 6 . Apparently if the numbers are multiplied that the remainders also get multiplied!

Let us do one more experiment. This time we divide by 9. Suppose the numbers are 83 and 904. 83 produced 2 as remainder ( 83 = 9 \times 9 + 2 ) and 904 produced 4 as remainder ( 904 = 9 \times 100 + 4 ) . Then what do we expect the remainder to be when 904 \times 83 is divided by 9? It should be the product of the individual remainders or 2 \times 4 = 8 . Indeed we find 904 \times 83 = 75032 = 9 \times 8336 + 8 .

The question is why this happens? Let us approach the problem algebraically. Suppose t_1 , t_2 be two numbers and m is the number by which we divided both them. Let the quotients and remainders produced be q_1 , q_2 , r_1 , r_2 respectively. That is

t_1 = n \times q_1 + r_1

t_2 = n \times q_2 + r_2

Then t_1 \times t_2 = ( n \times q_1 + r_1 ) \cdot (n \times q_2 + r_2 )

or t_1 \times t_2 = n^2 q_1 q_2 + n q_1 r_2 + n q_2 r_1 + r_1 r_2

or t_1 \times t_2 = n ( n q_1 q_2 + q_1 r_2 + q_2 r_1 ) + r_1 r_2

Thus when t_1 \times t_2 is divided by n , quotient is n q_1 q_2 + q_1 r_2 + q_2 r_1 and remainder is r_1 \times r_2 which is the product of the initial remainders. So it is no accident that if we multiply the initial remainders of two numbers we get the final remainder produced by the product of those two numbers.

However what will happen if r_1 r_2 exceeds n? Remainder cannot exceed the divisor. So we divide r_1 r_2 again by n to find the final remainder. That is suppose

r_1 r_2 = n \times q_3 + r_3 then r_3 is the final remainder. Infact, the final quotient and remainder will be formed in the following manner:

t_1 \times t_2 = n ( n q_1 q_2 + q_1 r_2 + q_2 r_1 ) + r_1 r_2

or t_1 \times t_2 = n ( n q_1 q_2 + q_1 r_2 + q_2 r_1 ) + n \times q_3 + r_3

or t_1 \times t_2 = n ( n q_1 q_2 + q_1 r_2 + q_2 r_1 + q_3 ) + r_3

Try to verify this if the numbers are 48 and 54 and the divisor is 5.

This same logic works when two numbers are added or a number is raised to some power. In the next installment of this series of articles on number theory we will hand all of these operations in detail.

Some Useful Links:

Chinese Remainder Theorem

Math Olympiad in India

Our Math Olympiad Program

A Math Game in Symmetry - Video

Knowledge Partner

Cheenta is a knowledge partner of Aditya Birla Education Academy

Cheenta Academy

Aditya Birla Education Academy

Aditya Birla Education Academy

Cheenta. Passion for Mathematics

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.