Elitmus
Exam
Category
what is the remainder of (169376^30)/31
Read Solution (Total 8)
-
- simply apply the fermat theorems that is a^(P-1)mod(P)=1 where a and p are prime numbers..so remainder is 1 ans
- 10 years agoHelpfull: Yes(11) No(0)
- when we defide 169376 by 31 , it will give reminder 23
means we can write 169376 as (31*n +23)
now 169376^30/31= (31*n +23)^30/31
after binomial expainsion of numerator we get all the term divisible by 31 except last term 23^30
Now think about 23^30
we can write it as (23^2)^15
23^2=529
now we have 529^15
when we devide 529 by 31 ,it will give reminder as 2
(529^15)/31=(31^m+2) ,after binomial expension of numerator we get all term divisible by 31 except last that is 2^15
now think about 2^15
that is 32^3=(31+1)^3
apply binomial expansion on numerator all term will be divisible by 31 except last
that is 1^3=1
hence reminder will be 1
Question is not so tough ,it follows traditional process but we have to solve this problem by dividing it into sub problem - 10 years agoHelpfull: Yes(4) No(0)
- correct ans is 1
previously i did small mistake in calculation - 10 years agoHelpfull: Yes(2) No(0)
- 169376 and 31 are co-prime to each other.
here m=16936, and n=31,,,
[m^p/n]=1,,,always where p=n(1-1/a)(1-1/b)......where n=a^x*b^y*c^z....
so here p=31(1-1/31)=30
So we can write...[169376^30]/31=1..
1 is the right answer.
- 10 years agoHelpfull: Yes(1) No(0)
- Ans is 8
169376^30/31
169376%31=23is remainder
so there 23 comes 30 times
23*30%31=690%31=8 remainder - 10 years agoHelpfull: Yes(0) No(6)
- where a is a prime no???
- 10 years agoHelpfull: Yes(0) No(0)
- ans is 1
at the end (2^5)^3 remains which give 1 remainder. - 10 years agoHelpfull: Yes(0) No(0)
- according to remainder theorem: [(x+a)^n]/x= a^n/x
so, 169376 mod 31=23
now, [(p*31+23)^30]/31= 23^30/31
= [(23^2)^15]/31
=529^15/31
applying the theorem again,
[(p*31+2)^15]/31
=2^15/31
=[(2^5)^3]/31
=32^3/31
=[(p*31+1)^3]/31(applying again)
=1^3/31
=1/31
so, remainder= 1 - 10 years agoHelpfull: Yes(0) No(0)
Elitmus Other Question