How to Calculate Remainders of large numbers

In this post we will see how to calculate remainders like the remainder of a sum, remainder of a product and understand what is meant by negative remainders. 

By the end of this post, you will learn

1. How to calculate remainders of sum and product.
2. The concept of negative remainders
3. How to find remainders of large numbers using negative remainders
4. How to calculate remainders of a number with power using the Fermat’s and Euler’s theorem.

Video:

What is a Remainder?

Remainder is a number that is left over when one number, say N, is divided by another number, say D. i.e If the number N is divided by another number D, it gives Quotient Q and Remainder R. We represent this as N = Q x D + R. Where Q and R are the Quotient and Remainder respectively.

For example, 22 when divided by 9, gives a quotient 2 and remainder 4. So, 22 = 2 x 9 + 4.

How to Calculate Remainders?

There are various techniques and theorems to calculate remainders, but in this post we will focus our attention on specific technique to calculate the remainders of sum or product. We will then look into an important concept in remainders called the negative remainders. Using these concepts we will try to find the remainder of powers. We will also apply the Fermat’s and Euler’s theorem to calculate the remainders of large numbers.

How to Calculate Remainder of Sum?

If N1, N2, N3… be numbers which when divided by a divisor D, give quotients Q1, Q2, Q3… and remainders R1, R2, R3… respectively. Then, remainder of sum of N1, N2, N3… when divided by D is the remainder obtained by dividing the sum of R1, R2, R3… by D.

[toggles type=”multiple”][toggle title=”Find the remainder of the sum of 28, 29 and 30 when divided by 9″]

Remainder$(\frac{28\ +\ 29\ +\ 30}{9})$ => Remainder$(\frac{1\ +\ 2\ +\ 3}{9})$ => 6

where,
1 , 2 and 3 are the remainders obtained when each of the numbers 28, 29 and 30 are divided by 9 respectively. [/toggle][/toggles]

How to Calculate Remainder of Product?

Consider N1, N2, N3… be numbers which when divided by a divisor D, give quotients Q1, Q2, Q3… and remainders R1, R2, R3… respectively.

In this case, Remainder of product of N1, N2, N3… when divided by D is the remainder obtained by dividing the product of R1, R2, R3… by D.

[toggles type=”multiple”][toggle title=”Find the remainder of the product of 22, 23 and 24 when divided by 7″]

Remainder$(\frac{22\ *\ 23\ *\ 24}{7})$ => Remainder($\frac{1\ *\ 2\ *\ 3}{7})$ => 6

where,
1 , 2 and 3 are the remainders obtained when each of the numbers 22, 23 and 24 are divided by 7 respectively.[/toggle]

[toggle title=”Calculate the remainder when 28 to the power of 1024 is divided by 9.”]

Remainder($\frac{28^{1024}}{9})$ => Remainder($\frac{28\ *\ 28\ *\ 28\ …\ (1024\ times)}{9})$

Here, 28 gives remainder 1 when divided by 9. Hence,

Remainder($\frac{28\ *\ 28\ *\ 28\ …\ (1024\ times)}{9})$ => Remainder($\frac{1\ *\ 1\ *\ 1\ …\ (1024\ times)}{9})$ => 1. [/toggle][/toggles]

What is a Negative Remainder?

Consider an example, 26 when divided by 9, gives remainder 8. Hence we have,
26 = (9 x 2) + 8 which is same as 26 = (9 x 3) - 1

In the above example 8 is the positive remainder and -1 is the negative remainder of 26 when it is divided by 9.

Lets look at some problems on negative remainders to understand how this concept is helpful in finding the remainders of large numbers.

Problems on Negative Remainders

[toggles type=”multiple”][toggle title=”What is the remainder when the product of 32, 64 and 96 is divided by 11.”]

Here,
32 can be written as 11 x 2 + 10 or 32 = 11 x 3 – 1.  Accordingly, positive remainder of 32 is 10 and its Negative remainder is -1

Similarly, 64 can be written as 11 x 5 + 9 or 64 = 11 x 6 – 2. Which gives positive remainder of 64 to be 9 and its Negative remainder to be -2

Also, 96 can be written as 11 x 8 + 8 or 96 = 11 x 9 – 3. Which gives positive remainder of 96 as 8 and its Negative remainder as -3

Now coming back to the problem, using the negative remainders above:

Remainder$(\frac{32\ *\ 64\ *\ 96}{11})$ => Remainder$(\frac{-1\ *\ -2\ *\ -3}{11})$ => Remainder$(\frac{-6}{11})$ => -6

Here, we see that the remainder is negative. The corresponding positive remainder can be obtained by adding the divisor 11 to -6, which is equal to 5.

Hence Remainder$(\frac{32\ *\ 64\ *\ 96}{11})$ = 5[/toggle]

[toggle title=”What is remainder of 2 to the power of 96 when divided by 9?”]

Remainder$(\frac{2^{96}}{9})$ => Remainder$(\frac{(2^3)^{32}}{9})$ => Remainder$(\frac{8^{32}}{9})$

8 when divided by 9 gives -1 as the negative remainder. Hence,

Remainder$(\frac{8^{32}}{9})$ => Remainder$(\frac{(-1)^{32}}{9})$ => 1

Therefore, Remainder$(\frac{2^{96}}{9})$ = 1. [/toggle][/toggles]

How to Calculate Remainders of Large Numbers using Fermat’s and Euler’s Theorem

Fermat’s Little Theorem

As per the Fermat’s little theorem, if N is a prime number & M is prime to N, then

Remainder$(\frac{M^{N-1}}{N}) = 1$

[toggles type=”accordion”][toggle title=”What is the remainder of 15 to the power of 26 when divided by 13.”]

Here, since the divisor 13 is prime number, as per the Fermat’s little theorem, we have
Remainderv(\frac{15^{12}}{13}) = 1$

Now, Remainder$(\frac{15^{26}}{13})$ => Remainder$(\frac{(15^{12})^2\ *\ 15^2 }{13})$

15 to the power of 12 when divided by 13 leaves a remainder 1 and 15 when divided by 13 leaves a remainder 2. Hence,

Remainder$(\frac{(15^{12})^2\ *\ 15^2 }{13})$ => Remainder$(\frac{(1)^2\ *\ 2^2 }{13})$ => 4

Therefore, Remainder$(\frac{15^{12}}{13}) = 4$

So Fermat’s theorem will be handy in calculating remainders when the divisor is a prime number.

[/toggle][/toggles]

Euler’s Theorem

In order to understand the Euler’s theorem, we must first understand the Euler’s Totient Function.

Euler’s Totient Function

The number of positive integers less than or equal to n and prime to n is given by

φ(n) = $n(1-\frac{1}{a})(1-\frac{1}{b})(1-\frac{1}{c})$

where, φ(n) is the Euler’s Totient function and n is a natural number such that n = {$a^p * b^q * c^r$…}. Here a,b,c are prime factors of n and p, q, r are positive integers.

[toggles type=”multiple”][toggle title=”Example 1: Find the Euler’s totient function of 33.”]
33 in terms of terms of its prime factors is written as 33 = 11 * 3.
The Euler’s totient function of 33 is given by
φ$(33) = 33(1 – \frac{1}{11})(1 – \frac{1}{3}) = 20$.

[/toggle]

[toggle title=”Example 2: Find the Euler’s totient function of 9.”]
9 in terms of terms of its prime factors is written as $9 = {3^2}$.
The Euler’s totient function of 9 is given by
φ$(9) = 9(1 – \frac{1}{3}) = 6$.

[/toggle][/toggles]

With this knowledge of Euler’s totient function, lets understand the Euler’s theorem.

Euler’s Theorem

Lets consider a number in the form $\frac{m^x}{n}$. As per the Euler’s theorem,

If n is relatively prime to m then ${m^{\Phi(n)}}$ divided by n gives 1 as the remainder. i.e

$Remainder(\frac{m^{\Phi(n)}}{n}) = 1$.

Approach to problems based on Euler’s Theorem

If the remainder of the number in the form $\frac{m^x}{n}$ has to be calculated, then

Step 1: Identify if m & n are co-primes.

Step 2: Calculate $\Phi(n)$.

Step 3: Divide the power of m by $\Phi(n)$, The remainder of which is the new power of m. Lets call this new power of m as y.

Step 4: Remainder$(\frac{m^x}{n})$ = Remainder$(\frac{m^y}{n})$

Examples to calculate remainders using Euler’s theorem.

[toggles type=”multiple”][toggle title=”Example 1: What is the remainder when 2 to the power of 63 is divided by 99?”]
Here, m = 2 and n = 99 are co-prime to each other. Hence we can apply Euler’s theorem.

-> Calculate the Euler’s totient function of 99.
$99 = 11 * {3^2}$
$=> \Phi(99) = 99(1 – \frac{1}{11})(1 – \frac{1}{3}) => 60$

-> After that, divide the exponent x by \Phi(n) to find remainder y.
$ y = Remainder(\frac{63}{\Phi(99)}) => 3 $

-> Next, find the remainder of m to the power of y when divided by n.
$ Remainder(\frac{2^3}{99}) = 8 $

Therefore, $ Remainder(\frac{2^{63}}{99}) = 8 $ 

But notice that, m and n were co-primes, now what if m and n are not co-primes? Check out the next example. [/toggle]

[toggle title=”Example 2: What is the remainder when 3 raised to 45 is divided by 45?”]

Here, m = 3 and n = 45 are not co-primes.
To solve this kind of a problem, first separate the common factor from the numerator and the denominator. i.e

$\frac{3^{45}}{45} = \frac{3^2*3^{43}}{9*5}$

-> We will use the common factor 9 later.
-> Consider $\frac{3^{43}}{5}$ both 3 and 5 are co-primes. So, we can calculate the remainder of $\frac{3^{43}}{5}$ using the Euler’s theorem.

Lets first calculate the remainder when the exponent 43 is divided by the Euler’s totient function of 5.
Remainder$(\frac{43}{\Phi(5)}) = 3 $

Now, calculate the remainder of $\frac{3^{43}}{5}$

Remainder$(\frac{3^{43}}{5}) => Remainder$(\frac{3^{3}}{5}) => 2 $

-> Multiplying the common factor 9 with the remainder of $\frac{3^{43}}{5}$ gives us the actual remainder of $\frac{3^{45}}{45}$

Remainder($\frac{3^{43}}{45}) => 9 * 2 = 18 $

[/toggle][/toggles]

What Next?

I hope this comprehensive post on finding the remainders was helpful. If yes, you may also be interested in calculating Divisors of a Number – Sum – Product – Number of Divisors

Please do try our android app – Math Tricks Workout. The app is developed to improve mental arithmetic using a series of left to right fast math workouts.