# How to Find Remainder of Large Powers Quickly

## Find Remainders of Large Powers Quickly

Ever wondered how you can calculate remainder of large powers quickly ? Like –

252627when divided by 3 what would be result?

You would need to learn the following –

• Basic Rules
• Common Factor
• Co Primes
• Fermat Theorem
• Euler Theorem
• Wilson Theorem ## Basic Rules

### Rule 0

Rem[(xy)/d] = Rem[ry/d]

where r is remainder when x divided by d

### Example

• Rem[(3132)/3]
• = Rem[132/3] (as remainder is 1 when 31 is divided by 3)
• = 1

or

• Rem[(2929)/3] = Rem[(-1)29/3] = -1 = +2

The above -1 can be written as 2 as -1 remained in case of 3 is nothing but + 2 remainder.

We didn’t do 2 power 29 as it would have taken additional steps and would’ve been lengthy

or

• Rem[(2930)/3] = Rem[(-1)30/3] = 1

### Rule 1

Rem[(a*b*c)/d] = Rem[a/d] * Rem[b/d] * Rem[c/d]

### Example

• Rem[(30*31*32)/7] = Rem[30/7] * Rem[31/7] * Rem[32/7]
• Rem * Rem * Rem
• 3

### Rule 2

Rem[(a+b+c)/d] = Rem[a/d] + Rem[b/d] + Rem[c/d]

### Example

• Rem[(30+31+32)/7] = Rem[30/7] + Rem[31/7] + Rem[32/7]
• Rem + Rem + Rem
• Rem[2+3+4] => Rem[9/7]
• 2

## Applications of above rules

Rem[(3030)/7]

### Solution

• Rem[(3030)/7] = Rem[(30)/7] * Rem[(30)/7] * Rem[(30)/7] * Rem[(30)/7] …….. (30 times)
• Rem[(3030)/7] = 2 * 2 * 2 ….. (30 times) = 230
• Rem[(3030)/7] = 230 = (26)5= (64)5
• Rem[(3030)/7] = Rem[64/7])5 => 15
• Rem[(3030)/7] = 1

Rem[(303132)/7]

### Solution

• Rem[(303132)/7] = Rem[(23132)/7] (as Rem[30/7] = 2)

#### Hypothesis

1. We know, 23 will give us remainder 1 when divided by 7 (Rem[8/7] = 1)
2. Thus, for any K > 0, 23K will also give us remainder 1 when divided by 7

Futhemore,

1. 23K+1 will give us remainder 2
1. 23K+1 can be written as (23K)*2 => Rem[23K/7] * 2
2. 1* 2 = 2

Similarly,

1. 23K+2 will give us remainder 4
1. 23K+2 can be written as (23K)*2*2 => Rem[23K/7] * 2 * 2
2. 1* 2 * 2 = 4

Now, we need to write 3132 in 3K, 3K + 1, 3K + 2 format by doing follows –

• Rem[3132/3] = Rem[132/3] = 1

Thus, can be written in format 3k+1

• Rem[(303132)/7] = Rem[(23132)/7] = Rem[(23K+1)/7] = 2

Thus, the remainder will be 2

## Common Factor

Rem[X/Y] = Rem[kx/ky] = k *resultOf(Rem[x/y])

### Example

• Rem[(415)/28] = Rem[(4*414)/(4*7)] = 4* Rem[(414)/(7)]
• 4 * resultOf(Rem[(4*4*412)/(7)])
• 4 * resultOf(Rem[(4)/(7)] * Rem[(4)/(7)] * Rem[(412)/(7)])
• 4 * resultOf(4 *4 * Rem[(644)/(7)])
• 4 * resultOf(4 *4 * Rem[(14)/(7)])
• 4 * resultOf(Rem[(4*4*1)/7])
• 4 * resultOf(Rem[(16)/7])
• 4 * resultOf(2])
• 8

### Example

• Rem[(516)/35] = Rem[(5*515)/(5*7)] = 5* Rem[(515)/(7)]
• 5 * resultOf(Rem[(1255)/(7)])
• 5 * resultOf(Rem[(65)/(7)])
• 5 * resultOf(Rem[(6*36*36)/(7)])
• 5 * resultOf(Rem[(6)/(7)] * Rem[(36)/(7)] * Rem[(36)/(7)])
• 5 * resultOf(6 *1 * 1)
• 30

## Co Primes

When trying to find out the remainder, if the divisor can be broken down into smaller co-prime factors; then

Rem[M/N] = Rem[M/(a*b)]

HCF(a, b) = 1 (then only these are co-primes)

Let, Rem[M/a] = r1 & Rem[M/b] = r2

Rem[M/N] = axr2 + byr1

Such that ax + bx = 1

### Example

• Rem[(715)/15]
• Rem[(715)/(3*5)]

a = 3 & b = 5

• Rem[(715)/(3)] = 1 &
• Rem[(715)/(5)] = Rem[(215)/(5)] = 3
(Trick) How is Rem[(215)/(5)] = 3 ?

We can observe a pattern for remainders when divided by 5.
• (21)/5 , Rem is 2
• (22)/5 , Rem is 4
• (23)/5 , Rem is 3
• (24)/5 , Rem is 1
• (25)/5 , Rem is 2
• (26)/5 , Rem is 4
• (27)/5 , Rem is 3
• (28)/5 , Rem is 1

So remainder for (215)/5 is 3.

So we now have,

r2 = 3, r1= 1

• axr2 + byr1 = 3*x*3 + 5*y*1

Such that, ax + by = 1 | 3x + 5y = 1

Valid values are x = -3 and y = 2

Thus final answer will be: 3*(-3)*3 + 5*2*1 = – 27 + 10 = 17

## Fermat Theorem

If p is a prime, and HCF (a, p) = 1 (a and p are co-primes), then Rem[ap-1/p] = 1

### Example

• Rem[2345/11]
• Rem[((210)34(2))/11]
• Rem[((210)34)/11] * Rem[(2)5)/11]
• p = 11 and p – 1 = 10 so using fermats theorem
• Rem[((1)34)/11] * Rem[(2)5)/11]
• Rem[((1)34)/11] * Rem[(2)5)/11]
• Rem[1/11] * Rem[32)/11]
• 1 * 10
• 10

## Euler’s Remainder Theorem

For a number of the form Px/Q , where P & Q are co-primes, then Rem[Pϕ(Q)/Q] =1, where

ϕ(Q) is called the Euler’s Number.

### Let us first learn How to find Euler Number ϕ(Q) ?

ϕ(Q) = Q (1 – 1/a) (1 – 1/b) (1 – 1/c)……………. ,

where Q = { al x bm x cn }  and a, b & c are prime factors of Q.

Example :  Euler’s Number for 36, i.e  ϕ(36)

• 33 can be prime factorised as { 22 x 32 }  which means a = 2 and b = 3
• ϕ(36) = 36 (1 – 1/a) (1 – 1/b)    (Using Formula)
• ϕ(36) = 36 (1 – 1/2) (1 – 1/3) ,  since a = 2 and b = 3
• ϕ(36) = 12

### Example 1 Using Euler’s Theorem

Remainer of  267/33

• Here P = 2 , Q = 33 and x = 67
• P and Q are co-prime i.e 2 and 33 are co-prime to each other
• Q = 33 can be prime factorised as { 111 x 31 }  which means a = 11 and b = 3
• ϕ(Q) = ϕ(33) = 33 (1 – 1/11) (1 – 1/3) = 20
• So ϕ(Q) = 20
• Now Divide x by ϕ(Q) and find the remainder ‘y’
• y = Rem[x / ϕ(Q)]
• y = Rem[67 / 20] = 7
• Now find Rem[Py/Q]
• i.e Rem[27/33] = 29
• So, Rem[267/33] = 29

### Example 2 Using Euler’s Theorem

Remainder of 353/63

• Here P = 3 , Q = 63 and x = 53
• P and Q are not co-prime i.e 3 and 63 are not co-prime to each other
• 353/63 = { 32 x 351 } / { 32 x 7 }
• 353/63 = { 351 } / { 7 }
• New Values P=3 and Q=7 are co-prime to each other. And New value of x = 51
• ϕ(7) = 6
• Now Divide x by ϕ(Q) and find the remainder ‘y’
• y = Rem[51 / 6] = 3
• Now find Rem[Py/Q]
• i.e Rem[33/7] = 6
• So, Rem[353/63] = 6 * 9 = 54 (as we eliminated 9 as common factor initially )

## Wilson’s Theorem

•        When (P-1)! is divided by P, the remainder is (P-1), where P must be a prime number.
•        When (P-2)! is divided by P, the remainder is 1, where P must be a prime number.

### Example 1

Find the remainder when 40! is divided by 41?

• Rem[40!/41]
• Rem[ (41-1)!  / 41]
• Here P = 41 is a prime number.
• So Rem[ (41-1)!  / 41] = (41 – 1) = 40

### Example 2

Find the remainder when 45! is divided by 47?

• Rem[45!/47]
• Rem[ (47-2)!  / 47]
• Here P = 47 is a prime number.
• So Rem[ (47-2)!  / 47] = 1

### Example 3

Find the remainder when 21! is divided by 361?

• Rem[21!/361]
• Rem[ (21*20*19*18!)  / (19 * 19)]
• Rem[ (21*20*18!)  / 19] , removing common terms
• Rem[(21*20*18!)/19] = Rem[21/19] * Rem[20/19] * Rem[18!/19]
• Rem * Rem * Rem[18!/19]
• Now, P = 19 is a prime number.
• Rem * Rem * Rem[18!/19]
• Rem * Rem * Rem[(19-1)!/19]
• Rem * Rem * Rem[19-1], by wilson’s theorem
• Rem[(2*1*18)/19]
• Rem[36/19]
• 17
• Now we removed common term 19 initially
• So final answer would be 17*19 = 323