Deduce remainder of large numbers [Manual Method]

Often articles are published on Python algorithms in this blog. But today’s article is all about calculating the remainder of two numbers by hand, manually.

When two numbers are divided, it produces two things. One is termed as the Quotient and the other is termed as the Remainder. Based on the application, more focus could be given either to the Quotient or to the Remainder. Today, will focus on the Remainder and find how to deduce the Remainder when a large number is divide by a comparatively small number without doing extensive calculations.

According to the Euclidean division, this can be written as follow:

let x – numerator, y – denominator, k – quotient and r – remainder

x = \displaystyle k*y + r

Using the above equation, will try to find the remainder of 27 / 12.

27 = \displaystyle k*12 + r

It is possible to try applying k = 1 ; k = 2 and then calculate r, at k = 2 we get the answer which is r = 3 . This algorithm is promising, however when the numerator (x) is relatively a large number, more computation is required.

For an example, try to find the remainder of \displaystyle (25^{243}/12)

Assuming this calculation is done by hand, as the numerator is a large number it is not possible to compute the remainder using the above algorithm, of course it is possible but it might take lot of computational steps and time. Therefore another approach is required.

To understand easily, will consider following generalize form; \displaystyle (x^{p}/y)

Algorithm

  1. Break the numerator (x) into two numbers where y needs to be a factor of one of the numbers. Let numbers are a and b, then a = k * y and x = a + b
  2. When there are some combinations available for a and b try to obtain the minimum value for b which satisfies the requirement mentioned in step 1. Obtaining b = 1 is the ideal, if possible.
  3. Once above steps are concluded, the equation reduces to \displaystyle ((a+b)^{p}/y) , further it can be deduce to \displaystyle ((k*y + b)^{p}/y)
  4. Once it is reduced, the remainder can be easily obtained by solving \displaystyle ((b)^{p}/y)
  5. In a scenario where b = 1, then the answer is 1 as \displaystyle ((1)^{p}/y) is always 1.

Getting back to the example mentioned above, \displaystyle (25^{243}/12)

  1. 25 can be broken into 1 and 24, a = 24 and b = 1, 12 become a factor of a therefore the combination satisfies the requirement.
  2. Then solve \displaystyle (1^{243}/12) , which is equal to 1.

Results can be verified with the following python code as well:

<pre>print('Remainder - ',(25**243)%12)</pre>

In such scenarios, where b is not possible to take as 1, it is required to solve the equation numerically. But even though the numerator is reduced, still it requires more computational effort.

Algorithm – part 2

When b is not equal to 1, following method can be used. It follows patterns recognition and then deduce the answer.

To understand the concept behind, will take a slightly different version of the above example, assume that it is required to calculate the remainder of \displaystyle (26^{243}/12)

At this time, as the numerator is 26, it is not possible to break into two numbers in which b = 1. When a = 12, b = 2. Therefore following algorithm needs to be used to deduce the remainder from the reduced equation.

The reduced equation for \displaystyle (29^{243}/12) is \displaystyle (2^{243}/12)

Then take the reduced equation as \displaystyle (2^{p}/12) where p = 243

The next part is identify the pattern by applying p = 1, p = 2, p = 3 ……… This needs to be done until a pattern can be recognized.

at p = 1 \displaystyle (2/12) remainder is 2
at p = 2 \displaystyle (4/12) remainder is 4
at p = 3 \displaystyle (8/12) remainder is 8
at p = 4 \displaystyle (16/12) remainder is 4
at p = 5 \displaystyle (32/12) remainder is 8
at p = 6 \displaystyle (64/12) remainder is 4

A pattern, now can be recognized. It seems when p is odd remainder is 8 and when p is even the remainder is 4 for all p when p>1. As we are looking for the remainder when p = 243 which is an odd number, as a result the remainder should be 8.

Verify the answer with the following python script.

print('Remainder - ',(26**243)%12)

Recognizing the pattern is quite cumbersome but it is always easier than working out the whole equation.

Finally, below is the mathematical proof for the above algorithm:

Mathematical Proof

Let \displaystyle (x^{p}/y) : where y ≠ 0 and x and y are positive real integers.

In Euclidean division, x = k * y + r ———————(1)

applying (1) , \displaystyle ((k*y+r)^{p}/y)

Term (k*y+r), can be treated as binomial expansion as a = k*y and b = r

(a+b)^{p} = \displaystyle c_{1}*a^{p} + c_{2}*a^{p-1}*b + c_{3}*a^{p-2}*b^{2}..... + c_{p-2}*a^{2}*b^{p-2} + c_{p-1}*a*b^{p-1} + b^{p} ———–(2)

In equation no. 2, it can be noticed that each term has a factor of a except the last term, which is \displaystyle b^{p} , that means each term is divisible with no reminder except the last term. Therefore that is the only term which generates a remainder. Calculating the remainder for the last term gives the remainder of the whole equation, that is why it is possible to reduce the original equation to:

\displaystyle ((b)^{p}/y)

Summary

When calculating prime numbers, it is often required to check if a given number has factors. One of the efficient ways is to divide given numbers and check if there is a remainder. For such operations this algorithm can be used specially when the numerator and the denominator are relatively large (in exponent format). Furthermore, if it is possible to break numbers into a and b (step 1 in Algorithm) such a way that b = 1, at a glance the remainder can be obtained. Therefore this is a faster technique that can be mastered to calculate the remainder manually and also can be implemented in computer aided calculations as well.

This article is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported (CC BY-SA 3.0) license. 
Advertisements

Please add your valuable idea below, will make a discussion, thanks !

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s