Don’t worry, unlock all articles / blogs on PrepInsta by just simply logging in on our website
Type atleast 3 characters
Popular Searches
Trending Pages
Notifications Mark All Read
Test Notification
Walmart is Hiring for 2024 and 2025! Batches Click here to apply!
PREPINSTA PRIME BIG BILLION SALE is live now. Go and grab the amazing offer.
asdasd
You have purchased Zoho Prime Mock Materials go to My Orders
You have purchased CTS Prime Mock Material. go to My Orders
February 18, 2023
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 –
Rem[(xy)/d] = Rem[ry/d]
where r is remainder when x divided by d
or
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
Rem[(a*b*c)/d] = Rem[a/d] * Rem[b/d] * Rem[c/d]
Rem[(a+b+c)/d] = Rem[a/d] + Rem[b/d] + Rem[c/d]
Rem[(3030)/7]
Rem[(303132)/7]
Futhemore,
Similarly,
Now, we need to write 3132 in 3K, 3K + 1, 3K + 2 format by doing follows –
Thus, can be written in format 3k+1
Thus, the remainder will be 2
Rem[X/Y] = Rem[kx/ky] = k *resultOf(Rem[x/y])
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
a = 3 & b = 5
So remainder for (215)/5 is 3.
So we now have,
r2 = 3, r1= 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
If p is a prime, and HCF (a, p) = 1 (a and p are co-primes), then Rem[ap-1/p] = 1
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.
ϕ(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)
Remainer of 267/33
Remainder of 353/63
Find the remainder when 40! is divided by 41?
Find the remainder when 45! is divided by 47?
Find the remainder when 21! is divided by 361?
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in 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
Get Hiring Updates right in your inbox from PrepInsta