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
How to find remainders of large numbers quickly

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[2] * Rem[3] * Rem[4]
  • Rem[2*3*4] => Rem[24/7]
  • 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[2] + Rem[3] + Rem[4]
  • 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
  • Answer = 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 )
  • Answer = 54

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[2] * Rem[1] * Rem[18!/19]
  • Now, P = 19 is a prime number.
  • Rem[2] * Rem[1] * Rem[18!/19]
  • Rem[2] * Rem[1] * Rem[(19-1)!/19]
  • Rem[2] * Rem[1] * 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