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[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
- We know, 23 will give us remainder 1 when divided by 7 (Rem[8/7] = 1)
- Thus, for any K > 0, 23K will also give us remainder 1 when divided by 7
Futhemore,
- 23K+1 will give us remainder 2
- 23K+1 can be written as (23K)*2 => Rem[23K/7] * 2
- 1* 2 = 2
Similarly,
- 23K+2 will give us remainder 4
- 23K+2 can be written as (23K)*2*2 => Rem[23K/7] * 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
- (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
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
- Logarithms – Questions | Formulas | How to Solve Quickly | Tricks & Shortcuts
- Clocks – Questions | Formulas | How to Solve Quickly | Tricks & Shortcuts
- Calendars – Questions | Formulas | How to Solve Quickly | Tricks & Shortcuts
- Clocks and Calendars – Questions | Formulas | How to Solve Quickly | Tricks & Shortcuts
- Logarithms –
Questions |
Formulas |
How to Solve Quickly |
Tricks & Shortcuts - Clocks –
Questions |
Formulas |
How to Solve Quickly |
Tricks & Shortcuts - Calendars –
Questions |
Formulas |
How to Solve Quickly |
Tricks & Shortcuts - Clocks and Calendars –
Questions |
Formulas |
How to Solve Quickly |
Tricks & Shortcuts