341are you sure? i am pretty certain its 16
62For obvious reasons ... the remainder is same as the remainder when (31! / 17) is divided by 17
Use wilson's theorem to proceed after this..
-1 x (1.2.3.4.5.6.7.8.9.10.11.12.13.14) / 17
17,34,51,68,85,102,119, 136, 153,
=-1 x (2.9).(3.6).(5.7).(8.10).(11.12).(13..4).(14) / 17
=-1 x (18).(18).(35).(80).(11.12).(13..4).(14) / 17
=-1 x (-1). (1).(1).(-5).(-4).(1).(-3) / 17
=(5).(12) / 17
=(60) / 17
Which is equal to 9
I dont know if there is a simpler way... Am I missing something?
341
Hari Shankar
·2009-11-09 22:21:44
hmm, quite a silly mistake by me.[31-17 = 15 :( ]
As nishant sir pointed out, we have to find the remainder when 31!/17 is divided by 17.
i.e. when 16! (18*19*...*31) is divided by 17
From Wilson's Theorem 16!≡-1 mod 17
Now since 18≡1 , 19≡2.,..., 31≡14 mod 17
their product will be ≡ 14! mod 17
Again Wilson's Theorem tells us that 16!≡-1 mod 17
or 15! X 16 ≡-1 mod 17.
But 16≡-1 mod 17 so that 15!≡1 mod 17
That means 14! X 15≡1 mod 17
But 8X15≡1 mod 17 so that 14!≡8 mod 17
That gives that 31!/17≡-8≡9 mod 17
1prophet sir can you explain the 2nd last step
'14! X 15 ≡1mod 17
But 8X15 ≡ 1 mod 17 so that 14!≡8mod 17
62
Lokesh Verma
·2009-11-09 22:48:34
8 is the inverse of 15
so multiply both sides by 8
'14! X 15 ≡1mod 17
this implies
'14! X 15 x8 ≡1x8 mod 17
'14! X (15 x8) ≡1x8 mod 17
'14! X (1) ≡8 mod 17
341
Hari Shankar
·2009-11-09 23:38:20
Yeah actually I wanted to avoid introducing the concept of inverse but thats precisely how you reason it
14!≡1/15≡8 mod
Otherwise you have 14! X 15 ≡1 mod 17 and 8X15≡1 mod 17, so subtracting, we get (14!-8)X15≡0 mod 17, and since 17 does not divide 15, it divides 14!-8.
That means 14!-8≡0 mod 17 or 14!≡8 mod 17
1
fibonacci
·2009-11-10 00:01:56
got it thanks nishant sir and prophet sir
62
Lokesh Verma
·2009-11-10 00:11:32
@Eureka...
Wilson's Theorem is basically
(p-1)! ≡ -1 (mod p) for prime number p
1are dese questions useful for jee since wilson theorem is not in jee syllabus
62
Lokesh Verma
·2009-11-10 00:26:32
No this is not very important for JEE as such..
but this is like a 5 minute thing that does not require too much brain either :D
3lots of pinks here,but i cant understand even a single piece of discussion
