Number System : 108 Remainders

how to do 40!%83

Solution to ur problem

40! mod 83
We know tht--frm Wilson's Theorem
(p-1)!%p = (p-1) or -1(iff p is prime)
so, we can deduce
82!%83=-1 or 82---------------(1)
frm Wilson's Corollary
(p-2)!%p = 1
so, we can deduce here
81!%83=1-----------------(2)
Now 81!=81.80.79.-------.42.41!----------(3)
from 2 and 3
(81.80.79.--------.42.41!)%83=1
-2*-3*-4*-5....-41*41! = 41!*41!%83 = (41!)^2%83 = 1
which is possible only when 41! mod 83=1
because there are even no of terms so negative sign got cancelled

Now we have 41!mod83=1
(41.40!)%83=1
(-42.40!)%83=1
suppose 40!=x
(-42*x)%83=1
which is possible only when x becomes -2 or 81
so ans is 81






-----------------------------------------------------------------------------------




find the last three digits of 3^{1994 .}Hi Ambar
Here I go. 
3²⁰⁰⁰ = 3⁶*3¹⁹⁹⁴ = 1(mod1000)
Let 3¹⁹⁹⁴ = x(mod1000) and as 3⁶ = 729
=> 729x = 1(mod1000)
=> 729x - 1000y = 1
Now using Eulid's Algorithm
1 = 3(1) - 1(2)
1 = 3(1) - 1(8 - 2*3)
1 = 3(3) - 1(8)
1 = 3(19 - 2*8) - 1(8)
1 = 3(19) - 7(8)
1 = 3(19) - 7(84 - 4*19)
1 = 31(19) - 7(84)
1 = 31(187 - 2*84) - 7(84)
1 = 31(187) - 69(84)
1 = 31(187) - 69(271 - 187)
1 = 100(187) - 69(271)
1 = 100(729 - 2*271) - 69(271)
1 = 100(729) - 269(271)
1 = 100(729) - 269(1000 - 729)
1 = 369(729) - 269(1000)
=> 3¹⁹⁹⁴ = 369mod1000