How to Find Remainder of Large Powers Quickly

Basic Rules

Rule 0

Rem[(x^y)/d] = Rem[r^y/d]

where r is remainder when x divided by d

Example

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

or

• Rem[(29²⁹)/3] = Rem[(-1)²⁹/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[(29³⁰)/3] = Rem[(-1)³⁰/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[(30³⁰)/7]

Solution

• Rem[(30³⁰)/7] = Rem[(30)/7] * Rem[(30)/7] * Rem[(30)/7] * Rem[(30)/7] …….. (30 times)
• Rem[(30³⁰)/7] = 2 * 2 * 2 ….. (30 times) = 2³⁰
• Rem[(30³⁰)/7] = 2³⁰ = (2⁶)⁵= (64)⁵
• Rem[(30³⁰)/7] = Rem[64/7])⁵ => 1⁵
• Rem[(30³⁰)/7] = 1

Rem[(30³¹³²)/7]

Solution

• Rem[(30³¹³²)/7] = Rem[(2³¹³²)/7] (as Rem[30/7] = 2)

Hypothesis

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

Futhemore,

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

Similarly,

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

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

• Rem[31³²/3] = Rem[1³²/3] = 1

Thus, can be written in format 3k+1

• Rem[(30³¹³²)/7] = Rem[(2³¹³²)/7] = Rem[(2^3K+1)/7] = 2

Thus, the remainder will be 2

Common Factor

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

Example

• Rem[(4¹⁵)/28] = Rem[(4*4¹⁴)/(4*7)] = 4* Rem[(4¹⁴)/(7)]
• 4 * resultOf(Rem[(4*4*4¹²)/(7)])
• 4 * resultOf(Rem[(4)/(7)] * Rem[(4)/(7)] * Rem[(4¹²)/(7)])
• 4 * resultOf(4 *4 * Rem[(64⁴)/(7)])
• 4 * resultOf(4 *4 * Rem[(1⁴)/(7)])
• 4 * resultOf(Rem[(4*4*1)/7])
• 4 * resultOf(Rem[(16)/7])
• 4 * resultOf(2])
• 8

Example

• Rem[(5¹⁶)/35] = Rem[(5*5¹⁵)/(5*7)] = 5* Rem[(5¹⁵)/(7)]
• 5 * resultOf(Rem[(125⁵)/(7)])
• 5 * resultOf(Rem[(6⁵)/(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] = r₁ & Rem[M/b] = r₂

Rem[M/N] = axr₂ + byr₁

Such that ax + bx = 1

Example

• Rem[(7¹⁵)/15]
• Rem[(7¹⁵)/(3*5)]

a = 3 & b = 5

• Rem[(7¹⁵)/(3)] = 1 &
• Rem[(7¹⁵)/(5)] = Rem[(2¹⁵)/(5)] = 3

• (2¹)/5 , Rem is 2
• (2²)/5 , Rem is 4
• (2³)/5 , Rem is 3
• (2⁴)/5 , Rem is 1
• (2⁵)/5 , Rem is 2
• (2⁶)/5 , Rem is 4
• (2⁷)/5 , Rem is 3
• (2⁸)/5 , Rem is 1

So remainder for (2¹⁵)/5 is 3.

So we now have,

r_{2 =} 3, r₁= 1

• axr₂ + byr₁ = 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[a^p-1/p] = 1

Example

• Rem[2³⁴⁵/11]
• Rem[((2¹⁰)³⁴(2))/11]
• Rem[((2¹⁰)³⁴)/11] * Rem[(2)⁵)/11]
• p = 11 and p – 1 = 10 so using fermats theorem
• Rem[((1)³⁴)/11] * Rem[(2)⁵)/11]
• Rem[((1)³⁴)/11] * Rem[(2)⁵)/11]
• Rem[1/11] * Rem[32)/11]
• 1 * 10
• 10

Euler’s Remainder Theorem

               For a number of the form P^x/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 = { a^l x b^m x cⁿ }  and a, b & c are prime factors of Q.

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

• 33 can be prime factorised as { 2² x 3² }  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  2⁶⁷/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 { 11¹ x 3¹ }  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[P^y/Q]
• i.e Rem[2⁷/33] = 29
• So, Rem[2⁶⁷/33] = 29
• Answer = 29

Example 2 Using Euler’s Theorem

Remainder of 3⁵³/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
• 3⁵³/63 = { 3² x 3⁵¹ } / { 3² x 7 }
• 3⁵³/63 = { 3⁵¹ } / { 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[P^y/Q]
• i.e Rem[3³/7] = 6
• So, Rem[3⁵³/63] = 6 * 9 = 54 (as we eliminated 9 as common factor initially )
• Answer = 54